1 //===- Attributor.h --- Module-wide attribute deduction ---------*- 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 // Attributor: An inter procedural (abstract) "attribute" deduction framework. 10 // 11 // The Attributor framework is an inter procedural abstract analysis (fixpoint 12 // iteration analysis). The goal is to allow easy deduction of new attributes as 13 // well as information exchange between abstract attributes in-flight. 14 // 15 // The Attributor class is the driver and the link between the various abstract 16 // attributes. The Attributor will iterate until a fixpoint state is reached by 17 // all abstract attributes in-flight, or until it will enforce a pessimistic fix 18 // point because an iteration limit is reached. 19 // 20 // Abstract attributes, derived from the AbstractAttribute class, actually 21 // describe properties of the code. They can correspond to actual LLVM-IR 22 // attributes, or they can be more general, ultimately unrelated to LLVM-IR 23 // attributes. The latter is useful when an abstract attributes provides 24 // information to other abstract attributes in-flight but we might not want to 25 // manifest the information. The Attributor allows to query in-flight abstract 26 // attributes through the `Attributor::getAAFor` method (see the method 27 // description for an example). If the method is used by an abstract attribute 28 // P, and it results in an abstract attribute Q, the Attributor will 29 // automatically capture a potential dependence from Q to P. This dependence 30 // will cause P to be reevaluated whenever Q changes in the future. 31 // 32 // The Attributor will only reevaluate abstract attributes that might have 33 // changed since the last iteration. That means that the Attribute will not 34 // revisit all instructions/blocks/functions in the module but only query 35 // an update from a subset of the abstract attributes. 36 // 37 // The update method `AbstractAttribute::updateImpl` is implemented by the 38 // specific "abstract attribute" subclasses. The method is invoked whenever the 39 // currently assumed state (see the AbstractState class) might not be valid 40 // anymore. This can, for example, happen if the state was dependent on another 41 // abstract attribute that changed. In every invocation, the update method has 42 // to adjust the internal state of an abstract attribute to a point that is 43 // justifiable by the underlying IR and the current state of abstract attributes 44 // in-flight. Since the IR is given and assumed to be valid, the information 45 // derived from it can be assumed to hold. However, information derived from 46 // other abstract attributes is conditional on various things. If the justifying 47 // state changed, the `updateImpl` has to revisit the situation and potentially 48 // find another justification or limit the optimistic assumes made. 49 // 50 // Change is the key in this framework. Until a state of no-change, thus a 51 // fixpoint, is reached, the Attributor will query the abstract attributes 52 // in-flight to re-evaluate their state. If the (current) state is too 53 // optimistic, hence it cannot be justified anymore through other abstract 54 // attributes or the state of the IR, the state of the abstract attribute will 55 // have to change. Generally, we assume abstract attribute state to be a finite 56 // height lattice and the update function to be monotone. However, these 57 // conditions are not enforced because the iteration limit will guarantee 58 // termination. If an optimistic fixpoint is reached, or a pessimistic fix 59 // point is enforced after a timeout, the abstract attributes are tasked to 60 // manifest their result in the IR for passes to come. 61 // 62 // Attribute manifestation is not mandatory. If desired, there is support to 63 // generate a single or multiple LLVM-IR attributes already in the helper struct 64 // IRAttribute. In the simplest case, a subclass inherits from IRAttribute with 65 // a proper Attribute::AttrKind as template parameter. The Attributor 66 // manifestation framework will then create and place a new attribute if it is 67 // allowed to do so (based on the abstract state). Other use cases can be 68 // achieved by overloading AbstractAttribute or IRAttribute methods. 69 // 70 // 71 // The "mechanics" of adding a new "abstract attribute": 72 // - Define a class (transitively) inheriting from AbstractAttribute and one 73 // (which could be the same) that (transitively) inherits from AbstractState. 74 // For the latter, consider the already available BooleanState and 75 // {Inc,Dec,Bit}IntegerState if they fit your needs, e.g., you require only a 76 // number tracking or bit-encoding. 77 // - Implement all pure methods. Also use overloading if the attribute is not 78 // conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for 79 // an argument, call site argument, function return value, or function. See 80 // the class and method descriptions for more information on the two 81 // "Abstract" classes and their respective methods. 82 // - Register opportunities for the new abstract attribute in the 83 // `Attributor::identifyDefaultAbstractAttributes` method if it should be 84 // counted as a 'default' attribute. 85 // - Add sufficient tests. 86 // - Add a Statistics object for bookkeeping. If it is a simple (set of) 87 // attribute(s) manifested through the Attributor manifestation framework, see 88 // the bookkeeping function in Attributor.cpp. 89 // - If instructions with a certain opcode are interesting to the attribute, add 90 // that opcode to the switch in `Attributor::identifyAbstractAttributes`. This 91 // will make it possible to query all those instructions through the 92 // `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the 93 // need to traverse the IR repeatedly. 94 // 95 //===----------------------------------------------------------------------===// 96 97 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H 98 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H 99 100 #include "llvm/ADT/DenseSet.h" 101 #include "llvm/ADT/GraphTraits.h" 102 #include "llvm/ADT/MapVector.h" 103 #include "llvm/ADT/STLExtras.h" 104 #include "llvm/ADT/SetOperations.h" 105 #include "llvm/ADT/SetVector.h" 106 #include "llvm/ADT/SmallSet.h" 107 #include "llvm/ADT/iterator.h" 108 #include "llvm/Analysis/AssumeBundleQueries.h" 109 #include "llvm/Analysis/CFG.h" 110 #include "llvm/Analysis/CGSCCPassManager.h" 111 #include "llvm/Analysis/LazyCallGraph.h" 112 #include "llvm/Analysis/LoopInfo.h" 113 #include "llvm/Analysis/MemoryLocation.h" 114 #include "llvm/Analysis/MustExecute.h" 115 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 116 #include "llvm/Analysis/PostDominators.h" 117 #include "llvm/Analysis/TargetLibraryInfo.h" 118 #include "llvm/IR/AbstractCallSite.h" 119 #include "llvm/IR/Attributes.h" 120 #include "llvm/IR/ConstantRange.h" 121 #include "llvm/IR/Constants.h" 122 #include "llvm/IR/GlobalValue.h" 123 #include "llvm/IR/InstIterator.h" 124 #include "llvm/IR/Instruction.h" 125 #include "llvm/IR/Instructions.h" 126 #include "llvm/IR/PassManager.h" 127 #include "llvm/IR/Value.h" 128 #include "llvm/Support/Alignment.h" 129 #include "llvm/Support/Allocator.h" 130 #include "llvm/Support/Casting.h" 131 #include "llvm/Support/DOTGraphTraits.h" 132 #include "llvm/Support/DebugCounter.h" 133 #include "llvm/Support/ErrorHandling.h" 134 #include "llvm/Support/ModRef.h" 135 #include "llvm/Support/TimeProfiler.h" 136 #include "llvm/Support/TypeSize.h" 137 #include "llvm/TargetParser/Triple.h" 138 #include "llvm/Transforms/Utils/CallGraphUpdater.h" 139 140 #include <limits> 141 #include <map> 142 #include <optional> 143 144 namespace llvm { 145 146 class DataLayout; 147 class LLVMContext; 148 class Pass; 149 template <typename Fn> class function_ref; 150 struct AADepGraphNode; 151 struct AADepGraph; 152 struct Attributor; 153 struct AbstractAttribute; 154 struct InformationCache; 155 struct AAIsDead; 156 struct AttributorCallGraph; 157 struct IRPosition; 158 159 class Function; 160 161 /// Abstract Attribute helper functions. 162 namespace AA { 163 using InstExclusionSetTy = SmallPtrSet<Instruction *, 4>; 164 165 enum class GPUAddressSpace : unsigned { 166 Generic = 0, 167 Global = 1, 168 Shared = 3, 169 Constant = 4, 170 Local = 5, 171 }; 172 173 /// Return true iff \p M target a GPU (and we can use GPU AS reasoning). 174 bool isGPU(const Module &M); 175 176 /// Flags to distinguish intra-procedural queries from *potentially* 177 /// inter-procedural queries. Not that information can be valid for both and 178 /// therefore both bits might be set. 179 enum ValueScope : uint8_t { 180 Intraprocedural = 1, 181 Interprocedural = 2, 182 AnyScope = Intraprocedural | Interprocedural, 183 }; 184 185 struct ValueAndContext : public std::pair<Value *, const Instruction *> { 186 using Base = std::pair<Value *, const Instruction *>; 187 ValueAndContext(const Base &B) : Base(B) {} 188 ValueAndContext(Value &V, const Instruction *CtxI) : Base(&V, CtxI) {} 189 ValueAndContext(Value &V, const Instruction &CtxI) : Base(&V, &CtxI) {} 190 191 Value *getValue() const { return this->first; } 192 const Instruction *getCtxI() const { return this->second; } 193 }; 194 195 /// Return true if \p I is a `nosync` instruction. Use generic reasoning and 196 /// potentially the corresponding AANoSync. 197 bool isNoSyncInst(Attributor &A, const Instruction &I, 198 const AbstractAttribute &QueryingAA); 199 200 /// Return true if \p V is dynamically unique, that is, there are no two 201 /// "instances" of \p V at runtime with different values. 202 /// Note: If \p ForAnalysisOnly is set we only check that the Attributor will 203 /// never use \p V to represent two "instances" not that \p V could not 204 /// technically represent them. 205 bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA, 206 const Value &V, bool ForAnalysisOnly = true); 207 208 /// Return true if \p V is a valid value in \p Scope, that is a constant or an 209 /// instruction/argument of \p Scope. 210 bool isValidInScope(const Value &V, const Function *Scope); 211 212 /// Return true if the value of \p VAC is a valid at the position of \p VAC, 213 /// that is a constant, an argument of the same function, or an instruction in 214 /// that function that dominates the position. 215 bool isValidAtPosition(const ValueAndContext &VAC, InformationCache &InfoCache); 216 217 /// Try to convert \p V to type \p Ty without introducing new instructions. If 218 /// this is not possible return `nullptr`. Note: this function basically knows 219 /// how to cast various constants. 220 Value *getWithType(Value &V, Type &Ty); 221 222 /// Return the combination of \p A and \p B such that the result is a possible 223 /// value of both. \p B is potentially casted to match the type \p Ty or the 224 /// type of \p A if \p Ty is null. 225 /// 226 /// Examples: 227 /// X + none => X 228 /// not_none + undef => not_none 229 /// V1 + V2 => nullptr 230 std::optional<Value *> 231 combineOptionalValuesInAAValueLatice(const std::optional<Value *> &A, 232 const std::optional<Value *> &B, Type *Ty); 233 234 /// Helper to represent an access offset and size, with logic to deal with 235 /// uncertainty and check for overlapping accesses. 236 struct RangeTy { 237 int64_t Offset = Unassigned; 238 int64_t Size = Unassigned; 239 240 RangeTy(int64_t Offset, int64_t Size) : Offset(Offset), Size(Size) {} 241 RangeTy() = default; 242 static RangeTy getUnknown() { return RangeTy{Unknown, Unknown}; } 243 244 /// Return true if offset or size are unknown. 245 bool offsetOrSizeAreUnknown() const { 246 return Offset == RangeTy::Unknown || Size == RangeTy::Unknown; 247 } 248 249 /// Return true if offset and size are unknown, thus this is the default 250 /// unknown object. 251 bool offsetAndSizeAreUnknown() const { 252 return Offset == RangeTy::Unknown && Size == RangeTy::Unknown; 253 } 254 255 /// Return true if the offset and size are unassigned. 256 bool isUnassigned() const { 257 assert((Offset == RangeTy::Unassigned) == (Size == RangeTy::Unassigned) && 258 "Inconsistent state!"); 259 return Offset == RangeTy::Unassigned; 260 } 261 262 /// Return true if this offset and size pair might describe an address that 263 /// overlaps with \p Range. 264 bool mayOverlap(const RangeTy &Range) const { 265 // Any unknown value and we are giving up -> overlap. 266 if (offsetOrSizeAreUnknown() || Range.offsetOrSizeAreUnknown()) 267 return true; 268 269 // Check if one offset point is in the other interval [offset, 270 // offset+size]. 271 return Range.Offset + Range.Size > Offset && Range.Offset < Offset + Size; 272 } 273 274 RangeTy &operator&=(const RangeTy &R) { 275 if (R.isUnassigned()) 276 return *this; 277 if (isUnassigned()) 278 return *this = R; 279 if (Offset == Unknown || R.Offset == Unknown) 280 Offset = Unknown; 281 if (Size == Unknown || R.Size == Unknown) 282 Size = Unknown; 283 if (offsetAndSizeAreUnknown()) 284 return *this; 285 if (Offset == Unknown) { 286 Size = std::max(Size, R.Size); 287 } else if (Size == Unknown) { 288 Offset = std::min(Offset, R.Offset); 289 } else { 290 Offset = std::min(Offset, R.Offset); 291 Size = std::max(Offset + Size, R.Offset + R.Size) - Offset; 292 } 293 return *this; 294 } 295 296 /// Comparison for sorting ranges by offset. 297 /// 298 /// Returns true if the offset \p L is less than that of \p R. 299 inline static bool OffsetLessThan(const RangeTy &L, const RangeTy &R) { 300 return L.Offset < R.Offset; 301 } 302 303 /// Constants used to represent special offsets or sizes. 304 /// - We cannot assume that Offsets and Size are non-negative. 305 /// - The constants should not clash with DenseMapInfo, such as EmptyKey 306 /// (INT64_MAX) and TombstoneKey (INT64_MIN). 307 /// We use values "in the middle" of the 64 bit range to represent these 308 /// special cases. 309 static constexpr int64_t Unassigned = std::numeric_limits<int32_t>::min(); 310 static constexpr int64_t Unknown = std::numeric_limits<int32_t>::max(); 311 }; 312 313 inline raw_ostream &operator<<(raw_ostream &OS, const RangeTy &R) { 314 OS << "[" << R.Offset << ", " << R.Size << "]"; 315 return OS; 316 } 317 318 inline bool operator==(const RangeTy &A, const RangeTy &B) { 319 return A.Offset == B.Offset && A.Size == B.Size; 320 } 321 322 inline bool operator!=(const RangeTy &A, const RangeTy &B) { return !(A == B); } 323 324 /// Return the initial value of \p Obj with type \p Ty if that is a constant. 325 Constant *getInitialValueForObj(Attributor &A, 326 const AbstractAttribute &QueryingAA, Value &Obj, 327 Type &Ty, const TargetLibraryInfo *TLI, 328 const DataLayout &DL, 329 RangeTy *RangePtr = nullptr); 330 331 /// Collect all potential values \p LI could read into \p PotentialValues. That 332 /// is, the only values read by \p LI are assumed to be known and all are in 333 /// \p PotentialValues. \p PotentialValueOrigins will contain all the 334 /// instructions that might have put a potential value into \p PotentialValues. 335 /// Dependences onto \p QueryingAA are properly tracked, \p 336 /// UsedAssumedInformation will inform the caller if assumed information was 337 /// used. 338 /// 339 /// \returns True if the assumed potential copies are all in \p PotentialValues, 340 /// false if something went wrong and the copies could not be 341 /// determined. 342 bool getPotentiallyLoadedValues( 343 Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues, 344 SmallSetVector<Instruction *, 4> &PotentialValueOrigins, 345 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation, 346 bool OnlyExact = false); 347 348 /// Collect all potential values of the one stored by \p SI into 349 /// \p PotentialCopies. That is, the only copies that were made via the 350 /// store are assumed to be known and all are in \p PotentialCopies. Dependences 351 /// onto \p QueryingAA are properly tracked, \p UsedAssumedInformation will 352 /// inform the caller if assumed information was used. 353 /// 354 /// \returns True if the assumed potential copies are all in \p PotentialCopies, 355 /// false if something went wrong and the copies could not be 356 /// determined. 357 bool getPotentialCopiesOfStoredValue( 358 Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies, 359 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation, 360 bool OnlyExact = false); 361 362 /// Return true if \p IRP is readonly. This will query respective AAs that 363 /// deduce the information and introduce dependences for \p QueryingAA. 364 bool isAssumedReadOnly(Attributor &A, const IRPosition &IRP, 365 const AbstractAttribute &QueryingAA, bool &IsKnown); 366 367 /// Return true if \p IRP is readnone. This will query respective AAs that 368 /// deduce the information and introduce dependences for \p QueryingAA. 369 bool isAssumedReadNone(Attributor &A, const IRPosition &IRP, 370 const AbstractAttribute &QueryingAA, bool &IsKnown); 371 372 /// Return true if \p ToI is potentially reachable from \p FromI without running 373 /// into any instruction in \p ExclusionSet The two instructions do not need to 374 /// be in the same function. \p GoBackwardsCB can be provided to convey domain 375 /// knowledge about the "lifespan" the user is interested in. By default, the 376 /// callers of \p FromI are checked as well to determine if \p ToI can be 377 /// reached. If the query is not interested in callers beyond a certain point, 378 /// e.g., a GPU kernel entry or the function containing an alloca, the 379 /// \p GoBackwardsCB should return false. 380 bool isPotentiallyReachable( 381 Attributor &A, const Instruction &FromI, const Instruction &ToI, 382 const AbstractAttribute &QueryingAA, 383 const AA::InstExclusionSetTy *ExclusionSet = nullptr, 384 std::function<bool(const Function &F)> GoBackwardsCB = nullptr); 385 386 /// Same as above but it is sufficient to reach any instruction in \p ToFn. 387 bool isPotentiallyReachable( 388 Attributor &A, const Instruction &FromI, const Function &ToFn, 389 const AbstractAttribute &QueryingAA, 390 const AA::InstExclusionSetTy *ExclusionSet = nullptr, 391 std::function<bool(const Function &F)> GoBackwardsCB = nullptr); 392 393 /// Return true if \p Obj is assumed to be a thread local object. 394 bool isAssumedThreadLocalObject(Attributor &A, Value &Obj, 395 const AbstractAttribute &QueryingAA); 396 397 /// Return true if \p I is potentially affected by a barrier. 398 bool isPotentiallyAffectedByBarrier(Attributor &A, const Instruction &I, 399 const AbstractAttribute &QueryingAA); 400 bool isPotentiallyAffectedByBarrier(Attributor &A, ArrayRef<const Value *> Ptrs, 401 const AbstractAttribute &QueryingAA, 402 const Instruction *CtxI); 403 } // namespace AA 404 405 template <> 406 struct DenseMapInfo<AA::ValueAndContext> 407 : public DenseMapInfo<AA::ValueAndContext::Base> { 408 using Base = DenseMapInfo<AA::ValueAndContext::Base>; 409 static inline AA::ValueAndContext getEmptyKey() { 410 return Base::getEmptyKey(); 411 } 412 static inline AA::ValueAndContext getTombstoneKey() { 413 return Base::getTombstoneKey(); 414 } 415 static unsigned getHashValue(const AA::ValueAndContext &VAC) { 416 return Base::getHashValue(VAC); 417 } 418 419 static bool isEqual(const AA::ValueAndContext &LHS, 420 const AA::ValueAndContext &RHS) { 421 return Base::isEqual(LHS, RHS); 422 } 423 }; 424 425 template <> 426 struct DenseMapInfo<AA::ValueScope> : public DenseMapInfo<unsigned char> { 427 using Base = DenseMapInfo<unsigned char>; 428 static inline AA::ValueScope getEmptyKey() { 429 return AA::ValueScope(Base::getEmptyKey()); 430 } 431 static inline AA::ValueScope getTombstoneKey() { 432 return AA::ValueScope(Base::getTombstoneKey()); 433 } 434 static unsigned getHashValue(const AA::ValueScope &S) { 435 return Base::getHashValue(S); 436 } 437 438 static bool isEqual(const AA::ValueScope &LHS, const AA::ValueScope &RHS) { 439 return Base::isEqual(LHS, RHS); 440 } 441 }; 442 443 template <> 444 struct DenseMapInfo<const AA::InstExclusionSetTy *> 445 : public DenseMapInfo<void *> { 446 using super = DenseMapInfo<void *>; 447 static inline const AA::InstExclusionSetTy *getEmptyKey() { 448 return static_cast<const AA::InstExclusionSetTy *>(super::getEmptyKey()); 449 } 450 static inline const AA::InstExclusionSetTy *getTombstoneKey() { 451 return static_cast<const AA::InstExclusionSetTy *>( 452 super::getTombstoneKey()); 453 } 454 static unsigned getHashValue(const AA::InstExclusionSetTy *BES) { 455 unsigned H = 0; 456 if (BES) 457 for (const auto *II : *BES) 458 H += DenseMapInfo<const Instruction *>::getHashValue(II); 459 return H; 460 } 461 static bool isEqual(const AA::InstExclusionSetTy *LHS, 462 const AA::InstExclusionSetTy *RHS) { 463 if (LHS == RHS) 464 return true; 465 if (LHS == getEmptyKey() || RHS == getEmptyKey() || 466 LHS == getTombstoneKey() || RHS == getTombstoneKey()) 467 return false; 468 auto SizeLHS = LHS ? LHS->size() : 0; 469 auto SizeRHS = RHS ? RHS->size() : 0; 470 if (SizeLHS != SizeRHS) 471 return false; 472 if (SizeRHS == 0) 473 return true; 474 return llvm::set_is_subset(*LHS, *RHS); 475 } 476 }; 477 478 /// The value passed to the line option that defines the maximal initialization 479 /// chain length. 480 extern unsigned MaxInitializationChainLength; 481 482 ///{ 483 enum class ChangeStatus { 484 CHANGED, 485 UNCHANGED, 486 }; 487 488 ChangeStatus operator|(ChangeStatus l, ChangeStatus r); 489 ChangeStatus &operator|=(ChangeStatus &l, ChangeStatus r); 490 ChangeStatus operator&(ChangeStatus l, ChangeStatus r); 491 ChangeStatus &operator&=(ChangeStatus &l, ChangeStatus r); 492 493 enum class DepClassTy { 494 REQUIRED, ///< The target cannot be valid if the source is not. 495 OPTIONAL, ///< The target may be valid if the source is not. 496 NONE, ///< Do not track a dependence between source and target. 497 }; 498 ///} 499 500 /// The data structure for the nodes of a dependency graph 501 struct AADepGraphNode { 502 public: 503 virtual ~AADepGraphNode() = default; 504 using DepTy = PointerIntPair<AADepGraphNode *, 1>; 505 using DepSetTy = SmallSetVector<DepTy, 2>; 506 507 protected: 508 /// Set of dependency graph nodes which should be updated if this one 509 /// is updated. The bit encodes if it is optional. 510 DepSetTy Deps; 511 512 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); } 513 static AbstractAttribute *DepGetValAA(const DepTy &DT) { 514 return cast<AbstractAttribute>(DT.getPointer()); 515 } 516 517 operator AbstractAttribute *() { return cast<AbstractAttribute>(this); } 518 519 public: 520 using iterator = mapped_iterator<DepSetTy::iterator, decltype(&DepGetVal)>; 521 using aaiterator = 522 mapped_iterator<DepSetTy::iterator, decltype(&DepGetValAA)>; 523 524 aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); } 525 aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); } 526 iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); } 527 iterator child_end() { return iterator(Deps.end(), &DepGetVal); } 528 529 void print(raw_ostream &OS) const { print(nullptr, OS); } 530 virtual void print(Attributor *, raw_ostream &OS) const { 531 OS << "AADepNode Impl\n"; 532 } 533 DepSetTy &getDeps() { return Deps; } 534 535 friend struct Attributor; 536 friend struct AADepGraph; 537 }; 538 539 /// The data structure for the dependency graph 540 /// 541 /// Note that in this graph if there is an edge from A to B (A -> B), 542 /// then it means that B depends on A, and when the state of A is 543 /// updated, node B should also be updated 544 struct AADepGraph { 545 AADepGraph() = default; 546 ~AADepGraph() = default; 547 548 using DepTy = AADepGraphNode::DepTy; 549 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); } 550 using iterator = 551 mapped_iterator<AADepGraphNode::DepSetTy::iterator, decltype(&DepGetVal)>; 552 553 /// There is no root node for the dependency graph. But the SCCIterator 554 /// requires a single entry point, so we maintain a fake("synthetic") root 555 /// node that depends on every node. 556 AADepGraphNode SyntheticRoot; 557 AADepGraphNode *GetEntryNode() { return &SyntheticRoot; } 558 559 iterator begin() { return SyntheticRoot.child_begin(); } 560 iterator end() { return SyntheticRoot.child_end(); } 561 562 void viewGraph(); 563 564 /// Dump graph to file 565 void dumpGraph(); 566 567 /// Print dependency graph 568 void print(); 569 }; 570 571 /// Helper to describe and deal with positions in the LLVM-IR. 572 /// 573 /// A position in the IR is described by an anchor value and an "offset" that 574 /// could be the argument number, for call sites and arguments, or an indicator 575 /// of the "position kind". The kinds, specified in the Kind enum below, include 576 /// the locations in the attribute list, i.a., function scope and return value, 577 /// as well as a distinction between call sites and functions. Finally, there 578 /// are floating values that do not have a corresponding attribute list 579 /// position. 580 struct IRPosition { 581 // NOTE: In the future this definition can be changed to support recursive 582 // functions. 583 using CallBaseContext = CallBase; 584 585 /// The positions we distinguish in the IR. 586 enum Kind : char { 587 IRP_INVALID, ///< An invalid position. 588 IRP_FLOAT, ///< A position that is not associated with a spot suitable 589 ///< for attributes. This could be any value or instruction. 590 IRP_RETURNED, ///< An attribute for the function return value. 591 IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value. 592 IRP_FUNCTION, ///< An attribute for a function (scope). 593 IRP_CALL_SITE, ///< An attribute for a call site (function scope). 594 IRP_ARGUMENT, ///< An attribute for a function argument. 595 IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument. 596 }; 597 598 /// Default constructor available to create invalid positions implicitly. All 599 /// other positions need to be created explicitly through the appropriate 600 /// static member function. 601 IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); } 602 603 /// Create a position describing the value of \p V. 604 static const IRPosition value(const Value &V, 605 const CallBaseContext *CBContext = nullptr) { 606 if (auto *Arg = dyn_cast<Argument>(&V)) 607 return IRPosition::argument(*Arg, CBContext); 608 if (auto *CB = dyn_cast<CallBase>(&V)) 609 return IRPosition::callsite_returned(*CB); 610 return IRPosition(const_cast<Value &>(V), IRP_FLOAT, CBContext); 611 } 612 613 /// Create a position describing the instruction \p I. This is different from 614 /// the value version because call sites are treated as intrusctions rather 615 /// than their return value in this function. 616 static const IRPosition inst(const Instruction &I, 617 const CallBaseContext *CBContext = nullptr) { 618 return IRPosition(const_cast<Instruction &>(I), IRP_FLOAT, CBContext); 619 } 620 621 /// Create a position describing the function scope of \p F. 622 /// \p CBContext is used for call base specific analysis. 623 static const IRPosition function(const Function &F, 624 const CallBaseContext *CBContext = nullptr) { 625 return IRPosition(const_cast<Function &>(F), IRP_FUNCTION, CBContext); 626 } 627 628 /// Create a position describing the returned value of \p F. 629 /// \p CBContext is used for call base specific analysis. 630 static const IRPosition returned(const Function &F, 631 const CallBaseContext *CBContext = nullptr) { 632 return IRPosition(const_cast<Function &>(F), IRP_RETURNED, CBContext); 633 } 634 635 /// Create a position describing the argument \p Arg. 636 /// \p CBContext is used for call base specific analysis. 637 static const IRPosition argument(const Argument &Arg, 638 const CallBaseContext *CBContext = nullptr) { 639 return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT, CBContext); 640 } 641 642 /// Create a position describing the function scope of \p CB. 643 static const IRPosition callsite_function(const CallBase &CB) { 644 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE); 645 } 646 647 /// Create a position describing the returned value of \p CB. 648 static const IRPosition callsite_returned(const CallBase &CB) { 649 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED); 650 } 651 652 /// Create a position describing the argument of \p CB at position \p ArgNo. 653 static const IRPosition callsite_argument(const CallBase &CB, 654 unsigned ArgNo) { 655 return IRPosition(const_cast<Use &>(CB.getArgOperandUse(ArgNo)), 656 IRP_CALL_SITE_ARGUMENT); 657 } 658 659 /// Create a position describing the argument of \p ACS at position \p ArgNo. 660 static const IRPosition callsite_argument(AbstractCallSite ACS, 661 unsigned ArgNo) { 662 if (ACS.getNumArgOperands() <= ArgNo) 663 return IRPosition(); 664 int CSArgNo = ACS.getCallArgOperandNo(ArgNo); 665 if (CSArgNo >= 0) 666 return IRPosition::callsite_argument( 667 cast<CallBase>(*ACS.getInstruction()), CSArgNo); 668 return IRPosition(); 669 } 670 671 /// Create a position with function scope matching the "context" of \p IRP. 672 /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result 673 /// will be a call site position, otherwise the function position of the 674 /// associated function. 675 static const IRPosition 676 function_scope(const IRPosition &IRP, 677 const CallBaseContext *CBContext = nullptr) { 678 if (IRP.isAnyCallSitePosition()) { 679 return IRPosition::callsite_function( 680 cast<CallBase>(IRP.getAnchorValue())); 681 } 682 assert(IRP.getAssociatedFunction()); 683 return IRPosition::function(*IRP.getAssociatedFunction(), CBContext); 684 } 685 686 bool operator==(const IRPosition &RHS) const { 687 return Enc == RHS.Enc && RHS.CBContext == CBContext; 688 } 689 bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); } 690 691 /// Return the value this abstract attribute is anchored with. 692 /// 693 /// The anchor value might not be the associated value if the latter is not 694 /// sufficient to determine where arguments will be manifested. This is, so 695 /// far, only the case for call site arguments as the value is not sufficient 696 /// to pinpoint them. Instead, we can use the call site as an anchor. 697 Value &getAnchorValue() const { 698 switch (getEncodingBits()) { 699 case ENC_VALUE: 700 case ENC_RETURNED_VALUE: 701 case ENC_FLOATING_FUNCTION: 702 return *getAsValuePtr(); 703 case ENC_CALL_SITE_ARGUMENT_USE: 704 return *(getAsUsePtr()->getUser()); 705 default: 706 llvm_unreachable("Unkown encoding!"); 707 }; 708 } 709 710 /// Return the associated function, if any. 711 Function *getAssociatedFunction() const { 712 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) { 713 // We reuse the logic that associates callback calles to arguments of a 714 // call site here to identify the callback callee as the associated 715 // function. 716 if (Argument *Arg = getAssociatedArgument()) 717 return Arg->getParent(); 718 return dyn_cast_if_present<Function>( 719 CB->getCalledOperand()->stripPointerCasts()); 720 } 721 return getAnchorScope(); 722 } 723 724 /// Return the associated argument, if any. 725 Argument *getAssociatedArgument() const; 726 727 /// Return true if the position refers to a function interface, that is the 728 /// function scope, the function return, or an argument. 729 bool isFnInterfaceKind() const { 730 switch (getPositionKind()) { 731 case IRPosition::IRP_FUNCTION: 732 case IRPosition::IRP_RETURNED: 733 case IRPosition::IRP_ARGUMENT: 734 return true; 735 default: 736 return false; 737 } 738 } 739 740 /// Return true if this is a function or call site position. 741 bool isFunctionScope() const { 742 switch (getPositionKind()) { 743 case IRPosition::IRP_CALL_SITE: 744 case IRPosition::IRP_FUNCTION: 745 return true; 746 default: 747 return false; 748 }; 749 } 750 751 /// Return the Function surrounding the anchor value. 752 Function *getAnchorScope() const { 753 Value &V = getAnchorValue(); 754 if (isa<Function>(V)) 755 return &cast<Function>(V); 756 if (isa<Argument>(V)) 757 return cast<Argument>(V).getParent(); 758 if (isa<Instruction>(V)) 759 return cast<Instruction>(V).getFunction(); 760 return nullptr; 761 } 762 763 /// Return the context instruction, if any. 764 Instruction *getCtxI() const { 765 Value &V = getAnchorValue(); 766 if (auto *I = dyn_cast<Instruction>(&V)) 767 return I; 768 if (auto *Arg = dyn_cast<Argument>(&V)) 769 if (!Arg->getParent()->isDeclaration()) 770 return &Arg->getParent()->getEntryBlock().front(); 771 if (auto *F = dyn_cast<Function>(&V)) 772 if (!F->isDeclaration()) 773 return &(F->getEntryBlock().front()); 774 return nullptr; 775 } 776 777 /// Return the value this abstract attribute is associated with. 778 Value &getAssociatedValue() const { 779 if (getCallSiteArgNo() < 0 || isa<Argument>(&getAnchorValue())) 780 return getAnchorValue(); 781 assert(isa<CallBase>(&getAnchorValue()) && "Expected a call base!"); 782 return *cast<CallBase>(&getAnchorValue()) 783 ->getArgOperand(getCallSiteArgNo()); 784 } 785 786 /// Return the type this abstract attribute is associated with. 787 Type *getAssociatedType() const { 788 if (getPositionKind() == IRPosition::IRP_RETURNED) 789 return getAssociatedFunction()->getReturnType(); 790 return getAssociatedValue().getType(); 791 } 792 793 /// Return the callee argument number of the associated value if it is an 794 /// argument or call site argument, otherwise a negative value. In contrast to 795 /// `getCallSiteArgNo` this method will always return the "argument number" 796 /// from the perspective of the callee. This may not the same as the call site 797 /// if this is a callback call. 798 int getCalleeArgNo() const { 799 return getArgNo(/* CallbackCalleeArgIfApplicable */ true); 800 } 801 802 /// Return the call site argument number of the associated value if it is an 803 /// argument or call site argument, otherwise a negative value. In contrast to 804 /// `getCalleArgNo` this method will always return the "operand number" from 805 /// the perspective of the call site. This may not the same as the callee 806 /// perspective if this is a callback call. 807 int getCallSiteArgNo() const { 808 return getArgNo(/* CallbackCalleeArgIfApplicable */ false); 809 } 810 811 /// Return the index in the attribute list for this position. 812 unsigned getAttrIdx() const { 813 switch (getPositionKind()) { 814 case IRPosition::IRP_INVALID: 815 case IRPosition::IRP_FLOAT: 816 break; 817 case IRPosition::IRP_FUNCTION: 818 case IRPosition::IRP_CALL_SITE: 819 return AttributeList::FunctionIndex; 820 case IRPosition::IRP_RETURNED: 821 case IRPosition::IRP_CALL_SITE_RETURNED: 822 return AttributeList::ReturnIndex; 823 case IRPosition::IRP_ARGUMENT: 824 return getCalleeArgNo() + AttributeList::FirstArgIndex; 825 case IRPosition::IRP_CALL_SITE_ARGUMENT: 826 return getCallSiteArgNo() + AttributeList::FirstArgIndex; 827 } 828 llvm_unreachable( 829 "There is no attribute index for a floating or invalid position!"); 830 } 831 832 /// Return the value attributes are attached to. 833 Value *getAttrListAnchor() const { 834 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) 835 return CB; 836 return getAssociatedFunction(); 837 } 838 839 /// Return the attributes associated with this function or call site scope. 840 AttributeList getAttrList() const { 841 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) 842 return CB->getAttributes(); 843 return getAssociatedFunction()->getAttributes(); 844 } 845 846 /// Update the attributes associated with this function or call site scope. 847 void setAttrList(const AttributeList &AttrList) const { 848 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) 849 return CB->setAttributes(AttrList); 850 return getAssociatedFunction()->setAttributes(AttrList); 851 } 852 853 /// Return the number of arguments associated with this function or call site 854 /// scope. 855 unsigned getNumArgs() const { 856 assert((getPositionKind() == IRP_CALL_SITE || 857 getPositionKind() == IRP_FUNCTION) && 858 "Only valid for function/call site positions!"); 859 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) 860 return CB->arg_size(); 861 return getAssociatedFunction()->arg_size(); 862 } 863 864 /// Return theargument \p ArgNo associated with this function or call site 865 /// scope. 866 Value *getArg(unsigned ArgNo) const { 867 assert((getPositionKind() == IRP_CALL_SITE || 868 getPositionKind() == IRP_FUNCTION) && 869 "Only valid for function/call site positions!"); 870 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) 871 return CB->getArgOperand(ArgNo); 872 return getAssociatedFunction()->getArg(ArgNo); 873 } 874 875 /// Return the associated position kind. 876 Kind getPositionKind() const { 877 char EncodingBits = getEncodingBits(); 878 if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE) 879 return IRP_CALL_SITE_ARGUMENT; 880 if (EncodingBits == ENC_FLOATING_FUNCTION) 881 return IRP_FLOAT; 882 883 Value *V = getAsValuePtr(); 884 if (!V) 885 return IRP_INVALID; 886 if (isa<Argument>(V)) 887 return IRP_ARGUMENT; 888 if (isa<Function>(V)) 889 return isReturnPosition(EncodingBits) ? IRP_RETURNED : IRP_FUNCTION; 890 if (isa<CallBase>(V)) 891 return isReturnPosition(EncodingBits) ? IRP_CALL_SITE_RETURNED 892 : IRP_CALL_SITE; 893 return IRP_FLOAT; 894 } 895 896 bool isAnyCallSitePosition() const { 897 switch (getPositionKind()) { 898 case IRPosition::IRP_CALL_SITE: 899 case IRPosition::IRP_CALL_SITE_RETURNED: 900 case IRPosition::IRP_CALL_SITE_ARGUMENT: 901 return true; 902 default: 903 return false; 904 } 905 } 906 907 /// Return true if the position is an argument or call site argument. 908 bool isArgumentPosition() const { 909 switch (getPositionKind()) { 910 case IRPosition::IRP_ARGUMENT: 911 case IRPosition::IRP_CALL_SITE_ARGUMENT: 912 return true; 913 default: 914 return false; 915 } 916 } 917 918 /// Return the same position without the call base context. 919 IRPosition stripCallBaseContext() const { 920 IRPosition Result = *this; 921 Result.CBContext = nullptr; 922 return Result; 923 } 924 925 /// Get the call base context from the position. 926 const CallBaseContext *getCallBaseContext() const { return CBContext; } 927 928 /// Check if the position has any call base context. 929 bool hasCallBaseContext() const { return CBContext != nullptr; } 930 931 /// Special DenseMap key values. 932 /// 933 ///{ 934 static const IRPosition EmptyKey; 935 static const IRPosition TombstoneKey; 936 ///} 937 938 /// Conversion into a void * to allow reuse of pointer hashing. 939 operator void *() const { return Enc.getOpaqueValue(); } 940 941 private: 942 /// Private constructor for special values only! 943 explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr) 944 : CBContext(CBContext) { 945 Enc.setFromOpaqueValue(Ptr); 946 } 947 948 /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK. 949 explicit IRPosition(Value &AnchorVal, Kind PK, 950 const CallBaseContext *CBContext = nullptr) 951 : CBContext(CBContext) { 952 switch (PK) { 953 case IRPosition::IRP_INVALID: 954 llvm_unreachable("Cannot create invalid IRP with an anchor value!"); 955 break; 956 case IRPosition::IRP_FLOAT: 957 // Special case for floating functions. 958 if (isa<Function>(AnchorVal) || isa<CallBase>(AnchorVal)) 959 Enc = {&AnchorVal, ENC_FLOATING_FUNCTION}; 960 else 961 Enc = {&AnchorVal, ENC_VALUE}; 962 break; 963 case IRPosition::IRP_FUNCTION: 964 case IRPosition::IRP_CALL_SITE: 965 Enc = {&AnchorVal, ENC_VALUE}; 966 break; 967 case IRPosition::IRP_RETURNED: 968 case IRPosition::IRP_CALL_SITE_RETURNED: 969 Enc = {&AnchorVal, ENC_RETURNED_VALUE}; 970 break; 971 case IRPosition::IRP_ARGUMENT: 972 Enc = {&AnchorVal, ENC_VALUE}; 973 break; 974 case IRPosition::IRP_CALL_SITE_ARGUMENT: 975 llvm_unreachable( 976 "Cannot create call site argument IRP with an anchor value!"); 977 break; 978 } 979 verify(); 980 } 981 982 /// Return the callee argument number of the associated value if it is an 983 /// argument or call site argument. See also `getCalleeArgNo` and 984 /// `getCallSiteArgNo`. 985 int getArgNo(bool CallbackCalleeArgIfApplicable) const { 986 if (CallbackCalleeArgIfApplicable) 987 if (Argument *Arg = getAssociatedArgument()) 988 return Arg->getArgNo(); 989 switch (getPositionKind()) { 990 case IRPosition::IRP_ARGUMENT: 991 return cast<Argument>(getAsValuePtr())->getArgNo(); 992 case IRPosition::IRP_CALL_SITE_ARGUMENT: { 993 Use &U = *getAsUsePtr(); 994 return cast<CallBase>(U.getUser())->getArgOperandNo(&U); 995 } 996 default: 997 return -1; 998 } 999 } 1000 1001 /// IRPosition for the use \p U. The position kind \p PK needs to be 1002 /// IRP_CALL_SITE_ARGUMENT, the anchor value is the user, the associated value 1003 /// the used value. 1004 explicit IRPosition(Use &U, Kind PK) { 1005 assert(PK == IRP_CALL_SITE_ARGUMENT && 1006 "Use constructor is for call site arguments only!"); 1007 Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE}; 1008 verify(); 1009 } 1010 1011 /// Verify internal invariants. 1012 void verify(); 1013 1014 /// Return the underlying pointer as Value *, valid for all positions but 1015 /// IRP_CALL_SITE_ARGUMENT. 1016 Value *getAsValuePtr() const { 1017 assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE && 1018 "Not a value pointer!"); 1019 return reinterpret_cast<Value *>(Enc.getPointer()); 1020 } 1021 1022 /// Return the underlying pointer as Use *, valid only for 1023 /// IRP_CALL_SITE_ARGUMENT positions. 1024 Use *getAsUsePtr() const { 1025 assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE && 1026 "Not a value pointer!"); 1027 return reinterpret_cast<Use *>(Enc.getPointer()); 1028 } 1029 1030 /// Return true if \p EncodingBits describe a returned or call site returned 1031 /// position. 1032 static bool isReturnPosition(char EncodingBits) { 1033 return EncodingBits == ENC_RETURNED_VALUE; 1034 } 1035 1036 /// Return true if the encoding bits describe a returned or call site returned 1037 /// position. 1038 bool isReturnPosition() const { return isReturnPosition(getEncodingBits()); } 1039 1040 /// The encoding of the IRPosition is a combination of a pointer and two 1041 /// encoding bits. The values of the encoding bits are defined in the enum 1042 /// below. The pointer is either a Value* (for the first three encoding bit 1043 /// combinations) or Use* (for ENC_CALL_SITE_ARGUMENT_USE). 1044 /// 1045 ///{ 1046 enum { 1047 ENC_VALUE = 0b00, 1048 ENC_RETURNED_VALUE = 0b01, 1049 ENC_FLOATING_FUNCTION = 0b10, 1050 ENC_CALL_SITE_ARGUMENT_USE = 0b11, 1051 }; 1052 1053 // Reserve the maximal amount of bits so there is no need to mask out the 1054 // remaining ones. We will not encode anything else in the pointer anyway. 1055 static constexpr int NumEncodingBits = 1056 PointerLikeTypeTraits<void *>::NumLowBitsAvailable; 1057 static_assert(NumEncodingBits >= 2, "At least two bits are required!"); 1058 1059 /// The pointer with the encoding bits. 1060 PointerIntPair<void *, NumEncodingBits, char> Enc; 1061 ///} 1062 1063 /// Call base context. Used for callsite specific analysis. 1064 const CallBaseContext *CBContext = nullptr; 1065 1066 /// Return the encoding bits. 1067 char getEncodingBits() const { return Enc.getInt(); } 1068 }; 1069 1070 /// Helper that allows IRPosition as a key in a DenseMap. 1071 template <> struct DenseMapInfo<IRPosition> { 1072 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; } 1073 static inline IRPosition getTombstoneKey() { 1074 return IRPosition::TombstoneKey; 1075 } 1076 static unsigned getHashValue(const IRPosition &IRP) { 1077 return (DenseMapInfo<void *>::getHashValue(IRP) << 4) ^ 1078 (DenseMapInfo<Value *>::getHashValue(IRP.getCallBaseContext())); 1079 } 1080 1081 static bool isEqual(const IRPosition &a, const IRPosition &b) { 1082 return a == b; 1083 } 1084 }; 1085 1086 /// A visitor class for IR positions. 1087 /// 1088 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming 1089 /// positions" wrt. attributes/information. Thus, if a piece of information 1090 /// holds for a subsuming position, it also holds for the position P. 1091 /// 1092 /// The subsuming positions always include the initial position and then, 1093 /// depending on the position kind, additionally the following ones: 1094 /// - for IRP_RETURNED: 1095 /// - the function (IRP_FUNCTION) 1096 /// - for IRP_ARGUMENT: 1097 /// - the function (IRP_FUNCTION) 1098 /// - for IRP_CALL_SITE: 1099 /// - the callee (IRP_FUNCTION), if known 1100 /// - for IRP_CALL_SITE_RETURNED: 1101 /// - the callee (IRP_RETURNED), if known 1102 /// - the call site (IRP_FUNCTION) 1103 /// - the callee (IRP_FUNCTION), if known 1104 /// - for IRP_CALL_SITE_ARGUMENT: 1105 /// - the argument of the callee (IRP_ARGUMENT), if known 1106 /// - the callee (IRP_FUNCTION), if known 1107 /// - the position the call site argument is associated with if it is not 1108 /// anchored to the call site, e.g., if it is an argument then the argument 1109 /// (IRP_ARGUMENT) 1110 class SubsumingPositionIterator { 1111 SmallVector<IRPosition, 4> IRPositions; 1112 using iterator = decltype(IRPositions)::iterator; 1113 1114 public: 1115 SubsumingPositionIterator(const IRPosition &IRP); 1116 iterator begin() { return IRPositions.begin(); } 1117 iterator end() { return IRPositions.end(); } 1118 }; 1119 1120 /// Wrapper for FunctionAnalysisManager. 1121 struct AnalysisGetter { 1122 // The client may be running the old pass manager, in which case, we need to 1123 // map the requested Analysis to its equivalent wrapper in the old pass 1124 // manager. The scheme implemented here does not require every Analysis to be 1125 // updated. Only those new analyses that the client cares about in the old 1126 // pass manager need to expose a LegacyWrapper type, and that wrapper should 1127 // support a getResult() method that matches the new Analysis. 1128 // 1129 // We need SFINAE to check for the LegacyWrapper, but function templates don't 1130 // allow partial specialization, which is needed in this case. So instead, we 1131 // use a constexpr bool to perform the SFINAE, and then use this information 1132 // inside the function template. 1133 template <typename, typename = void> 1134 static constexpr bool HasLegacyWrapper = false; 1135 1136 template <typename Analysis> 1137 typename Analysis::Result *getAnalysis(const Function &F, 1138 bool RequestCachedOnly = false) { 1139 if (!LegacyPass && !FAM) 1140 return nullptr; 1141 if (FAM) { 1142 if (CachedOnly || RequestCachedOnly) 1143 return FAM->getCachedResult<Analysis>(const_cast<Function &>(F)); 1144 return &FAM->getResult<Analysis>(const_cast<Function &>(F)); 1145 } 1146 if constexpr (HasLegacyWrapper<Analysis>) { 1147 if (!CachedOnly && !RequestCachedOnly) 1148 return &LegacyPass 1149 ->getAnalysis<typename Analysis::LegacyWrapper>( 1150 const_cast<Function &>(F)) 1151 .getResult(); 1152 if (auto *P = 1153 LegacyPass 1154 ->getAnalysisIfAvailable<typename Analysis::LegacyWrapper>()) 1155 return &P->getResult(); 1156 } 1157 return nullptr; 1158 } 1159 1160 /// Invalidates the analyses. Valid only when using the new pass manager. 1161 void invalidateAnalyses() { 1162 assert(FAM && "Can only be used from the new PM!"); 1163 FAM->clear(); 1164 } 1165 1166 AnalysisGetter(FunctionAnalysisManager &FAM, bool CachedOnly = false) 1167 : FAM(&FAM), CachedOnly(CachedOnly) {} 1168 AnalysisGetter(Pass *P, bool CachedOnly = false) 1169 : LegacyPass(P), CachedOnly(CachedOnly) {} 1170 AnalysisGetter() = default; 1171 1172 private: 1173 FunctionAnalysisManager *FAM = nullptr; 1174 Pass *LegacyPass = nullptr; 1175 1176 /// If \p CachedOnly is true, no pass is created, just existing results are 1177 /// used. Also available per request. 1178 bool CachedOnly = false; 1179 }; 1180 1181 template <typename Analysis> 1182 constexpr bool AnalysisGetter::HasLegacyWrapper< 1183 Analysis, std::void_t<typename Analysis::LegacyWrapper>> = true; 1184 1185 /// Data structure to hold cached (LLVM-IR) information. 1186 /// 1187 /// All attributes are given an InformationCache object at creation time to 1188 /// avoid inspection of the IR by all of them individually. This default 1189 /// InformationCache will hold information required by 'default' attributes, 1190 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..) 1191 /// is called. 1192 /// 1193 /// If custom abstract attributes, registered manually through 1194 /// Attributor::registerAA(...), need more information, especially if it is not 1195 /// reusable, it is advised to inherit from the InformationCache and cast the 1196 /// instance down in the abstract attributes. 1197 struct InformationCache { 1198 InformationCache(const Module &M, AnalysisGetter &AG, 1199 BumpPtrAllocator &Allocator, SetVector<Function *> *CGSCC, 1200 bool UseExplorer = true) 1201 : CGSCC(CGSCC), DL(M.getDataLayout()), Allocator(Allocator), AG(AG), 1202 TargetTriple(M.getTargetTriple()) { 1203 if (UseExplorer) 1204 Explorer = new (Allocator) MustBeExecutedContextExplorer( 1205 /* ExploreInterBlock */ true, /* ExploreCFGForward */ true, 1206 /* ExploreCFGBackward */ true, 1207 /* LIGetter */ 1208 [&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); }, 1209 /* DTGetter */ 1210 [&](const Function &F) { 1211 return AG.getAnalysis<DominatorTreeAnalysis>(F); 1212 }, 1213 /* PDTGetter */ 1214 [&](const Function &F) { 1215 return AG.getAnalysis<PostDominatorTreeAnalysis>(F); 1216 }); 1217 } 1218 1219 ~InformationCache() { 1220 // The FunctionInfo objects are allocated via a BumpPtrAllocator, we call 1221 // the destructor manually. 1222 for (auto &It : FuncInfoMap) 1223 It.getSecond()->~FunctionInfo(); 1224 // Same is true for the instruction exclusions sets. 1225 using AA::InstExclusionSetTy; 1226 for (auto *BES : BESets) 1227 BES->~InstExclusionSetTy(); 1228 if (Explorer) 1229 Explorer->~MustBeExecutedContextExplorer(); 1230 } 1231 1232 /// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is 1233 /// true, constant expression users are not given to \p CB but their uses are 1234 /// traversed transitively. 1235 template <typename CBTy> 1236 static void foreachUse(Function &F, CBTy CB, 1237 bool LookThroughConstantExprUses = true) { 1238 SmallVector<Use *, 8> Worklist(make_pointer_range(F.uses())); 1239 1240 for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) { 1241 Use &U = *Worklist[Idx]; 1242 1243 // Allow use in constant bitcasts and simply look through them. 1244 if (LookThroughConstantExprUses && isa<ConstantExpr>(U.getUser())) { 1245 for (Use &CEU : cast<ConstantExpr>(U.getUser())->uses()) 1246 Worklist.push_back(&CEU); 1247 continue; 1248 } 1249 1250 CB(U); 1251 } 1252 } 1253 1254 /// The CG-SCC the pass is run on, or nullptr if it is a module pass. 1255 const SetVector<Function *> *const CGSCC = nullptr; 1256 1257 /// A vector type to hold instructions. 1258 using InstructionVectorTy = SmallVector<Instruction *, 8>; 1259 1260 /// A map type from opcodes to instructions with this opcode. 1261 using OpcodeInstMapTy = DenseMap<unsigned, InstructionVectorTy *>; 1262 1263 /// Return the map that relates "interesting" opcodes with all instructions 1264 /// with that opcode in \p F. 1265 OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) { 1266 return getFunctionInfo(F).OpcodeInstMap; 1267 } 1268 1269 /// Return the instructions in \p F that may read or write memory. 1270 InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) { 1271 return getFunctionInfo(F).RWInsts; 1272 } 1273 1274 /// Return MustBeExecutedContextExplorer 1275 MustBeExecutedContextExplorer *getMustBeExecutedContextExplorer() { 1276 return Explorer; 1277 } 1278 1279 /// Return TargetLibraryInfo for function \p F. 1280 TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) { 1281 return AG.getAnalysis<TargetLibraryAnalysis>(F); 1282 } 1283 1284 /// Return true if \p Arg is involved in a must-tail call, thus the argument 1285 /// of the caller or callee. 1286 bool isInvolvedInMustTailCall(const Argument &Arg) { 1287 FunctionInfo &FI = getFunctionInfo(*Arg.getParent()); 1288 return FI.CalledViaMustTail || FI.ContainsMustTailCall; 1289 } 1290 1291 bool isOnlyUsedByAssume(const Instruction &I) const { 1292 return AssumeOnlyValues.contains(&I); 1293 } 1294 1295 /// Invalidates the cached analyses. Valid only when using the new pass 1296 /// manager. 1297 void invalidateAnalyses() { AG.invalidateAnalyses(); } 1298 1299 /// Return the analysis result from a pass \p AP for function \p F. 1300 template <typename AP> 1301 typename AP::Result *getAnalysisResultForFunction(const Function &F, 1302 bool CachedOnly = false) { 1303 return AG.getAnalysis<AP>(F, CachedOnly); 1304 } 1305 1306 /// Return datalayout used in the module. 1307 const DataLayout &getDL() { return DL; } 1308 1309 /// Return the map conaining all the knowledge we have from `llvm.assume`s. 1310 const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; } 1311 1312 /// Given \p BES, return a uniqued version. 1313 const AA::InstExclusionSetTy * 1314 getOrCreateUniqueBlockExecutionSet(const AA::InstExclusionSetTy *BES) { 1315 auto It = BESets.find(BES); 1316 if (It != BESets.end()) 1317 return *It; 1318 auto *UniqueBES = new (Allocator) AA::InstExclusionSetTy(*BES); 1319 bool Success = BESets.insert(UniqueBES).second; 1320 (void)Success; 1321 assert(Success && "Expected only new entries to be added"); 1322 return UniqueBES; 1323 } 1324 1325 /// Return true if the stack (llvm::Alloca) can be accessed by other threads. 1326 bool stackIsAccessibleByOtherThreads() { return !targetIsGPU(); } 1327 1328 /// Return true if the target is a GPU. 1329 bool targetIsGPU() { 1330 return TargetTriple.isAMDGPU() || TargetTriple.isNVPTX(); 1331 } 1332 1333 /// Return all functions that might be called indirectly, only valid for 1334 /// closed world modules (see isClosedWorldModule). 1335 const ArrayRef<Function *> 1336 getIndirectlyCallableFunctions(Attributor &A) const; 1337 1338 private: 1339 struct FunctionInfo { 1340 ~FunctionInfo(); 1341 1342 /// A nested map that remembers all instructions in a function with a 1343 /// certain instruction opcode (Instruction::getOpcode()). 1344 OpcodeInstMapTy OpcodeInstMap; 1345 1346 /// A map from functions to their instructions that may read or write 1347 /// memory. 1348 InstructionVectorTy RWInsts; 1349 1350 /// Function is called by a `musttail` call. 1351 bool CalledViaMustTail; 1352 1353 /// Function contains a `musttail` call. 1354 bool ContainsMustTailCall; 1355 }; 1356 1357 /// A map type from functions to informatio about it. 1358 DenseMap<const Function *, FunctionInfo *> FuncInfoMap; 1359 1360 /// Return information about the function \p F, potentially by creating it. 1361 FunctionInfo &getFunctionInfo(const Function &F) { 1362 FunctionInfo *&FI = FuncInfoMap[&F]; 1363 if (!FI) { 1364 FI = new (Allocator) FunctionInfo(); 1365 initializeInformationCache(F, *FI); 1366 } 1367 return *FI; 1368 } 1369 1370 /// Vector of functions that might be callable indirectly, i.a., via a 1371 /// function pointer. 1372 SmallVector<Function *> IndirectlyCallableFunctions; 1373 1374 /// Initialize the function information cache \p FI for the function \p F. 1375 /// 1376 /// This method needs to be called for all function that might be looked at 1377 /// through the information cache interface *prior* to looking at them. 1378 void initializeInformationCache(const Function &F, FunctionInfo &FI); 1379 1380 /// The datalayout used in the module. 1381 const DataLayout &DL; 1382 1383 /// The allocator used to allocate memory, e.g. for `FunctionInfo`s. 1384 BumpPtrAllocator &Allocator; 1385 1386 /// MustBeExecutedContextExplorer 1387 MustBeExecutedContextExplorer *Explorer = nullptr; 1388 1389 /// A map with knowledge retained in `llvm.assume` instructions. 1390 RetainedKnowledgeMap KnowledgeMap; 1391 1392 /// A container for all instructions that are only used by `llvm.assume`. 1393 SetVector<const Instruction *> AssumeOnlyValues; 1394 1395 /// Cache for block sets to allow reuse. 1396 DenseSet<const AA::InstExclusionSetTy *> BESets; 1397 1398 /// Getters for analysis. 1399 AnalysisGetter &AG; 1400 1401 /// Set of inlineable functions 1402 SmallPtrSet<const Function *, 8> InlineableFunctions; 1403 1404 /// The triple describing the target machine. 1405 Triple TargetTriple; 1406 1407 /// Give the Attributor access to the members so 1408 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them. 1409 friend struct Attributor; 1410 }; 1411 1412 /// Configuration for the Attributor. 1413 struct AttributorConfig { 1414 1415 AttributorConfig(CallGraphUpdater &CGUpdater) : CGUpdater(CGUpdater) {} 1416 1417 /// Is the user of the Attributor a module pass or not. This determines what 1418 /// IR we can look at and modify. If it is a module pass we might deduce facts 1419 /// outside the initial function set and modify functions outside that set, 1420 /// but only as part of the optimization of the functions in the initial 1421 /// function set. For CGSCC passes we can look at the IR of the module slice 1422 /// but never run any deduction, or perform any modification, outside the 1423 /// initial function set (which we assume is the SCC). 1424 bool IsModulePass = true; 1425 1426 /// Flag to determine if we can delete functions or keep dead ones around. 1427 bool DeleteFns = true; 1428 1429 /// Flag to determine if we rewrite function signatures. 1430 bool RewriteSignatures = true; 1431 1432 /// Flag to determine if we want to initialize all default AAs for an internal 1433 /// function marked live. See also: InitializationCallback> 1434 bool DefaultInitializeLiveInternals = true; 1435 1436 /// Flag to determine if we should skip all liveness checks early on. 1437 bool UseLiveness = true; 1438 1439 /// Flag to indicate if the entire world is contained in this module, that 1440 /// is, no outside functions exist. 1441 bool IsClosedWorldModule = false; 1442 1443 /// Callback function to be invoked on internal functions marked live. 1444 std::function<void(Attributor &A, const Function &F)> InitializationCallback = 1445 nullptr; 1446 1447 /// Callback function to determine if an indirect call targets should be made 1448 /// direct call targets (with an if-cascade). 1449 std::function<bool(Attributor &A, const AbstractAttribute &AA, CallBase &CB, 1450 Function &AssummedCallee)> 1451 IndirectCalleeSpecializationCallback = nullptr; 1452 1453 /// Helper to update an underlying call graph and to delete functions. 1454 CallGraphUpdater &CGUpdater; 1455 1456 /// If not null, a set limiting the attribute opportunities. 1457 DenseSet<const char *> *Allowed = nullptr; 1458 1459 /// Maximum number of iterations to run until fixpoint. 1460 std::optional<unsigned> MaxFixpointIterations; 1461 1462 /// A callback function that returns an ORE object from a Function pointer. 1463 ///{ 1464 using OptimizationRemarkGetter = 1465 function_ref<OptimizationRemarkEmitter &(Function *)>; 1466 OptimizationRemarkGetter OREGetter = nullptr; 1467 ///} 1468 1469 /// The name of the pass running the attributor, used to emit remarks. 1470 const char *PassName = nullptr; 1471 1472 using IPOAmendableCBTy = function_ref<bool(const Function &F)>; 1473 IPOAmendableCBTy IPOAmendableCB; 1474 }; 1475 1476 /// A debug counter to limit the number of AAs created. 1477 DEBUG_COUNTER(NumAbstractAttributes, "num-abstract-attributes", 1478 "How many AAs should be initialized"); 1479 1480 /// The fixpoint analysis framework that orchestrates the attribute deduction. 1481 /// 1482 /// The Attributor provides a general abstract analysis framework (guided 1483 /// fixpoint iteration) as well as helper functions for the deduction of 1484 /// (LLVM-IR) attributes. However, also other code properties can be deduced, 1485 /// propagated, and ultimately manifested through the Attributor framework. This 1486 /// is particularly useful if these properties interact with attributes and a 1487 /// co-scheduled deduction allows to improve the solution. Even if not, thus if 1488 /// attributes/properties are completely isolated, they should use the 1489 /// Attributor framework to reduce the number of fixpoint iteration frameworks 1490 /// in the code base. Note that the Attributor design makes sure that isolated 1491 /// attributes are not impacted, in any way, by others derived at the same time 1492 /// if there is no cross-reasoning performed. 1493 /// 1494 /// The public facing interface of the Attributor is kept simple and basically 1495 /// allows abstract attributes to one thing, query abstract attributes 1496 /// in-flight. There are two reasons to do this: 1497 /// a) The optimistic state of one abstract attribute can justify an 1498 /// optimistic state of another, allowing to framework to end up with an 1499 /// optimistic (=best possible) fixpoint instead of one based solely on 1500 /// information in the IR. 1501 /// b) This avoids reimplementing various kinds of lookups, e.g., to check 1502 /// for existing IR attributes, in favor of a single lookups interface 1503 /// provided by an abstract attribute subclass. 1504 /// 1505 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are 1506 /// described in the file comment. 1507 struct Attributor { 1508 1509 /// Constructor 1510 /// 1511 /// \param Functions The set of functions we are deriving attributes for. 1512 /// \param InfoCache Cache to hold various information accessible for 1513 /// the abstract attributes. 1514 /// \param Configuration The Attributor configuration which determines what 1515 /// generic features to use. 1516 Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache, 1517 AttributorConfig Configuration); 1518 1519 ~Attributor(); 1520 1521 /// Run the analyses until a fixpoint is reached or enforced (timeout). 1522 /// 1523 /// The attributes registered with this Attributor can be used after as long 1524 /// as the Attributor is not destroyed (it owns the attributes now). 1525 /// 1526 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED. 1527 ChangeStatus run(); 1528 1529 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While 1530 /// no abstract attribute is found equivalent positions are checked, see 1531 /// SubsumingPositionIterator. Thus, the returned abstract attribute 1532 /// might be anchored at a different position, e.g., the callee if \p IRP is a 1533 /// call base. 1534 /// 1535 /// This method is the only (supported) way an abstract attribute can retrieve 1536 /// information from another abstract attribute. As an example, take an 1537 /// abstract attribute that determines the memory access behavior for a 1538 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the 1539 /// most optimistic information for other abstract attributes in-flight, e.g. 1540 /// the one reasoning about the "captured" state for the argument or the one 1541 /// reasoning on the memory access behavior of the function as a whole. 1542 /// 1543 /// If the DepClass enum is set to `DepClassTy::None` the dependence from 1544 /// \p QueryingAA to the return abstract attribute is not automatically 1545 /// recorded. This should only be used if the caller will record the 1546 /// dependence explicitly if necessary, thus if it the returned abstract 1547 /// attribute is used for reasoning. To record the dependences explicitly use 1548 /// the `Attributor::recordDependence` method. 1549 template <typename AAType> 1550 const AAType *getAAFor(const AbstractAttribute &QueryingAA, 1551 const IRPosition &IRP, DepClassTy DepClass) { 1552 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass, 1553 /* ForceUpdate */ false); 1554 } 1555 1556 /// The version of getAAFor that allows to omit a querying abstract 1557 /// attribute. Using this after Attributor started running is restricted to 1558 /// only the Attributor itself. Initial seeding of AAs can be done via this 1559 /// function. 1560 /// NOTE: ForceUpdate is ignored in any stage other than the update stage. 1561 template <typename AAType> 1562 const AAType *getOrCreateAAFor(IRPosition IRP, 1563 const AbstractAttribute *QueryingAA, 1564 DepClassTy DepClass, bool ForceUpdate = false, 1565 bool UpdateAfterInit = true) { 1566 if (!shouldPropagateCallBaseContext(IRP)) 1567 IRP = IRP.stripCallBaseContext(); 1568 1569 if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass, 1570 /* AllowInvalidState */ true)) { 1571 if (ForceUpdate && Phase == AttributorPhase::UPDATE) 1572 updateAA(*AAPtr); 1573 return AAPtr; 1574 } 1575 1576 bool ShouldUpdateAA; 1577 if (!shouldInitialize<AAType>(IRP, ShouldUpdateAA)) 1578 return nullptr; 1579 1580 if (!DebugCounter::shouldExecute(NumAbstractAttributes)) 1581 return nullptr; 1582 1583 // No matching attribute found, create one. 1584 // Use the static create method. 1585 auto &AA = AAType::createForPosition(IRP, *this); 1586 1587 // Always register a new attribute to make sure we clean up the allocated 1588 // memory properly. 1589 registerAA(AA); 1590 1591 // If we are currenty seeding attributes, enforce seeding rules. 1592 if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) { 1593 AA.getState().indicatePessimisticFixpoint(); 1594 return &AA; 1595 } 1596 1597 // Bootstrap the new attribute with an initial update to propagate 1598 // information, e.g., function -> call site. 1599 { 1600 TimeTraceScope TimeScope("initialize", [&]() { 1601 return AA.getName() + 1602 std::to_string(AA.getIRPosition().getPositionKind()); 1603 }); 1604 ++InitializationChainLength; 1605 AA.initialize(*this); 1606 --InitializationChainLength; 1607 } 1608 1609 if (!ShouldUpdateAA) { 1610 AA.getState().indicatePessimisticFixpoint(); 1611 return &AA; 1612 } 1613 1614 // Allow seeded attributes to declare dependencies. 1615 // Remember the seeding state. 1616 if (UpdateAfterInit) { 1617 AttributorPhase OldPhase = Phase; 1618 Phase = AttributorPhase::UPDATE; 1619 1620 updateAA(AA); 1621 1622 Phase = OldPhase; 1623 } 1624 1625 if (QueryingAA && AA.getState().isValidState()) 1626 recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA), 1627 DepClass); 1628 return &AA; 1629 } 1630 1631 template <typename AAType> 1632 const AAType *getOrCreateAAFor(const IRPosition &IRP) { 1633 return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr, 1634 DepClassTy::NONE); 1635 } 1636 1637 /// Return the attribute of \p AAType for \p IRP if existing and valid. This 1638 /// also allows non-AA users lookup. 1639 template <typename AAType> 1640 AAType *lookupAAFor(const IRPosition &IRP, 1641 const AbstractAttribute *QueryingAA = nullptr, 1642 DepClassTy DepClass = DepClassTy::OPTIONAL, 1643 bool AllowInvalidState = false) { 1644 static_assert(std::is_base_of<AbstractAttribute, AAType>::value, 1645 "Cannot query an attribute with a type not derived from " 1646 "'AbstractAttribute'!"); 1647 // Lookup the abstract attribute of type AAType. If found, return it after 1648 // registering a dependence of QueryingAA on the one returned attribute. 1649 AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP}); 1650 if (!AAPtr) 1651 return nullptr; 1652 1653 AAType *AA = static_cast<AAType *>(AAPtr); 1654 1655 // Do not register a dependence on an attribute with an invalid state. 1656 if (DepClass != DepClassTy::NONE && QueryingAA && 1657 AA->getState().isValidState()) 1658 recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA), 1659 DepClass); 1660 1661 // Return nullptr if this attribute has an invalid state. 1662 if (!AllowInvalidState && !AA->getState().isValidState()) 1663 return nullptr; 1664 return AA; 1665 } 1666 1667 /// Allows a query AA to request an update if a new query was received. 1668 void registerForUpdate(AbstractAttribute &AA); 1669 1670 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if 1671 /// \p FromAA changes \p ToAA should be updated as well. 1672 /// 1673 /// This method should be used in conjunction with the `getAAFor` method and 1674 /// with the DepClass enum passed to the method set to None. This can 1675 /// be beneficial to avoid false dependences but it requires the users of 1676 /// `getAAFor` to explicitly record true dependences through this method. 1677 /// The \p DepClass flag indicates if the dependence is striclty necessary. 1678 /// That means for required dependences, if \p FromAA changes to an invalid 1679 /// state, \p ToAA can be moved to a pessimistic fixpoint because it required 1680 /// information from \p FromAA but none are available anymore. 1681 void recordDependence(const AbstractAttribute &FromAA, 1682 const AbstractAttribute &ToAA, DepClassTy DepClass); 1683 1684 /// Introduce a new abstract attribute into the fixpoint analysis. 1685 /// 1686 /// Note that ownership of the attribute is given to the Attributor. It will 1687 /// invoke delete for the Attributor on destruction of the Attributor. 1688 /// 1689 /// Attributes are identified by their IR position (AAType::getIRPosition()) 1690 /// and the address of their static member (see AAType::ID). 1691 template <typename AAType> AAType ®isterAA(AAType &AA) { 1692 static_assert(std::is_base_of<AbstractAttribute, AAType>::value, 1693 "Cannot register an attribute with a type not derived from " 1694 "'AbstractAttribute'!"); 1695 // Put the attribute in the lookup map structure and the container we use to 1696 // keep track of all attributes. 1697 const IRPosition &IRP = AA.getIRPosition(); 1698 AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}]; 1699 1700 assert(!AAPtr && "Attribute already in map!"); 1701 AAPtr = &AA; 1702 1703 // Register AA with the synthetic root only before the manifest stage. 1704 if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE) 1705 DG.SyntheticRoot.Deps.insert( 1706 AADepGraphNode::DepTy(&AA, unsigned(DepClassTy::REQUIRED))); 1707 1708 return AA; 1709 } 1710 1711 /// Return the internal information cache. 1712 InformationCache &getInfoCache() { return InfoCache; } 1713 1714 /// Return true if this is a module pass, false otherwise. 1715 bool isModulePass() const { return Configuration.IsModulePass; } 1716 1717 /// Return true if we should specialize the call site \b CB for the potential 1718 /// callee \p Fn. 1719 bool shouldSpecializeCallSiteForCallee(const AbstractAttribute &AA, 1720 CallBase &CB, Function &Callee) { 1721 return Configuration.IndirectCalleeSpecializationCallback 1722 ? Configuration.IndirectCalleeSpecializationCallback(*this, AA, 1723 CB, Callee) 1724 : true; 1725 } 1726 1727 /// Return true if the module contains the whole world, thus, no outside 1728 /// functions exist. 1729 bool isClosedWorldModule() const; 1730 1731 /// Return true if we derive attributes for \p Fn 1732 bool isRunOn(Function &Fn) const { return isRunOn(&Fn); } 1733 bool isRunOn(Function *Fn) const { 1734 return Functions.empty() || Functions.count(Fn); 1735 } 1736 1737 template <typename AAType> bool shouldUpdateAA(const IRPosition &IRP) { 1738 // If this is queried in the manifest stage, we force the AA to indicate 1739 // pessimistic fixpoint immediately. 1740 if (Phase == AttributorPhase::MANIFEST || Phase == AttributorPhase::CLEANUP) 1741 return false; 1742 1743 Function *AssociatedFn = IRP.getAssociatedFunction(); 1744 1745 if (IRP.isAnyCallSitePosition()) { 1746 // Check if we require a callee but there is none. 1747 if (!AssociatedFn && AAType::requiresCalleeForCallBase()) 1748 return false; 1749 1750 // Check if we require non-asm but it is inline asm. 1751 if (AAType::requiresNonAsmForCallBase() && 1752 cast<CallBase>(IRP.getAnchorValue()).isInlineAsm()) 1753 return false; 1754 } 1755 1756 // Check if we require a calles but we can't see all. 1757 if (AAType::requiresCallersForArgOrFunction()) 1758 if (IRP.getPositionKind() == IRPosition::IRP_FUNCTION || 1759 IRP.getPositionKind() == IRPosition::IRP_ARGUMENT) 1760 if (!AssociatedFn->hasLocalLinkage()) 1761 return false; 1762 1763 if (!AAType::isValidIRPositionForUpdate(*this, IRP)) 1764 return false; 1765 1766 // We update only AAs associated with functions in the Functions set or 1767 // call sites of them. 1768 return (!AssociatedFn || isModulePass() || isRunOn(AssociatedFn) || 1769 isRunOn(IRP.getAnchorScope())); 1770 } 1771 1772 template <typename AAType> 1773 bool shouldInitialize(const IRPosition &IRP, bool &ShouldUpdateAA) { 1774 if (!AAType::isValidIRPositionForInit(*this, IRP)) 1775 return false; 1776 1777 if (Configuration.Allowed && !Configuration.Allowed->count(&AAType::ID)) 1778 return false; 1779 1780 // For now we skip anything in naked and optnone functions. 1781 const Function *AnchorFn = IRP.getAnchorScope(); 1782 if (AnchorFn && (AnchorFn->hasFnAttribute(Attribute::Naked) || 1783 AnchorFn->hasFnAttribute(Attribute::OptimizeNone))) 1784 return false; 1785 1786 // Avoid too many nested initializations to prevent a stack overflow. 1787 if (InitializationChainLength > MaxInitializationChainLength) 1788 return false; 1789 1790 ShouldUpdateAA = shouldUpdateAA<AAType>(IRP); 1791 1792 return !AAType::hasTrivialInitializer() || ShouldUpdateAA; 1793 } 1794 1795 /// Determine opportunities to derive 'default' attributes in \p F and create 1796 /// abstract attribute objects for them. 1797 /// 1798 /// \param F The function that is checked for attribute opportunities. 1799 /// 1800 /// Note that abstract attribute instances are generally created even if the 1801 /// IR already contains the information they would deduce. The most important 1802 /// reason for this is the single interface, the one of the abstract attribute 1803 /// instance, which can be queried without the need to look at the IR in 1804 /// various places. 1805 void identifyDefaultAbstractAttributes(Function &F); 1806 1807 /// Determine whether the function \p F is IPO amendable 1808 /// 1809 /// If a function is exactly defined or it has alwaysinline attribute 1810 /// and is viable to be inlined, we say it is IPO amendable 1811 bool isFunctionIPOAmendable(const Function &F) { 1812 return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F) || 1813 (Configuration.IPOAmendableCB && Configuration.IPOAmendableCB(F)); 1814 } 1815 1816 /// Mark the internal function \p F as live. 1817 /// 1818 /// This will trigger the identification and initialization of attributes for 1819 /// \p F. 1820 void markLiveInternalFunction(const Function &F) { 1821 assert(F.hasLocalLinkage() && 1822 "Only local linkage is assumed dead initially."); 1823 1824 if (Configuration.DefaultInitializeLiveInternals) 1825 identifyDefaultAbstractAttributes(const_cast<Function &>(F)); 1826 if (Configuration.InitializationCallback) 1827 Configuration.InitializationCallback(*this, F); 1828 } 1829 1830 /// Helper function to remove callsite. 1831 void removeCallSite(CallInst *CI) { 1832 if (!CI) 1833 return; 1834 1835 Configuration.CGUpdater.removeCallSite(*CI); 1836 } 1837 1838 /// Record that \p U is to be replaces with \p NV after information was 1839 /// manifested. This also triggers deletion of trivially dead istructions. 1840 bool changeUseAfterManifest(Use &U, Value &NV) { 1841 Value *&V = ToBeChangedUses[&U]; 1842 if (V && (V->stripPointerCasts() == NV.stripPointerCasts() || 1843 isa_and_nonnull<UndefValue>(V))) 1844 return false; 1845 assert((!V || V == &NV || isa<UndefValue>(NV)) && 1846 "Use was registered twice for replacement with different values!"); 1847 V = &NV; 1848 return true; 1849 } 1850 1851 /// Helper function to replace all uses associated with \p IRP with \p NV. 1852 /// Return true if there is any change. The flag \p ChangeDroppable indicates 1853 /// if dropppable uses should be changed too. 1854 bool changeAfterManifest(const IRPosition IRP, Value &NV, 1855 bool ChangeDroppable = true) { 1856 if (IRP.getPositionKind() == IRPosition::IRP_CALL_SITE_ARGUMENT) { 1857 auto *CB = cast<CallBase>(IRP.getCtxI()); 1858 return changeUseAfterManifest( 1859 CB->getArgOperandUse(IRP.getCallSiteArgNo()), NV); 1860 } 1861 Value &V = IRP.getAssociatedValue(); 1862 auto &Entry = ToBeChangedValues[&V]; 1863 Value *CurNV = get<0>(Entry); 1864 if (CurNV && (CurNV->stripPointerCasts() == NV.stripPointerCasts() || 1865 isa<UndefValue>(CurNV))) 1866 return false; 1867 assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) && 1868 "Value replacement was registered twice with different values!"); 1869 Entry = {&NV, ChangeDroppable}; 1870 return true; 1871 } 1872 1873 /// Record that \p I is to be replaced with `unreachable` after information 1874 /// was manifested. 1875 void changeToUnreachableAfterManifest(Instruction *I) { 1876 ToBeChangedToUnreachableInsts.insert(I); 1877 } 1878 1879 /// Record that \p II has at least one dead successor block. This information 1880 /// is used, e.g., to replace \p II with a call, after information was 1881 /// manifested. 1882 void registerInvokeWithDeadSuccessor(InvokeInst &II) { 1883 InvokeWithDeadSuccessor.insert(&II); 1884 } 1885 1886 /// Record that \p I is deleted after information was manifested. This also 1887 /// triggers deletion of trivially dead istructions. 1888 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); } 1889 1890 /// Record that \p BB is deleted after information was manifested. This also 1891 /// triggers deletion of trivially dead istructions. 1892 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); } 1893 1894 // Record that \p BB is added during the manifest of an AA. Added basic blocks 1895 // are preserved in the IR. 1896 void registerManifestAddedBasicBlock(BasicBlock &BB) { 1897 ManifestAddedBlocks.insert(&BB); 1898 } 1899 1900 /// Record that \p F is deleted after information was manifested. 1901 void deleteAfterManifest(Function &F) { 1902 if (Configuration.DeleteFns) 1903 ToBeDeletedFunctions.insert(&F); 1904 } 1905 1906 /// Return the attributes of kind \p AK existing in the IR as operand bundles 1907 /// of an llvm.assume. 1908 bool getAttrsFromAssumes(const IRPosition &IRP, Attribute::AttrKind AK, 1909 SmallVectorImpl<Attribute> &Attrs); 1910 1911 /// Return true if any kind in \p AKs existing in the IR at a position that 1912 /// will affect this one. See also getAttrs(...). 1913 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions, 1914 /// e.g., the function position if this is an 1915 /// argument position, should be ignored. 1916 bool hasAttr(const IRPosition &IRP, ArrayRef<Attribute::AttrKind> AKs, 1917 bool IgnoreSubsumingPositions = false, 1918 Attribute::AttrKind ImpliedAttributeKind = Attribute::None); 1919 1920 /// Return the attributes of any kind in \p AKs existing in the IR at a 1921 /// position that will affect this one. While each position can only have a 1922 /// single attribute of any kind in \p AKs, there are "subsuming" positions 1923 /// that could have an attribute as well. This method returns all attributes 1924 /// found in \p Attrs. 1925 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions, 1926 /// e.g., the function position if this is an 1927 /// argument position, should be ignored. 1928 void getAttrs(const IRPosition &IRP, ArrayRef<Attribute::AttrKind> AKs, 1929 SmallVectorImpl<Attribute> &Attrs, 1930 bool IgnoreSubsumingPositions = false); 1931 1932 /// Remove all \p AttrKinds attached to \p IRP. 1933 ChangeStatus removeAttrs(const IRPosition &IRP, 1934 ArrayRef<Attribute::AttrKind> AttrKinds); 1935 ChangeStatus removeAttrs(const IRPosition &IRP, ArrayRef<StringRef> Attrs); 1936 1937 /// Attach \p DeducedAttrs to \p IRP, if \p ForceReplace is set we do this 1938 /// even if the same attribute kind was already present. 1939 ChangeStatus manifestAttrs(const IRPosition &IRP, 1940 ArrayRef<Attribute> DeducedAttrs, 1941 bool ForceReplace = false); 1942 1943 private: 1944 /// Helper to check \p Attrs for \p AK, if not found, check if \p 1945 /// AAType::isImpliedByIR is true, and if not, create AAType for \p IRP. 1946 template <Attribute::AttrKind AK, typename AAType> 1947 void checkAndQueryIRAttr(const IRPosition &IRP, AttributeSet Attrs); 1948 1949 /// Helper to apply \p CB on all attributes of type \p AttrDescs of \p IRP. 1950 template <typename DescTy> 1951 ChangeStatus updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs, 1952 function_ref<bool(const DescTy &, AttributeSet, 1953 AttributeMask &, AttrBuilder &)> 1954 CB); 1955 1956 /// Mapping from functions/call sites to their attributes. 1957 DenseMap<Value *, AttributeList> AttrsMap; 1958 1959 public: 1960 /// If \p IRP is assumed to be a constant, return it, if it is unclear yet, 1961 /// return std::nullopt, otherwise return `nullptr`. 1962 std::optional<Constant *> getAssumedConstant(const IRPosition &IRP, 1963 const AbstractAttribute &AA, 1964 bool &UsedAssumedInformation); 1965 std::optional<Constant *> getAssumedConstant(const Value &V, 1966 const AbstractAttribute &AA, 1967 bool &UsedAssumedInformation) { 1968 return getAssumedConstant(IRPosition::value(V), AA, UsedAssumedInformation); 1969 } 1970 1971 /// If \p V is assumed simplified, return it, if it is unclear yet, 1972 /// return std::nullopt, otherwise return `nullptr`. 1973 std::optional<Value *> getAssumedSimplified(const IRPosition &IRP, 1974 const AbstractAttribute &AA, 1975 bool &UsedAssumedInformation, 1976 AA::ValueScope S) { 1977 return getAssumedSimplified(IRP, &AA, UsedAssumedInformation, S); 1978 } 1979 std::optional<Value *> getAssumedSimplified(const Value &V, 1980 const AbstractAttribute &AA, 1981 bool &UsedAssumedInformation, 1982 AA::ValueScope S) { 1983 return getAssumedSimplified(IRPosition::value(V), AA, 1984 UsedAssumedInformation, S); 1985 } 1986 1987 /// If \p V is assumed simplified, return it, if it is unclear yet, 1988 /// return std::nullopt, otherwise return `nullptr`. Same as the public 1989 /// version except that it can be used without recording dependences on any \p 1990 /// AA. 1991 std::optional<Value *> getAssumedSimplified(const IRPosition &V, 1992 const AbstractAttribute *AA, 1993 bool &UsedAssumedInformation, 1994 AA::ValueScope S); 1995 1996 /// Try to simplify \p IRP and in the scope \p S. If successful, true is 1997 /// returned and all potential values \p IRP can take are put into \p Values. 1998 /// If the result in \p Values contains select or PHI instructions it means 1999 /// those could not be simplified to a single value. Recursive calls with 2000 /// these instructions will yield their respective potential values. If false 2001 /// is returned no other information is valid. 2002 bool getAssumedSimplifiedValues(const IRPosition &IRP, 2003 const AbstractAttribute *AA, 2004 SmallVectorImpl<AA::ValueAndContext> &Values, 2005 AA::ValueScope S, 2006 bool &UsedAssumedInformation, 2007 bool RecurseForSelectAndPHI = true); 2008 2009 /// Register \p CB as a simplification callback. 2010 /// `Attributor::getAssumedSimplified` will use these callbacks before 2011 /// we it will ask `AAValueSimplify`. It is important to ensure this 2012 /// is called before `identifyDefaultAbstractAttributes`, assuming the 2013 /// latter is called at all. 2014 using SimplifictionCallbackTy = std::function<std::optional<Value *>( 2015 const IRPosition &, const AbstractAttribute *, bool &)>; 2016 void registerSimplificationCallback(const IRPosition &IRP, 2017 const SimplifictionCallbackTy &CB) { 2018 SimplificationCallbacks[IRP].emplace_back(CB); 2019 } 2020 2021 /// Return true if there is a simplification callback for \p IRP. 2022 bool hasSimplificationCallback(const IRPosition &IRP) { 2023 return SimplificationCallbacks.count(IRP); 2024 } 2025 2026 /// Register \p CB as a simplification callback. 2027 /// Similar to \p registerSimplificationCallback, the call back will be called 2028 /// first when we simplify a global variable \p GV. 2029 using GlobalVariableSimplifictionCallbackTy = 2030 std::function<std::optional<Constant *>( 2031 const GlobalVariable &, const AbstractAttribute *, bool &)>; 2032 void registerGlobalVariableSimplificationCallback( 2033 const GlobalVariable &GV, 2034 const GlobalVariableSimplifictionCallbackTy &CB) { 2035 GlobalVariableSimplificationCallbacks[&GV].emplace_back(CB); 2036 } 2037 2038 /// Return true if there is a simplification callback for \p GV. 2039 bool hasGlobalVariableSimplificationCallback(const GlobalVariable &GV) { 2040 return GlobalVariableSimplificationCallbacks.count(&GV); 2041 } 2042 2043 /// Return \p std::nullopt if there is no call back registered for \p GV or 2044 /// the call back is still not sure if \p GV can be simplified. Return \p 2045 /// nullptr if \p GV can't be simplified. 2046 std::optional<Constant *> 2047 getAssumedInitializerFromCallBack(const GlobalVariable &GV, 2048 const AbstractAttribute *AA, 2049 bool &UsedAssumedInformation) { 2050 assert(GlobalVariableSimplificationCallbacks.contains(&GV)); 2051 for (auto &CB : GlobalVariableSimplificationCallbacks.lookup(&GV)) { 2052 auto SimplifiedGV = CB(GV, AA, UsedAssumedInformation); 2053 // For now we assume the call back will not return a std::nullopt. 2054 assert(SimplifiedGV.has_value() && "SimplifiedGV has not value"); 2055 return *SimplifiedGV; 2056 } 2057 llvm_unreachable("there must be a callback registered"); 2058 } 2059 2060 using VirtualUseCallbackTy = 2061 std::function<bool(Attributor &, const AbstractAttribute *)>; 2062 void registerVirtualUseCallback(const Value &V, 2063 const VirtualUseCallbackTy &CB) { 2064 VirtualUseCallbacks[&V].emplace_back(CB); 2065 } 2066 2067 private: 2068 /// The vector with all simplification callbacks registered by outside AAs. 2069 DenseMap<IRPosition, SmallVector<SimplifictionCallbackTy, 1>> 2070 SimplificationCallbacks; 2071 2072 /// The vector with all simplification callbacks for global variables 2073 /// registered by outside AAs. 2074 DenseMap<const GlobalVariable *, 2075 SmallVector<GlobalVariableSimplifictionCallbackTy, 1>> 2076 GlobalVariableSimplificationCallbacks; 2077 2078 DenseMap<const Value *, SmallVector<VirtualUseCallbackTy, 1>> 2079 VirtualUseCallbacks; 2080 2081 public: 2082 /// Translate \p V from the callee context into the call site context. 2083 std::optional<Value *> 2084 translateArgumentToCallSiteContent(std::optional<Value *> V, CallBase &CB, 2085 const AbstractAttribute &AA, 2086 bool &UsedAssumedInformation); 2087 2088 /// Return true if \p AA (or its context instruction) is assumed dead. 2089 /// 2090 /// If \p LivenessAA is not provided it is queried. 2091 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA, 2092 bool &UsedAssumedInformation, 2093 bool CheckBBLivenessOnly = false, 2094 DepClassTy DepClass = DepClassTy::OPTIONAL); 2095 2096 /// Return true if \p I is assumed dead. 2097 /// 2098 /// If \p LivenessAA is not provided it is queried. 2099 bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA, 2100 const AAIsDead *LivenessAA, bool &UsedAssumedInformation, 2101 bool CheckBBLivenessOnly = false, 2102 DepClassTy DepClass = DepClassTy::OPTIONAL, 2103 bool CheckForDeadStore = false); 2104 2105 /// Return true if \p U is assumed dead. 2106 /// 2107 /// If \p FnLivenessAA is not provided it is queried. 2108 bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA, 2109 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation, 2110 bool CheckBBLivenessOnly = false, 2111 DepClassTy DepClass = DepClassTy::OPTIONAL); 2112 2113 /// Return true if \p IRP is assumed dead. 2114 /// 2115 /// If \p FnLivenessAA is not provided it is queried. 2116 bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA, 2117 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation, 2118 bool CheckBBLivenessOnly = false, 2119 DepClassTy DepClass = DepClassTy::OPTIONAL); 2120 2121 /// Return true if \p BB is assumed dead. 2122 /// 2123 /// If \p LivenessAA is not provided it is queried. 2124 bool isAssumedDead(const BasicBlock &BB, const AbstractAttribute *QueryingAA, 2125 const AAIsDead *FnLivenessAA, 2126 DepClassTy DepClass = DepClassTy::OPTIONAL); 2127 2128 /// Check \p Pred on all potential Callees of \p CB. 2129 /// 2130 /// This method will evaluate \p Pred with all potential callees of \p CB as 2131 /// input and return true if \p Pred does. If some callees might be unknown 2132 /// this function will return false. 2133 bool checkForAllCallees( 2134 function_ref<bool(ArrayRef<const Function *> Callees)> Pred, 2135 const AbstractAttribute &QueryingAA, const CallBase &CB); 2136 2137 /// Check \p Pred on all (transitive) uses of \p V. 2138 /// 2139 /// This method will evaluate \p Pred on all (transitive) uses of the 2140 /// associated value and return true if \p Pred holds every time. 2141 /// If uses are skipped in favor of equivalent ones, e.g., if we look through 2142 /// memory, the \p EquivalentUseCB will be used to give the caller an idea 2143 /// what original used was replaced by a new one (or new ones). The visit is 2144 /// cut short if \p EquivalentUseCB returns false and the function will return 2145 /// false as well. 2146 bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred, 2147 const AbstractAttribute &QueryingAA, const Value &V, 2148 bool CheckBBLivenessOnly = false, 2149 DepClassTy LivenessDepClass = DepClassTy::OPTIONAL, 2150 bool IgnoreDroppableUses = true, 2151 function_ref<bool(const Use &OldU, const Use &NewU)> 2152 EquivalentUseCB = nullptr); 2153 2154 /// Emit a remark generically. 2155 /// 2156 /// This template function can be used to generically emit a remark. The 2157 /// RemarkKind should be one of the following: 2158 /// - OptimizationRemark to indicate a successful optimization attempt 2159 /// - OptimizationRemarkMissed to report a failed optimization attempt 2160 /// - OptimizationRemarkAnalysis to provide additional information about an 2161 /// optimization attempt 2162 /// 2163 /// The remark is built using a callback function \p RemarkCB that takes a 2164 /// RemarkKind as input and returns a RemarkKind. 2165 template <typename RemarkKind, typename RemarkCallBack> 2166 void emitRemark(Instruction *I, StringRef RemarkName, 2167 RemarkCallBack &&RemarkCB) const { 2168 if (!Configuration.OREGetter) 2169 return; 2170 2171 Function *F = I->getFunction(); 2172 auto &ORE = Configuration.OREGetter(F); 2173 2174 if (RemarkName.starts_with("OMP")) 2175 ORE.emit([&]() { 2176 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I)) 2177 << " [" << RemarkName << "]"; 2178 }); 2179 else 2180 ORE.emit([&]() { 2181 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I)); 2182 }); 2183 } 2184 2185 /// Emit a remark on a function. 2186 template <typename RemarkKind, typename RemarkCallBack> 2187 void emitRemark(Function *F, StringRef RemarkName, 2188 RemarkCallBack &&RemarkCB) const { 2189 if (!Configuration.OREGetter) 2190 return; 2191 2192 auto &ORE = Configuration.OREGetter(F); 2193 2194 if (RemarkName.starts_with("OMP")) 2195 ORE.emit([&]() { 2196 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F)) 2197 << " [" << RemarkName << "]"; 2198 }); 2199 else 2200 ORE.emit([&]() { 2201 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F)); 2202 }); 2203 } 2204 2205 /// Helper struct used in the communication between an abstract attribute (AA) 2206 /// that wants to change the signature of a function and the Attributor which 2207 /// applies the changes. The struct is partially initialized with the 2208 /// information from the AA (see the constructor). All other members are 2209 /// provided by the Attributor prior to invoking any callbacks. 2210 struct ArgumentReplacementInfo { 2211 /// Callee repair callback type 2212 /// 2213 /// The function repair callback is invoked once to rewire the replacement 2214 /// arguments in the body of the new function. The argument replacement info 2215 /// is passed, as build from the registerFunctionSignatureRewrite call, as 2216 /// well as the replacement function and an iteratore to the first 2217 /// replacement argument. 2218 using CalleeRepairCBTy = std::function<void( 2219 const ArgumentReplacementInfo &, Function &, Function::arg_iterator)>; 2220 2221 /// Abstract call site (ACS) repair callback type 2222 /// 2223 /// The abstract call site repair callback is invoked once on every abstract 2224 /// call site of the replaced function (\see ReplacedFn). The callback needs 2225 /// to provide the operands for the call to the new replacement function. 2226 /// The number and type of the operands appended to the provided vector 2227 /// (second argument) is defined by the number and types determined through 2228 /// the replacement type vector (\see ReplacementTypes). The first argument 2229 /// is the ArgumentReplacementInfo object registered with the Attributor 2230 /// through the registerFunctionSignatureRewrite call. 2231 using ACSRepairCBTy = 2232 std::function<void(const ArgumentReplacementInfo &, AbstractCallSite, 2233 SmallVectorImpl<Value *> &)>; 2234 2235 /// Simple getters, see the corresponding members for details. 2236 ///{ 2237 2238 Attributor &getAttributor() const { return A; } 2239 const Function &getReplacedFn() const { return ReplacedFn; } 2240 const Argument &getReplacedArg() const { return ReplacedArg; } 2241 unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); } 2242 const SmallVectorImpl<Type *> &getReplacementTypes() const { 2243 return ReplacementTypes; 2244 } 2245 2246 ///} 2247 2248 private: 2249 /// Constructor that takes the argument to be replaced, the types of 2250 /// the replacement arguments, as well as callbacks to repair the call sites 2251 /// and new function after the replacement happened. 2252 ArgumentReplacementInfo(Attributor &A, Argument &Arg, 2253 ArrayRef<Type *> ReplacementTypes, 2254 CalleeRepairCBTy &&CalleeRepairCB, 2255 ACSRepairCBTy &&ACSRepairCB) 2256 : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg), 2257 ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()), 2258 CalleeRepairCB(std::move(CalleeRepairCB)), 2259 ACSRepairCB(std::move(ACSRepairCB)) {} 2260 2261 /// Reference to the attributor to allow access from the callbacks. 2262 Attributor &A; 2263 2264 /// The "old" function replaced by ReplacementFn. 2265 const Function &ReplacedFn; 2266 2267 /// The "old" argument replaced by new ones defined via ReplacementTypes. 2268 const Argument &ReplacedArg; 2269 2270 /// The types of the arguments replacing ReplacedArg. 2271 const SmallVector<Type *, 8> ReplacementTypes; 2272 2273 /// Callee repair callback, see CalleeRepairCBTy. 2274 const CalleeRepairCBTy CalleeRepairCB; 2275 2276 /// Abstract call site (ACS) repair callback, see ACSRepairCBTy. 2277 const ACSRepairCBTy ACSRepairCB; 2278 2279 /// Allow access to the private members from the Attributor. 2280 friend struct Attributor; 2281 }; 2282 2283 /// Check if we can rewrite a function signature. 2284 /// 2285 /// The argument \p Arg is replaced with new ones defined by the number, 2286 /// order, and types in \p ReplacementTypes. 2287 /// 2288 /// \returns True, if the replacement can be registered, via 2289 /// registerFunctionSignatureRewrite, false otherwise. 2290 bool isValidFunctionSignatureRewrite(Argument &Arg, 2291 ArrayRef<Type *> ReplacementTypes); 2292 2293 /// Register a rewrite for a function signature. 2294 /// 2295 /// The argument \p Arg is replaced with new ones defined by the number, 2296 /// order, and types in \p ReplacementTypes. The rewiring at the call sites is 2297 /// done through \p ACSRepairCB and at the callee site through 2298 /// \p CalleeRepairCB. 2299 /// 2300 /// \returns True, if the replacement was registered, false otherwise. 2301 bool registerFunctionSignatureRewrite( 2302 Argument &Arg, ArrayRef<Type *> ReplacementTypes, 2303 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, 2304 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB); 2305 2306 /// Check \p Pred on all function call sites. 2307 /// 2308 /// This method will evaluate \p Pred on call sites and return 2309 /// true if \p Pred holds in every call sites. However, this is only possible 2310 /// all call sites are known, hence the function has internal linkage. 2311 /// If true is returned, \p UsedAssumedInformation is set if assumed 2312 /// information was used to skip or simplify potential call sites. 2313 bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred, 2314 const AbstractAttribute &QueryingAA, 2315 bool RequireAllCallSites, 2316 bool &UsedAssumedInformation); 2317 2318 /// Check \p Pred on all call sites of \p Fn. 2319 /// 2320 /// This method will evaluate \p Pred on call sites and return 2321 /// true if \p Pred holds in every call sites. However, this is only possible 2322 /// all call sites are known, hence the function has internal linkage. 2323 /// If true is returned, \p UsedAssumedInformation is set if assumed 2324 /// information was used to skip or simplify potential call sites. 2325 bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred, 2326 const Function &Fn, bool RequireAllCallSites, 2327 const AbstractAttribute *QueryingAA, 2328 bool &UsedAssumedInformation, 2329 bool CheckPotentiallyDead = false); 2330 2331 /// Check \p Pred on all values potentially returned by the function 2332 /// associated with \p QueryingAA. 2333 /// 2334 /// This is the context insensitive version of the method above. 2335 bool 2336 checkForAllReturnedValues(function_ref<bool(Value &)> Pred, 2337 const AbstractAttribute &QueryingAA, 2338 AA::ValueScope S = AA::ValueScope::Intraprocedural, 2339 bool RecurseForSelectAndPHI = true); 2340 2341 /// Check \p Pred on all instructions in \p Fn with an opcode present in 2342 /// \p Opcodes. 2343 /// 2344 /// This method will evaluate \p Pred on all instructions with an opcode 2345 /// present in \p Opcode and return true if \p Pred holds on all of them. 2346 bool checkForAllInstructions(function_ref<bool(Instruction &)> Pred, 2347 const Function *Fn, 2348 const AbstractAttribute *QueryingAA, 2349 ArrayRef<unsigned> Opcodes, 2350 bool &UsedAssumedInformation, 2351 bool CheckBBLivenessOnly = false, 2352 bool CheckPotentiallyDead = false); 2353 2354 /// Check \p Pred on all instructions with an opcode present in \p Opcodes. 2355 /// 2356 /// This method will evaluate \p Pred on all instructions with an opcode 2357 /// present in \p Opcode and return true if \p Pred holds on all of them. 2358 bool checkForAllInstructions(function_ref<bool(Instruction &)> Pred, 2359 const AbstractAttribute &QueryingAA, 2360 ArrayRef<unsigned> Opcodes, 2361 bool &UsedAssumedInformation, 2362 bool CheckBBLivenessOnly = false, 2363 bool CheckPotentiallyDead = false); 2364 2365 /// Check \p Pred on all call-like instructions (=CallBased derived). 2366 /// 2367 /// See checkForAllCallLikeInstructions(...) for more information. 2368 bool checkForAllCallLikeInstructions(function_ref<bool(Instruction &)> Pred, 2369 const AbstractAttribute &QueryingAA, 2370 bool &UsedAssumedInformation, 2371 bool CheckBBLivenessOnly = false, 2372 bool CheckPotentiallyDead = false) { 2373 return checkForAllInstructions( 2374 Pred, QueryingAA, 2375 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, 2376 (unsigned)Instruction::Call}, 2377 UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead); 2378 } 2379 2380 /// Check \p Pred on all Read/Write instructions. 2381 /// 2382 /// This method will evaluate \p Pred on all instructions that read or write 2383 /// to memory present in the information cache and return true if \p Pred 2384 /// holds on all of them. 2385 bool checkForAllReadWriteInstructions(function_ref<bool(Instruction &)> Pred, 2386 AbstractAttribute &QueryingAA, 2387 bool &UsedAssumedInformation); 2388 2389 /// Create a shallow wrapper for \p F such that \p F has internal linkage 2390 /// afterwards. It also sets the original \p F 's name to anonymous 2391 /// 2392 /// A wrapper is a function with the same type (and attributes) as \p F 2393 /// that will only call \p F and return the result, if any. 2394 /// 2395 /// Assuming the declaration of looks like: 2396 /// rty F(aty0 arg0, ..., atyN argN); 2397 /// 2398 /// The wrapper will then look as follows: 2399 /// rty wrapper(aty0 arg0, ..., atyN argN) { 2400 /// return F(arg0, ..., argN); 2401 /// } 2402 /// 2403 static void createShallowWrapper(Function &F); 2404 2405 /// Returns true if the function \p F can be internalized. i.e. it has a 2406 /// compatible linkage. 2407 static bool isInternalizable(Function &F); 2408 2409 /// Make another copy of the function \p F such that the copied version has 2410 /// internal linkage afterwards and can be analysed. Then we replace all uses 2411 /// of the original function to the copied one 2412 /// 2413 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr` 2414 /// linkage can be internalized because these linkages guarantee that other 2415 /// definitions with the same name have the same semantics as this one. 2416 /// 2417 /// This will only be run if the `attributor-allow-deep-wrappers` option is 2418 /// set, or if the function is called with \p Force set to true. 2419 /// 2420 /// If the function \p F failed to be internalized the return value will be a 2421 /// null pointer. 2422 static Function *internalizeFunction(Function &F, bool Force = false); 2423 2424 /// Make copies of each function in the set \p FnSet such that the copied 2425 /// version has internal linkage afterwards and can be analysed. Then we 2426 /// replace all uses of the original function to the copied one. The map 2427 /// \p FnMap contains a mapping of functions to their internalized versions. 2428 /// 2429 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr` 2430 /// linkage can be internalized because these linkages guarantee that other 2431 /// definitions with the same name have the same semantics as this one. 2432 /// 2433 /// This version will internalize all the functions in the set \p FnSet at 2434 /// once and then replace the uses. This prevents internalized functions being 2435 /// called by external functions when there is an internalized version in the 2436 /// module. 2437 static bool internalizeFunctions(SmallPtrSetImpl<Function *> &FnSet, 2438 DenseMap<Function *, Function *> &FnMap); 2439 2440 /// Return the data layout associated with the anchor scope. 2441 const DataLayout &getDataLayout() const { return InfoCache.DL; } 2442 2443 /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s. 2444 BumpPtrAllocator &Allocator; 2445 2446 const SmallSetVector<Function *, 8> &getModifiedFunctions() { 2447 return CGModifiedFunctions; 2448 } 2449 2450 private: 2451 /// This method will do fixpoint iteration until fixpoint or the 2452 /// maximum iteration count is reached. 2453 /// 2454 /// If the maximum iteration count is reached, This method will 2455 /// indicate pessimistic fixpoint on attributes that transitively depend 2456 /// on attributes that were scheduled for an update. 2457 void runTillFixpoint(); 2458 2459 /// Gets called after scheduling, manifests attributes to the LLVM IR. 2460 ChangeStatus manifestAttributes(); 2461 2462 /// Gets called after attributes have been manifested, cleans up the IR. 2463 /// Deletes dead functions, blocks and instructions. 2464 /// Rewrites function signitures and updates the call graph. 2465 ChangeStatus cleanupIR(); 2466 2467 /// Identify internal functions that are effectively dead, thus not reachable 2468 /// from a live entry point. The functions are added to ToBeDeletedFunctions. 2469 void identifyDeadInternalFunctions(); 2470 2471 /// Run `::update` on \p AA and track the dependences queried while doing so. 2472 /// Also adjust the state if we know further updates are not necessary. 2473 ChangeStatus updateAA(AbstractAttribute &AA); 2474 2475 /// Remember the dependences on the top of the dependence stack such that they 2476 /// may trigger further updates. (\see DependenceStack) 2477 void rememberDependences(); 2478 2479 /// Determine if CallBase context in \p IRP should be propagated. 2480 bool shouldPropagateCallBaseContext(const IRPosition &IRP); 2481 2482 /// Apply all requested function signature rewrites 2483 /// (\see registerFunctionSignatureRewrite) and return Changed if the module 2484 /// was altered. 2485 ChangeStatus 2486 rewriteFunctionSignatures(SmallSetVector<Function *, 8> &ModifiedFns); 2487 2488 /// Check if the Attribute \p AA should be seeded. 2489 /// See getOrCreateAAFor. 2490 bool shouldSeedAttribute(AbstractAttribute &AA); 2491 2492 /// A nested map to lookup abstract attributes based on the argument position 2493 /// on the outer level, and the addresses of the static member (AAType::ID) on 2494 /// the inner level. 2495 ///{ 2496 using AAMapKeyTy = std::pair<const char *, IRPosition>; 2497 DenseMap<AAMapKeyTy, AbstractAttribute *> AAMap; 2498 ///} 2499 2500 /// Map to remember all requested signature changes (= argument replacements). 2501 DenseMap<Function *, SmallVector<std::unique_ptr<ArgumentReplacementInfo>, 8>> 2502 ArgumentReplacementMap; 2503 2504 /// The set of functions we are deriving attributes for. 2505 SetVector<Function *> &Functions; 2506 2507 /// The information cache that holds pre-processed (LLVM-IR) information. 2508 InformationCache &InfoCache; 2509 2510 /// Abstract Attribute dependency graph 2511 AADepGraph DG; 2512 2513 /// Set of functions for which we modified the content such that it might 2514 /// impact the call graph. 2515 SmallSetVector<Function *, 8> CGModifiedFunctions; 2516 2517 /// Information about a dependence. If FromAA is changed ToAA needs to be 2518 /// updated as well. 2519 struct DepInfo { 2520 const AbstractAttribute *FromAA; 2521 const AbstractAttribute *ToAA; 2522 DepClassTy DepClass; 2523 }; 2524 2525 /// The dependence stack is used to track dependences during an 2526 /// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be 2527 /// recursive we might have multiple vectors of dependences in here. The stack 2528 /// size, should be adjusted according to the expected recursion depth and the 2529 /// inner dependence vector size to the expected number of dependences per 2530 /// abstract attribute. Since the inner vectors are actually allocated on the 2531 /// stack we can be generous with their size. 2532 using DependenceVector = SmallVector<DepInfo, 8>; 2533 SmallVector<DependenceVector *, 16> DependenceStack; 2534 2535 /// A set to remember the functions we already assume to be live and visited. 2536 DenseSet<const Function *> VisitedFunctions; 2537 2538 /// Uses we replace with a new value after manifest is done. We will remove 2539 /// then trivially dead instructions as well. 2540 SmallMapVector<Use *, Value *, 32> ToBeChangedUses; 2541 2542 /// Values we replace with a new value after manifest is done. We will remove 2543 /// then trivially dead instructions as well. 2544 SmallMapVector<Value *, PointerIntPair<Value *, 1, bool>, 32> 2545 ToBeChangedValues; 2546 2547 /// Instructions we replace with `unreachable` insts after manifest is done. 2548 SmallSetVector<WeakVH, 16> ToBeChangedToUnreachableInsts; 2549 2550 /// Invoke instructions with at least a single dead successor block. 2551 SmallSetVector<WeakVH, 16> InvokeWithDeadSuccessor; 2552 2553 /// A flag that indicates which stage of the process we are in. Initially, the 2554 /// phase is SEEDING. Phase is changed in `Attributor::run()` 2555 enum class AttributorPhase { 2556 SEEDING, 2557 UPDATE, 2558 MANIFEST, 2559 CLEANUP, 2560 } Phase = AttributorPhase::SEEDING; 2561 2562 /// The current initialization chain length. Tracked to avoid stack overflows. 2563 unsigned InitializationChainLength = 0; 2564 2565 /// Functions, blocks, and instructions we delete after manifest is done. 2566 /// 2567 ///{ 2568 SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks; 2569 SmallSetVector<Function *, 8> ToBeDeletedFunctions; 2570 SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks; 2571 SmallSetVector<WeakVH, 8> ToBeDeletedInsts; 2572 ///} 2573 2574 /// Container with all the query AAs that requested an update via 2575 /// registerForUpdate. 2576 SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate; 2577 2578 /// User provided configuration for this Attributor instance. 2579 const AttributorConfig Configuration; 2580 2581 friend AADepGraph; 2582 friend AttributorCallGraph; 2583 }; 2584 2585 /// An interface to query the internal state of an abstract attribute. 2586 /// 2587 /// The abstract state is a minimal interface that allows the Attributor to 2588 /// communicate with the abstract attributes about their internal state without 2589 /// enforcing or exposing implementation details, e.g., the (existence of an) 2590 /// underlying lattice. 2591 /// 2592 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2) 2593 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint 2594 /// was reached or (4) a pessimistic fixpoint was enforced. 2595 /// 2596 /// All methods need to be implemented by the subclass. For the common use case, 2597 /// a single boolean state or a bit-encoded state, the BooleanState and 2598 /// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract 2599 /// attribute can inherit from them to get the abstract state interface and 2600 /// additional methods to directly modify the state based if needed. See the 2601 /// class comments for help. 2602 struct AbstractState { 2603 virtual ~AbstractState() = default; 2604 2605 /// Return if this abstract state is in a valid state. If false, no 2606 /// information provided should be used. 2607 virtual bool isValidState() const = 0; 2608 2609 /// Return if this abstract state is fixed, thus does not need to be updated 2610 /// if information changes as it cannot change itself. 2611 virtual bool isAtFixpoint() const = 0; 2612 2613 /// Indicate that the abstract state should converge to the optimistic state. 2614 /// 2615 /// This will usually make the optimistically assumed state the known to be 2616 /// true state. 2617 /// 2618 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change. 2619 virtual ChangeStatus indicateOptimisticFixpoint() = 0; 2620 2621 /// Indicate that the abstract state should converge to the pessimistic state. 2622 /// 2623 /// This will usually revert the optimistically assumed state to the known to 2624 /// be true state. 2625 /// 2626 /// \returns ChangeStatus::CHANGED as the assumed value may change. 2627 virtual ChangeStatus indicatePessimisticFixpoint() = 0; 2628 }; 2629 2630 /// Simple state with integers encoding. 2631 /// 2632 /// The interface ensures that the assumed bits are always a subset of the known 2633 /// bits. Users can only add known bits and, except through adding known bits, 2634 /// they can only remove assumed bits. This should guarantee monotonicity and 2635 /// thereby the existence of a fixpoint (if used correctly). The fixpoint is 2636 /// reached when the assumed and known state/bits are equal. Users can 2637 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known 2638 /// state will catch up with the assumed one, for a pessimistic fixpoint it is 2639 /// the other way around. 2640 template <typename base_ty, base_ty BestState, base_ty WorstState> 2641 struct IntegerStateBase : public AbstractState { 2642 using base_t = base_ty; 2643 2644 IntegerStateBase() = default; 2645 IntegerStateBase(base_t Assumed) : Assumed(Assumed) {} 2646 2647 /// Return the best possible representable state. 2648 static constexpr base_t getBestState() { return BestState; } 2649 static constexpr base_t getBestState(const IntegerStateBase &) { 2650 return getBestState(); 2651 } 2652 2653 /// Return the worst possible representable state. 2654 static constexpr base_t getWorstState() { return WorstState; } 2655 static constexpr base_t getWorstState(const IntegerStateBase &) { 2656 return getWorstState(); 2657 } 2658 2659 /// See AbstractState::isValidState() 2660 /// NOTE: For now we simply pretend that the worst possible state is invalid. 2661 bool isValidState() const override { return Assumed != getWorstState(); } 2662 2663 /// See AbstractState::isAtFixpoint() 2664 bool isAtFixpoint() const override { return Assumed == Known; } 2665 2666 /// See AbstractState::indicateOptimisticFixpoint(...) 2667 ChangeStatus indicateOptimisticFixpoint() override { 2668 Known = Assumed; 2669 return ChangeStatus::UNCHANGED; 2670 } 2671 2672 /// See AbstractState::indicatePessimisticFixpoint(...) 2673 ChangeStatus indicatePessimisticFixpoint() override { 2674 Assumed = Known; 2675 return ChangeStatus::CHANGED; 2676 } 2677 2678 /// Return the known state encoding 2679 base_t getKnown() const { return Known; } 2680 2681 /// Return the assumed state encoding. 2682 base_t getAssumed() const { return Assumed; } 2683 2684 /// Equality for IntegerStateBase. 2685 bool 2686 operator==(const IntegerStateBase<base_t, BestState, WorstState> &R) const { 2687 return this->getAssumed() == R.getAssumed() && 2688 this->getKnown() == R.getKnown(); 2689 } 2690 2691 /// Inequality for IntegerStateBase. 2692 bool 2693 operator!=(const IntegerStateBase<base_t, BestState, WorstState> &R) const { 2694 return !(*this == R); 2695 } 2696 2697 /// "Clamp" this state with \p R. The result is subtype dependent but it is 2698 /// intended that only information assumed in both states will be assumed in 2699 /// this one afterwards. 2700 void operator^=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 2701 handleNewAssumedValue(R.getAssumed()); 2702 } 2703 2704 /// "Clamp" this state with \p R. The result is subtype dependent but it is 2705 /// intended that information known in either state will be known in 2706 /// this one afterwards. 2707 void operator+=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 2708 handleNewKnownValue(R.getKnown()); 2709 } 2710 2711 void operator|=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 2712 joinOR(R.getAssumed(), R.getKnown()); 2713 } 2714 2715 void operator&=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 2716 joinAND(R.getAssumed(), R.getKnown()); 2717 } 2718 2719 protected: 2720 /// Handle a new assumed value \p Value. Subtype dependent. 2721 virtual void handleNewAssumedValue(base_t Value) = 0; 2722 2723 /// Handle a new known value \p Value. Subtype dependent. 2724 virtual void handleNewKnownValue(base_t Value) = 0; 2725 2726 /// Handle a value \p Value. Subtype dependent. 2727 virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0; 2728 2729 /// Handle a new assumed value \p Value. Subtype dependent. 2730 virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0; 2731 2732 /// The known state encoding in an integer of type base_t. 2733 base_t Known = getWorstState(); 2734 2735 /// The assumed state encoding in an integer of type base_t. 2736 base_t Assumed = getBestState(); 2737 }; 2738 2739 /// Specialization of the integer state for a bit-wise encoding. 2740 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0), 2741 base_ty WorstState = 0> 2742 struct BitIntegerState 2743 : public IntegerStateBase<base_ty, BestState, WorstState> { 2744 using super = IntegerStateBase<base_ty, BestState, WorstState>; 2745 using base_t = base_ty; 2746 BitIntegerState() = default; 2747 BitIntegerState(base_t Assumed) : super(Assumed) {} 2748 2749 /// Return true if the bits set in \p BitsEncoding are "known bits". 2750 bool isKnown(base_t BitsEncoding = BestState) const { 2751 return (this->Known & BitsEncoding) == BitsEncoding; 2752 } 2753 2754 /// Return true if the bits set in \p BitsEncoding are "assumed bits". 2755 bool isAssumed(base_t BitsEncoding = BestState) const { 2756 return (this->Assumed & BitsEncoding) == BitsEncoding; 2757 } 2758 2759 /// Add the bits in \p BitsEncoding to the "known bits". 2760 BitIntegerState &addKnownBits(base_t Bits) { 2761 // Make sure we never miss any "known bits". 2762 this->Assumed |= Bits; 2763 this->Known |= Bits; 2764 return *this; 2765 } 2766 2767 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known. 2768 BitIntegerState &removeAssumedBits(base_t BitsEncoding) { 2769 return intersectAssumedBits(~BitsEncoding); 2770 } 2771 2772 /// Remove the bits in \p BitsEncoding from the "known bits". 2773 BitIntegerState &removeKnownBits(base_t BitsEncoding) { 2774 this->Known = (this->Known & ~BitsEncoding); 2775 return *this; 2776 } 2777 2778 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones. 2779 BitIntegerState &intersectAssumedBits(base_t BitsEncoding) { 2780 // Make sure we never lose any "known bits". 2781 this->Assumed = (this->Assumed & BitsEncoding) | this->Known; 2782 return *this; 2783 } 2784 2785 private: 2786 void handleNewAssumedValue(base_t Value) override { 2787 intersectAssumedBits(Value); 2788 } 2789 void handleNewKnownValue(base_t Value) override { addKnownBits(Value); } 2790 void joinOR(base_t AssumedValue, base_t KnownValue) override { 2791 this->Known |= KnownValue; 2792 this->Assumed |= AssumedValue; 2793 } 2794 void joinAND(base_t AssumedValue, base_t KnownValue) override { 2795 this->Known &= KnownValue; 2796 this->Assumed &= AssumedValue; 2797 } 2798 }; 2799 2800 /// Specialization of the integer state for an increasing value, hence ~0u is 2801 /// the best state and 0 the worst. 2802 template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0), 2803 base_ty WorstState = 0> 2804 struct IncIntegerState 2805 : public IntegerStateBase<base_ty, BestState, WorstState> { 2806 using super = IntegerStateBase<base_ty, BestState, WorstState>; 2807 using base_t = base_ty; 2808 2809 IncIntegerState() : super() {} 2810 IncIntegerState(base_t Assumed) : super(Assumed) {} 2811 2812 /// Return the best possible representable state. 2813 static constexpr base_t getBestState() { return BestState; } 2814 static constexpr base_t 2815 getBestState(const IncIntegerState<base_ty, BestState, WorstState> &) { 2816 return getBestState(); 2817 } 2818 2819 /// Take minimum of assumed and \p Value. 2820 IncIntegerState &takeAssumedMinimum(base_t Value) { 2821 // Make sure we never lose "known value". 2822 this->Assumed = std::max(std::min(this->Assumed, Value), this->Known); 2823 return *this; 2824 } 2825 2826 /// Take maximum of known and \p Value. 2827 IncIntegerState &takeKnownMaximum(base_t Value) { 2828 // Make sure we never lose "known value". 2829 this->Assumed = std::max(Value, this->Assumed); 2830 this->Known = std::max(Value, this->Known); 2831 return *this; 2832 } 2833 2834 private: 2835 void handleNewAssumedValue(base_t Value) override { 2836 takeAssumedMinimum(Value); 2837 } 2838 void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); } 2839 void joinOR(base_t AssumedValue, base_t KnownValue) override { 2840 this->Known = std::max(this->Known, KnownValue); 2841 this->Assumed = std::max(this->Assumed, AssumedValue); 2842 } 2843 void joinAND(base_t AssumedValue, base_t KnownValue) override { 2844 this->Known = std::min(this->Known, KnownValue); 2845 this->Assumed = std::min(this->Assumed, AssumedValue); 2846 } 2847 }; 2848 2849 /// Specialization of the integer state for a decreasing value, hence 0 is the 2850 /// best state and ~0u the worst. 2851 template <typename base_ty = uint32_t> 2852 struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> { 2853 using base_t = base_ty; 2854 2855 /// Take maximum of assumed and \p Value. 2856 DecIntegerState &takeAssumedMaximum(base_t Value) { 2857 // Make sure we never lose "known value". 2858 this->Assumed = std::min(std::max(this->Assumed, Value), this->Known); 2859 return *this; 2860 } 2861 2862 /// Take minimum of known and \p Value. 2863 DecIntegerState &takeKnownMinimum(base_t Value) { 2864 // Make sure we never lose "known value". 2865 this->Assumed = std::min(Value, this->Assumed); 2866 this->Known = std::min(Value, this->Known); 2867 return *this; 2868 } 2869 2870 private: 2871 void handleNewAssumedValue(base_t Value) override { 2872 takeAssumedMaximum(Value); 2873 } 2874 void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); } 2875 void joinOR(base_t AssumedValue, base_t KnownValue) override { 2876 this->Assumed = std::min(this->Assumed, KnownValue); 2877 this->Assumed = std::min(this->Assumed, AssumedValue); 2878 } 2879 void joinAND(base_t AssumedValue, base_t KnownValue) override { 2880 this->Assumed = std::max(this->Assumed, KnownValue); 2881 this->Assumed = std::max(this->Assumed, AssumedValue); 2882 } 2883 }; 2884 2885 /// Simple wrapper for a single bit (boolean) state. 2886 struct BooleanState : public IntegerStateBase<bool, true, false> { 2887 using super = IntegerStateBase<bool, true, false>; 2888 using base_t = IntegerStateBase::base_t; 2889 2890 BooleanState() = default; 2891 BooleanState(base_t Assumed) : super(Assumed) {} 2892 2893 /// Set the assumed value to \p Value but never below the known one. 2894 void setAssumed(bool Value) { Assumed &= (Known | Value); } 2895 2896 /// Set the known and asssumed value to \p Value. 2897 void setKnown(bool Value) { 2898 Known |= Value; 2899 Assumed |= Value; 2900 } 2901 2902 /// Return true if the state is assumed to hold. 2903 bool isAssumed() const { return getAssumed(); } 2904 2905 /// Return true if the state is known to hold. 2906 bool isKnown() const { return getKnown(); } 2907 2908 private: 2909 void handleNewAssumedValue(base_t Value) override { 2910 if (!Value) 2911 Assumed = Known; 2912 } 2913 void handleNewKnownValue(base_t Value) override { 2914 if (Value) 2915 Known = (Assumed = Value); 2916 } 2917 void joinOR(base_t AssumedValue, base_t KnownValue) override { 2918 Known |= KnownValue; 2919 Assumed |= AssumedValue; 2920 } 2921 void joinAND(base_t AssumedValue, base_t KnownValue) override { 2922 Known &= KnownValue; 2923 Assumed &= AssumedValue; 2924 } 2925 }; 2926 2927 /// State for an integer range. 2928 struct IntegerRangeState : public AbstractState { 2929 2930 /// Bitwidth of the associated value. 2931 uint32_t BitWidth; 2932 2933 /// State representing assumed range, initially set to empty. 2934 ConstantRange Assumed; 2935 2936 /// State representing known range, initially set to [-inf, inf]. 2937 ConstantRange Known; 2938 2939 IntegerRangeState(uint32_t BitWidth) 2940 : BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)), 2941 Known(ConstantRange::getFull(BitWidth)) {} 2942 2943 IntegerRangeState(const ConstantRange &CR) 2944 : BitWidth(CR.getBitWidth()), Assumed(CR), 2945 Known(getWorstState(CR.getBitWidth())) {} 2946 2947 /// Return the worst possible representable state. 2948 static ConstantRange getWorstState(uint32_t BitWidth) { 2949 return ConstantRange::getFull(BitWidth); 2950 } 2951 2952 /// Return the best possible representable state. 2953 static ConstantRange getBestState(uint32_t BitWidth) { 2954 return ConstantRange::getEmpty(BitWidth); 2955 } 2956 static ConstantRange getBestState(const IntegerRangeState &IRS) { 2957 return getBestState(IRS.getBitWidth()); 2958 } 2959 2960 /// Return associated values' bit width. 2961 uint32_t getBitWidth() const { return BitWidth; } 2962 2963 /// See AbstractState::isValidState() 2964 bool isValidState() const override { 2965 return BitWidth > 0 && !Assumed.isFullSet(); 2966 } 2967 2968 /// See AbstractState::isAtFixpoint() 2969 bool isAtFixpoint() const override { return Assumed == Known; } 2970 2971 /// See AbstractState::indicateOptimisticFixpoint(...) 2972 ChangeStatus indicateOptimisticFixpoint() override { 2973 Known = Assumed; 2974 return ChangeStatus::CHANGED; 2975 } 2976 2977 /// See AbstractState::indicatePessimisticFixpoint(...) 2978 ChangeStatus indicatePessimisticFixpoint() override { 2979 Assumed = Known; 2980 return ChangeStatus::CHANGED; 2981 } 2982 2983 /// Return the known state encoding 2984 ConstantRange getKnown() const { return Known; } 2985 2986 /// Return the assumed state encoding. 2987 ConstantRange getAssumed() const { return Assumed; } 2988 2989 /// Unite assumed range with the passed state. 2990 void unionAssumed(const ConstantRange &R) { 2991 // Don't lose a known range. 2992 Assumed = Assumed.unionWith(R).intersectWith(Known); 2993 } 2994 2995 /// See IntegerRangeState::unionAssumed(..). 2996 void unionAssumed(const IntegerRangeState &R) { 2997 unionAssumed(R.getAssumed()); 2998 } 2999 3000 /// Intersect known range with the passed state. 3001 void intersectKnown(const ConstantRange &R) { 3002 Assumed = Assumed.intersectWith(R); 3003 Known = Known.intersectWith(R); 3004 } 3005 3006 /// See IntegerRangeState::intersectKnown(..). 3007 void intersectKnown(const IntegerRangeState &R) { 3008 intersectKnown(R.getKnown()); 3009 } 3010 3011 /// Equality for IntegerRangeState. 3012 bool operator==(const IntegerRangeState &R) const { 3013 return getAssumed() == R.getAssumed() && getKnown() == R.getKnown(); 3014 } 3015 3016 /// "Clamp" this state with \p R. The result is subtype dependent but it is 3017 /// intended that only information assumed in both states will be assumed in 3018 /// this one afterwards. 3019 IntegerRangeState operator^=(const IntegerRangeState &R) { 3020 // NOTE: `^=` operator seems like `intersect` but in this case, we need to 3021 // take `union`. 3022 unionAssumed(R); 3023 return *this; 3024 } 3025 3026 IntegerRangeState operator&=(const IntegerRangeState &R) { 3027 // NOTE: `&=` operator seems like `intersect` but in this case, we need to 3028 // take `union`. 3029 Known = Known.unionWith(R.getKnown()); 3030 Assumed = Assumed.unionWith(R.getAssumed()); 3031 return *this; 3032 } 3033 }; 3034 3035 /// Simple state for a set. 3036 /// 3037 /// This represents a state containing a set of values. The interface supports 3038 /// modelling sets that contain all possible elements. The state's internal 3039 /// value is modified using union or intersection operations. 3040 template <typename BaseTy> struct SetState : public AbstractState { 3041 /// A wrapper around a set that has semantics for handling unions and 3042 /// intersections with a "universal" set that contains all elements. 3043 struct SetContents { 3044 /// Creates a universal set with no concrete elements or an empty set. 3045 SetContents(bool Universal) : Universal(Universal) {} 3046 3047 /// Creates a non-universal set with concrete values. 3048 SetContents(const DenseSet<BaseTy> &Assumptions) 3049 : Universal(false), Set(Assumptions) {} 3050 3051 SetContents(bool Universal, const DenseSet<BaseTy> &Assumptions) 3052 : Universal(Universal), Set(Assumptions) {} 3053 3054 const DenseSet<BaseTy> &getSet() const { return Set; } 3055 3056 bool isUniversal() const { return Universal; } 3057 3058 bool empty() const { return Set.empty() && !Universal; } 3059 3060 /// Finds A := A ^ B where A or B could be the "Universal" set which 3061 /// contains every possible attribute. Returns true if changes were made. 3062 bool getIntersection(const SetContents &RHS) { 3063 bool IsUniversal = Universal; 3064 unsigned Size = Set.size(); 3065 3066 // A := A ^ U = A 3067 if (RHS.isUniversal()) 3068 return false; 3069 3070 // A := U ^ B = B 3071 if (Universal) 3072 Set = RHS.getSet(); 3073 else 3074 set_intersect(Set, RHS.getSet()); 3075 3076 Universal &= RHS.isUniversal(); 3077 return IsUniversal != Universal || Size != Set.size(); 3078 } 3079 3080 /// Finds A := A u B where A or B could be the "Universal" set which 3081 /// contains every possible attribute. returns true if changes were made. 3082 bool getUnion(const SetContents &RHS) { 3083 bool IsUniversal = Universal; 3084 unsigned Size = Set.size(); 3085 3086 // A := A u U = U = U u B 3087 if (!RHS.isUniversal() && !Universal) 3088 set_union(Set, RHS.getSet()); 3089 3090 Universal |= RHS.isUniversal(); 3091 return IsUniversal != Universal || Size != Set.size(); 3092 } 3093 3094 private: 3095 /// Indicates if this set is "universal", containing every possible element. 3096 bool Universal; 3097 3098 /// The set of currently active assumptions. 3099 DenseSet<BaseTy> Set; 3100 }; 3101 3102 SetState() : Known(false), Assumed(true), IsAtFixedpoint(false) {} 3103 3104 /// Initializes the known state with an initial set and initializes the 3105 /// assumed state as universal. 3106 SetState(const DenseSet<BaseTy> &Known) 3107 : Known(Known), Assumed(true), IsAtFixedpoint(false) {} 3108 3109 /// See AbstractState::isValidState() 3110 bool isValidState() const override { return !Assumed.empty(); } 3111 3112 /// See AbstractState::isAtFixpoint() 3113 bool isAtFixpoint() const override { return IsAtFixedpoint; } 3114 3115 /// See AbstractState::indicateOptimisticFixpoint(...) 3116 ChangeStatus indicateOptimisticFixpoint() override { 3117 IsAtFixedpoint = true; 3118 Known = Assumed; 3119 return ChangeStatus::UNCHANGED; 3120 } 3121 3122 /// See AbstractState::indicatePessimisticFixpoint(...) 3123 ChangeStatus indicatePessimisticFixpoint() override { 3124 IsAtFixedpoint = true; 3125 Assumed = Known; 3126 return ChangeStatus::CHANGED; 3127 } 3128 3129 /// Return the known state encoding. 3130 const SetContents &getKnown() const { return Known; } 3131 3132 /// Return the assumed state encoding. 3133 const SetContents &getAssumed() const { return Assumed; } 3134 3135 /// Returns if the set state contains the element. 3136 bool setContains(const BaseTy &Elem) const { 3137 return Assumed.getSet().contains(Elem) || Known.getSet().contains(Elem); 3138 } 3139 3140 /// Performs the set intersection between this set and \p RHS. Returns true if 3141 /// changes were made. 3142 bool getIntersection(const SetContents &RHS) { 3143 bool IsUniversal = Assumed.isUniversal(); 3144 unsigned SizeBefore = Assumed.getSet().size(); 3145 3146 // Get intersection and make sure that the known set is still a proper 3147 // subset of the assumed set. A := K u (A ^ R). 3148 Assumed.getIntersection(RHS); 3149 Assumed.getUnion(Known); 3150 3151 return SizeBefore != Assumed.getSet().size() || 3152 IsUniversal != Assumed.isUniversal(); 3153 } 3154 3155 /// Performs the set union between this set and \p RHS. Returns true if 3156 /// changes were made. 3157 bool getUnion(const SetContents &RHS) { return Assumed.getUnion(RHS); } 3158 3159 private: 3160 /// The set of values known for this state. 3161 SetContents Known; 3162 3163 /// The set of assumed values for this state. 3164 SetContents Assumed; 3165 3166 bool IsAtFixedpoint; 3167 }; 3168 3169 /// Helper to tie a abstract state implementation to an abstract attribute. 3170 template <typename StateTy, typename BaseType, class... Ts> 3171 struct StateWrapper : public BaseType, public StateTy { 3172 /// Provide static access to the type of the state. 3173 using StateType = StateTy; 3174 3175 StateWrapper(const IRPosition &IRP, Ts... Args) 3176 : BaseType(IRP), StateTy(Args...) {} 3177 3178 /// See AbstractAttribute::getState(...). 3179 StateType &getState() override { return *this; } 3180 3181 /// See AbstractAttribute::getState(...). 3182 const StateType &getState() const override { return *this; } 3183 }; 3184 3185 /// Helper class that provides common functionality to manifest IR attributes. 3186 template <Attribute::AttrKind AK, typename BaseType, typename AAType> 3187 struct IRAttribute : public BaseType { 3188 IRAttribute(const IRPosition &IRP) : BaseType(IRP) {} 3189 3190 /// Most boolean IRAttribute AAs don't do anything non-trivial 3191 /// in their initializers while non-boolean ones often do. Subclasses can 3192 /// change this. 3193 static bool hasTrivialInitializer() { return Attribute::isEnumAttrKind(AK); } 3194 3195 /// Compile time access to the IR attribute kind. 3196 static constexpr Attribute::AttrKind IRAttributeKind = AK; 3197 3198 /// Return true if the IR attribute(s) associated with this AA are implied for 3199 /// an undef value. 3200 static bool isImpliedByUndef() { return true; } 3201 3202 /// Return true if the IR attribute(s) associated with this AA are implied for 3203 /// an poison value. 3204 static bool isImpliedByPoison() { return true; } 3205 3206 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3207 Attribute::AttrKind ImpliedAttributeKind = AK, 3208 bool IgnoreSubsumingPositions = false) { 3209 if (AAType::isImpliedByUndef() && isa<UndefValue>(IRP.getAssociatedValue())) 3210 return true; 3211 if (AAType::isImpliedByPoison() && 3212 isa<PoisonValue>(IRP.getAssociatedValue())) 3213 return true; 3214 return A.hasAttr(IRP, {ImpliedAttributeKind}, IgnoreSubsumingPositions, 3215 ImpliedAttributeKind); 3216 } 3217 3218 /// See AbstractAttribute::manifest(...). 3219 ChangeStatus manifest(Attributor &A) override { 3220 if (isa<UndefValue>(this->getIRPosition().getAssociatedValue())) 3221 return ChangeStatus::UNCHANGED; 3222 SmallVector<Attribute, 4> DeducedAttrs; 3223 getDeducedAttributes(A, this->getAnchorValue().getContext(), DeducedAttrs); 3224 if (DeducedAttrs.empty()) 3225 return ChangeStatus::UNCHANGED; 3226 return A.manifestAttrs(this->getIRPosition(), DeducedAttrs); 3227 } 3228 3229 /// Return the kind that identifies the abstract attribute implementation. 3230 Attribute::AttrKind getAttrKind() const { return AK; } 3231 3232 /// Return the deduced attributes in \p Attrs. 3233 virtual void getDeducedAttributes(Attributor &A, LLVMContext &Ctx, 3234 SmallVectorImpl<Attribute> &Attrs) const { 3235 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind())); 3236 } 3237 }; 3238 3239 /// Base struct for all "concrete attribute" deductions. 3240 /// 3241 /// The abstract attribute is a minimal interface that allows the Attributor to 3242 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away 3243 /// implementation choices made for the subclasses but also to structure their 3244 /// implementation and simplify the use of other abstract attributes in-flight. 3245 /// 3246 /// To allow easy creation of new attributes, most methods have default 3247 /// implementations. The ones that do not are generally straight forward, except 3248 /// `AbstractAttribute::updateImpl` which is the location of most reasoning 3249 /// associated with the abstract attribute. The update is invoked by the 3250 /// Attributor in case the situation used to justify the current optimistic 3251 /// state might have changed. The Attributor determines this automatically 3252 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes. 3253 /// 3254 /// The `updateImpl` method should inspect the IR and other abstract attributes 3255 /// in-flight to justify the best possible (=optimistic) state. The actual 3256 /// implementation is, similar to the underlying abstract state encoding, not 3257 /// exposed. In the most common case, the `updateImpl` will go through a list of 3258 /// reasons why its optimistic state is valid given the current information. If 3259 /// any combination of them holds and is sufficient to justify the current 3260 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic 3261 /// state is adjusted to the situation and the method shall return CHANGED. 3262 /// 3263 /// If the manifestation of the "concrete attribute" deduced by the subclass 3264 /// differs from the "default" behavior, which is a (set of) LLVM-IR 3265 /// attribute(s) for an argument, call site argument, function return value, or 3266 /// function, the `AbstractAttribute::manifest` method should be overloaded. 3267 /// 3268 /// NOTE: If the state obtained via getState() is INVALID, thus if 3269 /// AbstractAttribute::getState().isValidState() returns false, no 3270 /// information provided by the methods of this class should be used. 3271 /// NOTE: The Attributor currently has certain limitations to what we can do. 3272 /// As a general rule of thumb, "concrete" abstract attributes should *for 3273 /// now* only perform "backward" information propagation. That means 3274 /// optimistic information obtained through abstract attributes should 3275 /// only be used at positions that precede the origin of the information 3276 /// with regards to the program flow. More practically, information can 3277 /// *now* be propagated from instructions to their enclosing function, but 3278 /// *not* from call sites to the called function. The mechanisms to allow 3279 /// both directions will be added in the future. 3280 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are 3281 /// described in the file comment. 3282 struct AbstractAttribute : public IRPosition, public AADepGraphNode { 3283 using StateType = AbstractState; 3284 3285 AbstractAttribute(const IRPosition &IRP) : IRPosition(IRP) {} 3286 3287 /// Virtual destructor. 3288 virtual ~AbstractAttribute() = default; 3289 3290 /// Compile time access to the IR attribute kind. 3291 static constexpr Attribute::AttrKind IRAttributeKind = Attribute::None; 3292 3293 /// This function is used to identify if an \p DGN is of type 3294 /// AbstractAttribute so that the dyn_cast and cast can use such information 3295 /// to cast an AADepGraphNode to an AbstractAttribute. 3296 /// 3297 /// We eagerly return true here because all AADepGraphNodes except for the 3298 /// Synthethis Node are of type AbstractAttribute 3299 static bool classof(const AADepGraphNode *DGN) { return true; } 3300 3301 /// Return false if this AA does anything non-trivial (hence not done by 3302 /// default) in its initializer. 3303 static bool hasTrivialInitializer() { return false; } 3304 3305 /// Return true if this AA requires a "callee" (or an associted function) for 3306 /// a call site positon. Default is optimistic to minimize AAs. 3307 static bool requiresCalleeForCallBase() { return false; } 3308 3309 /// Return true if this AA requires non-asm "callee" for a call site positon. 3310 static bool requiresNonAsmForCallBase() { return true; } 3311 3312 /// Return true if this AA requires all callees for an argument or function 3313 /// positon. 3314 static bool requiresCallersForArgOrFunction() { return false; } 3315 3316 /// Return false if an AA should not be created for \p IRP. 3317 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3318 return true; 3319 } 3320 3321 /// Return false if an AA should not be updated for \p IRP. 3322 static bool isValidIRPositionForUpdate(Attributor &A, const IRPosition &IRP) { 3323 Function *AssociatedFn = IRP.getAssociatedFunction(); 3324 bool IsFnInterface = IRP.isFnInterfaceKind(); 3325 assert((!IsFnInterface || AssociatedFn) && 3326 "Function interface without a function?"); 3327 3328 // TODO: Not all attributes require an exact definition. Find a way to 3329 // enable deduction for some but not all attributes in case the 3330 // definition might be changed at runtime, see also 3331 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html. 3332 // TODO: We could always determine abstract attributes and if sufficient 3333 // information was found we could duplicate the functions that do not 3334 // have an exact definition. 3335 return !IsFnInterface || A.isFunctionIPOAmendable(*AssociatedFn); 3336 } 3337 3338 /// Initialize the state with the information in the Attributor \p A. 3339 /// 3340 /// This function is called by the Attributor once all abstract attributes 3341 /// have been identified. It can and shall be used for task like: 3342 /// - identify existing knowledge in the IR and use it for the "known state" 3343 /// - perform any work that is not going to change over time, e.g., determine 3344 /// a subset of the IR, or attributes in-flight, that have to be looked at 3345 /// in the `updateImpl` method. 3346 virtual void initialize(Attributor &A) {} 3347 3348 /// A query AA is always scheduled as long as we do updates because it does 3349 /// lazy computation that cannot be determined to be done from the outside. 3350 /// However, while query AAs will not be fixed if they do not have outstanding 3351 /// dependences, we will only schedule them like other AAs. If a query AA that 3352 /// received a new query it needs to request an update via 3353 /// `Attributor::requestUpdateForAA`. 3354 virtual bool isQueryAA() const { return false; } 3355 3356 /// Return the internal abstract state for inspection. 3357 virtual StateType &getState() = 0; 3358 virtual const StateType &getState() const = 0; 3359 3360 /// Return an IR position, see struct IRPosition. 3361 const IRPosition &getIRPosition() const { return *this; }; 3362 IRPosition &getIRPosition() { return *this; }; 3363 3364 /// Helper functions, for debug purposes only. 3365 ///{ 3366 void print(raw_ostream &OS) const { print(nullptr, OS); } 3367 void print(Attributor *, raw_ostream &OS) const override; 3368 virtual void printWithDeps(raw_ostream &OS) const; 3369 void dump() const { this->print(dbgs()); } 3370 3371 /// This function should return the "summarized" assumed state as string. 3372 virtual const std::string getAsStr(Attributor *A) const = 0; 3373 3374 /// This function should return the name of the AbstractAttribute 3375 virtual const std::string getName() const = 0; 3376 3377 /// This function should return the address of the ID of the AbstractAttribute 3378 virtual const char *getIdAddr() const = 0; 3379 ///} 3380 3381 /// Allow the Attributor access to the protected methods. 3382 friend struct Attributor; 3383 3384 protected: 3385 /// Hook for the Attributor to trigger an update of the internal state. 3386 /// 3387 /// If this attribute is already fixed, this method will return UNCHANGED, 3388 /// otherwise it delegates to `AbstractAttribute::updateImpl`. 3389 /// 3390 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. 3391 ChangeStatus update(Attributor &A); 3392 3393 /// Hook for the Attributor to trigger the manifestation of the information 3394 /// represented by the abstract attribute in the LLVM-IR. 3395 /// 3396 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED. 3397 virtual ChangeStatus manifest(Attributor &A) { 3398 return ChangeStatus::UNCHANGED; 3399 } 3400 3401 /// Hook to enable custom statistic tracking, called after manifest that 3402 /// resulted in a change if statistics are enabled. 3403 /// 3404 /// We require subclasses to provide an implementation so we remember to 3405 /// add statistics for them. 3406 virtual void trackStatistics() const = 0; 3407 3408 /// The actual update/transfer function which has to be implemented by the 3409 /// derived classes. 3410 /// 3411 /// If it is called, the environment has changed and we have to determine if 3412 /// the current information is still valid or adjust it otherwise. 3413 /// 3414 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. 3415 virtual ChangeStatus updateImpl(Attributor &A) = 0; 3416 }; 3417 3418 /// Forward declarations of output streams for debug purposes. 3419 /// 3420 ///{ 3421 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA); 3422 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S); 3423 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind); 3424 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &); 3425 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State); 3426 template <typename base_ty, base_ty BestState, base_ty WorstState> 3427 raw_ostream & 3428 operator<<(raw_ostream &OS, 3429 const IntegerStateBase<base_ty, BestState, WorstState> &S) { 3430 return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")" 3431 << static_cast<const AbstractState &>(S); 3432 } 3433 raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State); 3434 ///} 3435 3436 struct AttributorPass : public PassInfoMixin<AttributorPass> { 3437 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 3438 }; 3439 struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> { 3440 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, 3441 LazyCallGraph &CG, CGSCCUpdateResult &UR); 3442 }; 3443 3444 /// A more lightweight version of the Attributor which only runs attribute 3445 /// inference but no simplifications. 3446 struct AttributorLightPass : public PassInfoMixin<AttributorLightPass> { 3447 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 3448 }; 3449 3450 /// A more lightweight version of the Attributor which only runs attribute 3451 /// inference but no simplifications. 3452 struct AttributorLightCGSCCPass 3453 : public PassInfoMixin<AttributorLightCGSCCPass> { 3454 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, 3455 LazyCallGraph &CG, CGSCCUpdateResult &UR); 3456 }; 3457 3458 /// Helper function to clamp a state \p S of type \p StateType with the 3459 /// information in \p R and indicate/return if \p S did change (as-in update is 3460 /// required to be run again). 3461 template <typename StateType> 3462 ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) { 3463 auto Assumed = S.getAssumed(); 3464 S ^= R; 3465 return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED 3466 : ChangeStatus::CHANGED; 3467 } 3468 3469 /// ---------------------------------------------------------------------------- 3470 /// Abstract Attribute Classes 3471 /// ---------------------------------------------------------------------------- 3472 3473 struct AANoUnwind 3474 : public IRAttribute<Attribute::NoUnwind, 3475 StateWrapper<BooleanState, AbstractAttribute>, 3476 AANoUnwind> { 3477 AANoUnwind(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3478 3479 /// Returns true if nounwind is assumed. 3480 bool isAssumedNoUnwind() const { return getAssumed(); } 3481 3482 /// Returns true if nounwind is known. 3483 bool isKnownNoUnwind() const { return getKnown(); } 3484 3485 /// Create an abstract attribute view for the position \p IRP. 3486 static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A); 3487 3488 /// See AbstractAttribute::getName() 3489 const std::string getName() const override { return "AANoUnwind"; } 3490 3491 /// See AbstractAttribute::getIdAddr() 3492 const char *getIdAddr() const override { return &ID; } 3493 3494 /// This function should return true if the type of the \p AA is AANoUnwind 3495 static bool classof(const AbstractAttribute *AA) { 3496 return (AA->getIdAddr() == &ID); 3497 } 3498 3499 /// Unique ID (due to the unique address) 3500 static const char ID; 3501 }; 3502 3503 struct AANoSync 3504 : public IRAttribute<Attribute::NoSync, 3505 StateWrapper<BooleanState, AbstractAttribute>, 3506 AANoSync> { 3507 AANoSync(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3508 3509 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3510 Attribute::AttrKind ImpliedAttributeKind, 3511 bool IgnoreSubsumingPositions = false) { 3512 // Note: This is also run for non-IPO amendable functions. 3513 assert(ImpliedAttributeKind == Attribute::NoSync); 3514 if (A.hasAttr(IRP, {Attribute::NoSync}, IgnoreSubsumingPositions, 3515 Attribute::NoSync)) 3516 return true; 3517 3518 // Check for readonly + non-convergent. 3519 // TODO: We should be able to use hasAttr for Attributes, not only 3520 // AttrKinds. 3521 Function *F = IRP.getAssociatedFunction(); 3522 if (!F || F->isConvergent()) 3523 return false; 3524 3525 SmallVector<Attribute, 2> Attrs; 3526 A.getAttrs(IRP, {Attribute::Memory}, Attrs, IgnoreSubsumingPositions); 3527 3528 MemoryEffects ME = MemoryEffects::unknown(); 3529 for (const Attribute &Attr : Attrs) 3530 ME &= Attr.getMemoryEffects(); 3531 3532 if (!ME.onlyReadsMemory()) 3533 return false; 3534 3535 A.manifestAttrs(IRP, Attribute::get(F->getContext(), Attribute::NoSync)); 3536 return true; 3537 } 3538 3539 /// See AbstractAttribute::isValidIRPositionForInit 3540 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3541 if (!IRP.isFunctionScope() && 3542 !IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 3543 return false; 3544 return IRAttribute::isValidIRPositionForInit(A, IRP); 3545 } 3546 3547 /// Returns true if "nosync" is assumed. 3548 bool isAssumedNoSync() const { return getAssumed(); } 3549 3550 /// Returns true if "nosync" is known. 3551 bool isKnownNoSync() const { return getKnown(); } 3552 3553 /// Helper function used to determine whether an instruction is non-relaxed 3554 /// atomic. In other words, if an atomic instruction does not have unordered 3555 /// or monotonic ordering 3556 static bool isNonRelaxedAtomic(const Instruction *I); 3557 3558 /// Helper function specific for intrinsics which are potentially volatile. 3559 static bool isNoSyncIntrinsic(const Instruction *I); 3560 3561 /// Helper function to determine if \p CB is an aligned (GPU) barrier. Aligned 3562 /// barriers have to be executed by all threads. The flag \p ExecutedAligned 3563 /// indicates if the call is executed by all threads in a (thread) block in an 3564 /// aligned way. If that is the case, non-aligned barriers are effectively 3565 /// aligned barriers. 3566 static bool isAlignedBarrier(const CallBase &CB, bool ExecutedAligned); 3567 3568 /// Create an abstract attribute view for the position \p IRP. 3569 static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A); 3570 3571 /// See AbstractAttribute::getName() 3572 const std::string getName() const override { return "AANoSync"; } 3573 3574 /// See AbstractAttribute::getIdAddr() 3575 const char *getIdAddr() const override { return &ID; } 3576 3577 /// This function should return true if the type of the \p AA is AANoSync 3578 static bool classof(const AbstractAttribute *AA) { 3579 return (AA->getIdAddr() == &ID); 3580 } 3581 3582 /// Unique ID (due to the unique address) 3583 static const char ID; 3584 }; 3585 3586 /// An abstract interface for all nonnull attributes. 3587 struct AAMustProgress 3588 : public IRAttribute<Attribute::MustProgress, 3589 StateWrapper<BooleanState, AbstractAttribute>, 3590 AAMustProgress> { 3591 AAMustProgress(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3592 3593 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3594 Attribute::AttrKind ImpliedAttributeKind, 3595 bool IgnoreSubsumingPositions = false) { 3596 // Note: This is also run for non-IPO amendable functions. 3597 assert(ImpliedAttributeKind == Attribute::MustProgress); 3598 return A.hasAttr(IRP, {Attribute::MustProgress, Attribute::WillReturn}, 3599 IgnoreSubsumingPositions, Attribute::MustProgress); 3600 } 3601 3602 /// Return true if we assume that the underlying value is nonnull. 3603 bool isAssumedMustProgress() const { return getAssumed(); } 3604 3605 /// Return true if we know that underlying value is nonnull. 3606 bool isKnownMustProgress() const { return getKnown(); } 3607 3608 /// Create an abstract attribute view for the position \p IRP. 3609 static AAMustProgress &createForPosition(const IRPosition &IRP, 3610 Attributor &A); 3611 3612 /// See AbstractAttribute::getName() 3613 const std::string getName() const override { return "AAMustProgress"; } 3614 3615 /// See AbstractAttribute::getIdAddr() 3616 const char *getIdAddr() const override { return &ID; } 3617 3618 /// This function should return true if the type of the \p AA is 3619 /// AAMustProgress 3620 static bool classof(const AbstractAttribute *AA) { 3621 return (AA->getIdAddr() == &ID); 3622 } 3623 3624 /// Unique ID (due to the unique address) 3625 static const char ID; 3626 }; 3627 3628 /// An abstract interface for all nonnull attributes. 3629 struct AANonNull 3630 : public IRAttribute<Attribute::NonNull, 3631 StateWrapper<BooleanState, AbstractAttribute>, 3632 AANonNull> { 3633 AANonNull(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3634 3635 /// See AbstractAttribute::hasTrivialInitializer. 3636 static bool hasTrivialInitializer() { return false; } 3637 3638 /// See IRAttribute::isImpliedByUndef. 3639 /// Undef is not necessarily nonnull as nonnull + noundef would cause poison. 3640 /// Poison implies nonnull though. 3641 static bool isImpliedByUndef() { return false; } 3642 3643 /// See AbstractAttribute::isValidIRPositionForInit 3644 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3645 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 3646 return false; 3647 return IRAttribute::isValidIRPositionForInit(A, IRP); 3648 } 3649 3650 /// See AbstractAttribute::isImpliedByIR(...). 3651 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3652 Attribute::AttrKind ImpliedAttributeKind, 3653 bool IgnoreSubsumingPositions = false); 3654 3655 /// Return true if we assume that the underlying value is nonnull. 3656 bool isAssumedNonNull() const { return getAssumed(); } 3657 3658 /// Return true if we know that underlying value is nonnull. 3659 bool isKnownNonNull() const { return getKnown(); } 3660 3661 /// Create an abstract attribute view for the position \p IRP. 3662 static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A); 3663 3664 /// See AbstractAttribute::getName() 3665 const std::string getName() const override { return "AANonNull"; } 3666 3667 /// See AbstractAttribute::getIdAddr() 3668 const char *getIdAddr() const override { return &ID; } 3669 3670 /// This function should return true if the type of the \p AA is AANonNull 3671 static bool classof(const AbstractAttribute *AA) { 3672 return (AA->getIdAddr() == &ID); 3673 } 3674 3675 /// Unique ID (due to the unique address) 3676 static const char ID; 3677 }; 3678 3679 /// An abstract attribute for norecurse. 3680 struct AANoRecurse 3681 : public IRAttribute<Attribute::NoRecurse, 3682 StateWrapper<BooleanState, AbstractAttribute>, 3683 AANoRecurse> { 3684 AANoRecurse(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3685 3686 /// Return true if "norecurse" is assumed. 3687 bool isAssumedNoRecurse() const { return getAssumed(); } 3688 3689 /// Return true if "norecurse" is known. 3690 bool isKnownNoRecurse() const { return getKnown(); } 3691 3692 /// Create an abstract attribute view for the position \p IRP. 3693 static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A); 3694 3695 /// See AbstractAttribute::getName() 3696 const std::string getName() const override { return "AANoRecurse"; } 3697 3698 /// See AbstractAttribute::getIdAddr() 3699 const char *getIdAddr() const override { return &ID; } 3700 3701 /// This function should return true if the type of the \p AA is AANoRecurse 3702 static bool classof(const AbstractAttribute *AA) { 3703 return (AA->getIdAddr() == &ID); 3704 } 3705 3706 /// Unique ID (due to the unique address) 3707 static const char ID; 3708 }; 3709 3710 /// An abstract attribute for willreturn. 3711 struct AAWillReturn 3712 : public IRAttribute<Attribute::WillReturn, 3713 StateWrapper<BooleanState, AbstractAttribute>, 3714 AAWillReturn> { 3715 AAWillReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3716 3717 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3718 Attribute::AttrKind ImpliedAttributeKind, 3719 bool IgnoreSubsumingPositions = false) { 3720 // Note: This is also run for non-IPO amendable functions. 3721 assert(ImpliedAttributeKind == Attribute::WillReturn); 3722 if (IRAttribute::isImpliedByIR(A, IRP, ImpliedAttributeKind, 3723 IgnoreSubsumingPositions)) 3724 return true; 3725 if (!isImpliedByMustprogressAndReadonly(A, IRP)) 3726 return false; 3727 A.manifestAttrs(IRP, Attribute::get(IRP.getAnchorValue().getContext(), 3728 Attribute::WillReturn)); 3729 return true; 3730 } 3731 3732 /// Check for `mustprogress` and `readonly` as they imply `willreturn`. 3733 static bool isImpliedByMustprogressAndReadonly(Attributor &A, 3734 const IRPosition &IRP) { 3735 // Check for `mustprogress` in the scope and the associated function which 3736 // might be different if this is a call site. 3737 if (!A.hasAttr(IRP, {Attribute::MustProgress})) 3738 return false; 3739 3740 SmallVector<Attribute, 2> Attrs; 3741 A.getAttrs(IRP, {Attribute::Memory}, Attrs, 3742 /* IgnoreSubsumingPositions */ false); 3743 3744 MemoryEffects ME = MemoryEffects::unknown(); 3745 for (const Attribute &Attr : Attrs) 3746 ME &= Attr.getMemoryEffects(); 3747 return ME.onlyReadsMemory(); 3748 } 3749 3750 /// Return true if "willreturn" is assumed. 3751 bool isAssumedWillReturn() const { return getAssumed(); } 3752 3753 /// Return true if "willreturn" is known. 3754 bool isKnownWillReturn() const { return getKnown(); } 3755 3756 /// Create an abstract attribute view for the position \p IRP. 3757 static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A); 3758 3759 /// See AbstractAttribute::getName() 3760 const std::string getName() const override { return "AAWillReturn"; } 3761 3762 /// See AbstractAttribute::getIdAddr() 3763 const char *getIdAddr() const override { return &ID; } 3764 3765 /// This function should return true if the type of the \p AA is AAWillReturn 3766 static bool classof(const AbstractAttribute *AA) { 3767 return (AA->getIdAddr() == &ID); 3768 } 3769 3770 /// Unique ID (due to the unique address) 3771 static const char ID; 3772 }; 3773 3774 /// An abstract attribute for undefined behavior. 3775 struct AAUndefinedBehavior 3776 : public StateWrapper<BooleanState, AbstractAttribute> { 3777 using Base = StateWrapper<BooleanState, AbstractAttribute>; 3778 AAUndefinedBehavior(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 3779 3780 /// Return true if "undefined behavior" is assumed. 3781 bool isAssumedToCauseUB() const { return getAssumed(); } 3782 3783 /// Return true if "undefined behavior" is assumed for a specific instruction. 3784 virtual bool isAssumedToCauseUB(Instruction *I) const = 0; 3785 3786 /// Return true if "undefined behavior" is known. 3787 bool isKnownToCauseUB() const { return getKnown(); } 3788 3789 /// Return true if "undefined behavior" is known for a specific instruction. 3790 virtual bool isKnownToCauseUB(Instruction *I) const = 0; 3791 3792 /// Create an abstract attribute view for the position \p IRP. 3793 static AAUndefinedBehavior &createForPosition(const IRPosition &IRP, 3794 Attributor &A); 3795 3796 /// See AbstractAttribute::getName() 3797 const std::string getName() const override { return "AAUndefinedBehavior"; } 3798 3799 /// See AbstractAttribute::getIdAddr() 3800 const char *getIdAddr() const override { return &ID; } 3801 3802 /// This function should return true if the type of the \p AA is 3803 /// AAUndefineBehavior 3804 static bool classof(const AbstractAttribute *AA) { 3805 return (AA->getIdAddr() == &ID); 3806 } 3807 3808 /// Unique ID (due to the unique address) 3809 static const char ID; 3810 }; 3811 3812 /// An abstract interface to determine reachability of point A to B. 3813 struct AAIntraFnReachability 3814 : public StateWrapper<BooleanState, AbstractAttribute> { 3815 using Base = StateWrapper<BooleanState, AbstractAttribute>; 3816 AAIntraFnReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 3817 3818 /// Returns true if 'From' instruction is assumed to reach, 'To' instruction. 3819 /// Users should provide two positions they are interested in, and the class 3820 /// determines (and caches) reachability. 3821 virtual bool isAssumedReachable( 3822 Attributor &A, const Instruction &From, const Instruction &To, 3823 const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0; 3824 3825 /// Create an abstract attribute view for the position \p IRP. 3826 static AAIntraFnReachability &createForPosition(const IRPosition &IRP, 3827 Attributor &A); 3828 3829 /// See AbstractAttribute::getName() 3830 const std::string getName() const override { return "AAIntraFnReachability"; } 3831 3832 /// See AbstractAttribute::getIdAddr() 3833 const char *getIdAddr() const override { return &ID; } 3834 3835 /// This function should return true if the type of the \p AA is 3836 /// AAIntraFnReachability 3837 static bool classof(const AbstractAttribute *AA) { 3838 return (AA->getIdAddr() == &ID); 3839 } 3840 3841 /// Unique ID (due to the unique address) 3842 static const char ID; 3843 }; 3844 3845 /// An abstract interface for all noalias attributes. 3846 struct AANoAlias 3847 : public IRAttribute<Attribute::NoAlias, 3848 StateWrapper<BooleanState, AbstractAttribute>, 3849 AANoAlias> { 3850 AANoAlias(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3851 3852 /// See AbstractAttribute::isValidIRPositionForInit 3853 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3854 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 3855 return false; 3856 return IRAttribute::isValidIRPositionForInit(A, IRP); 3857 } 3858 3859 /// See IRAttribute::isImpliedByIR 3860 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3861 Attribute::AttrKind ImpliedAttributeKind, 3862 bool IgnoreSubsumingPositions = false); 3863 3864 /// See AbstractAttribute::requiresCallersForArgOrFunction 3865 static bool requiresCallersForArgOrFunction() { return true; } 3866 3867 /// Return true if we assume that the underlying value is alias. 3868 bool isAssumedNoAlias() const { return getAssumed(); } 3869 3870 /// Return true if we know that underlying value is noalias. 3871 bool isKnownNoAlias() const { return getKnown(); } 3872 3873 /// Create an abstract attribute view for the position \p IRP. 3874 static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A); 3875 3876 /// See AbstractAttribute::getName() 3877 const std::string getName() const override { return "AANoAlias"; } 3878 3879 /// See AbstractAttribute::getIdAddr() 3880 const char *getIdAddr() const override { return &ID; } 3881 3882 /// This function should return true if the type of the \p AA is AANoAlias 3883 static bool classof(const AbstractAttribute *AA) { 3884 return (AA->getIdAddr() == &ID); 3885 } 3886 3887 /// Unique ID (due to the unique address) 3888 static const char ID; 3889 }; 3890 3891 /// An AbstractAttribute for nofree. 3892 struct AANoFree 3893 : public IRAttribute<Attribute::NoFree, 3894 StateWrapper<BooleanState, AbstractAttribute>, 3895 AANoFree> { 3896 AANoFree(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3897 3898 /// See IRAttribute::isImpliedByIR 3899 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 3900 Attribute::AttrKind ImpliedAttributeKind, 3901 bool IgnoreSubsumingPositions = false) { 3902 // Note: This is also run for non-IPO amendable functions. 3903 assert(ImpliedAttributeKind == Attribute::NoFree); 3904 return A.hasAttr( 3905 IRP, {Attribute::ReadNone, Attribute::ReadOnly, Attribute::NoFree}, 3906 IgnoreSubsumingPositions, Attribute::NoFree); 3907 } 3908 3909 /// See AbstractAttribute::isValidIRPositionForInit 3910 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3911 if (!IRP.isFunctionScope() && 3912 !IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 3913 return false; 3914 return IRAttribute::isValidIRPositionForInit(A, IRP); 3915 } 3916 3917 /// Return true if "nofree" is assumed. 3918 bool isAssumedNoFree() const { return getAssumed(); } 3919 3920 /// Return true if "nofree" is known. 3921 bool isKnownNoFree() const { return getKnown(); } 3922 3923 /// Create an abstract attribute view for the position \p IRP. 3924 static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A); 3925 3926 /// See AbstractAttribute::getName() 3927 const std::string getName() const override { return "AANoFree"; } 3928 3929 /// See AbstractAttribute::getIdAddr() 3930 const char *getIdAddr() const override { return &ID; } 3931 3932 /// This function should return true if the type of the \p AA is AANoFree 3933 static bool classof(const AbstractAttribute *AA) { 3934 return (AA->getIdAddr() == &ID); 3935 } 3936 3937 /// Unique ID (due to the unique address) 3938 static const char ID; 3939 }; 3940 3941 /// An AbstractAttribute for noreturn. 3942 struct AANoReturn 3943 : public IRAttribute<Attribute::NoReturn, 3944 StateWrapper<BooleanState, AbstractAttribute>, 3945 AANoReturn> { 3946 AANoReturn(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 3947 3948 /// Return true if the underlying object is assumed to never return. 3949 bool isAssumedNoReturn() const { return getAssumed(); } 3950 3951 /// Return true if the underlying object is known to never return. 3952 bool isKnownNoReturn() const { return getKnown(); } 3953 3954 /// Create an abstract attribute view for the position \p IRP. 3955 static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A); 3956 3957 /// See AbstractAttribute::getName() 3958 const std::string getName() const override { return "AANoReturn"; } 3959 3960 /// See AbstractAttribute::getIdAddr() 3961 const char *getIdAddr() const override { return &ID; } 3962 3963 /// This function should return true if the type of the \p AA is AANoReturn 3964 static bool classof(const AbstractAttribute *AA) { 3965 return (AA->getIdAddr() == &ID); 3966 } 3967 3968 /// Unique ID (due to the unique address) 3969 static const char ID; 3970 }; 3971 3972 /// An abstract interface for liveness abstract attribute. 3973 struct AAIsDead 3974 : public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> { 3975 using Base = StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute>; 3976 AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 3977 3978 /// See AbstractAttribute::isValidIRPositionForInit 3979 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 3980 if (IRP.getPositionKind() == IRPosition::IRP_FUNCTION) 3981 return isa<Function>(IRP.getAnchorValue()) && 3982 !cast<Function>(IRP.getAnchorValue()).isDeclaration(); 3983 return true; 3984 } 3985 3986 /// State encoding bits. A set bit in the state means the property holds. 3987 enum { 3988 HAS_NO_EFFECT = 1 << 0, 3989 IS_REMOVABLE = 1 << 1, 3990 3991 IS_DEAD = HAS_NO_EFFECT | IS_REMOVABLE, 3992 }; 3993 static_assert(IS_DEAD == getBestState(), "Unexpected BEST_STATE value"); 3994 3995 protected: 3996 /// The query functions are protected such that other attributes need to go 3997 /// through the Attributor interfaces: `Attributor::isAssumedDead(...)` 3998 3999 /// Returns true if the underlying value is assumed dead. 4000 virtual bool isAssumedDead() const = 0; 4001 4002 /// Returns true if the underlying value is known dead. 4003 virtual bool isKnownDead() const = 0; 4004 4005 /// Returns true if \p BB is known dead. 4006 virtual bool isKnownDead(const BasicBlock *BB) const = 0; 4007 4008 /// Returns true if \p I is assumed dead. 4009 virtual bool isAssumedDead(const Instruction *I) const = 0; 4010 4011 /// Returns true if \p I is known dead. 4012 virtual bool isKnownDead(const Instruction *I) const = 0; 4013 4014 /// Return true if the underlying value is a store that is known to be 4015 /// removable. This is different from dead stores as the removable store 4016 /// can have an effect on live values, especially loads, but that effect 4017 /// is propagated which allows us to remove the store in turn. 4018 virtual bool isRemovableStore() const { return false; } 4019 4020 /// This method is used to check if at least one instruction in a collection 4021 /// of instructions is live. 4022 template <typename T> bool isLiveInstSet(T begin, T end) const { 4023 for (const auto &I : llvm::make_range(begin, end)) { 4024 assert(I->getFunction() == getIRPosition().getAssociatedFunction() && 4025 "Instruction must be in the same anchor scope function."); 4026 4027 if (!isAssumedDead(I)) 4028 return true; 4029 } 4030 4031 return false; 4032 } 4033 4034 public: 4035 /// Create an abstract attribute view for the position \p IRP. 4036 static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A); 4037 4038 /// Determine if \p F might catch asynchronous exceptions. 4039 static bool mayCatchAsynchronousExceptions(const Function &F) { 4040 return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F); 4041 } 4042 4043 /// Returns true if \p BB is assumed dead. 4044 virtual bool isAssumedDead(const BasicBlock *BB) const = 0; 4045 4046 /// Return if the edge from \p From BB to \p To BB is assumed dead. 4047 /// This is specifically useful in AAReachability. 4048 virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const { 4049 return false; 4050 } 4051 4052 /// See AbstractAttribute::getName() 4053 const std::string getName() const override { return "AAIsDead"; } 4054 4055 /// See AbstractAttribute::getIdAddr() 4056 const char *getIdAddr() const override { return &ID; } 4057 4058 /// This function should return true if the type of the \p AA is AAIsDead 4059 static bool classof(const AbstractAttribute *AA) { 4060 return (AA->getIdAddr() == &ID); 4061 } 4062 4063 /// Unique ID (due to the unique address) 4064 static const char ID; 4065 4066 friend struct Attributor; 4067 }; 4068 4069 /// State for dereferenceable attribute 4070 struct DerefState : AbstractState { 4071 4072 static DerefState getBestState() { return DerefState(); } 4073 static DerefState getBestState(const DerefState &) { return getBestState(); } 4074 4075 /// Return the worst possible representable state. 4076 static DerefState getWorstState() { 4077 DerefState DS; 4078 DS.indicatePessimisticFixpoint(); 4079 return DS; 4080 } 4081 static DerefState getWorstState(const DerefState &) { 4082 return getWorstState(); 4083 } 4084 4085 /// State representing for dereferenceable bytes. 4086 IncIntegerState<> DerefBytesState; 4087 4088 /// Map representing for accessed memory offsets and sizes. 4089 /// A key is Offset and a value is size. 4090 /// If there is a load/store instruction something like, 4091 /// p[offset] = v; 4092 /// (offset, sizeof(v)) will be inserted to this map. 4093 /// std::map is used because we want to iterate keys in ascending order. 4094 std::map<int64_t, uint64_t> AccessedBytesMap; 4095 4096 /// Helper function to calculate dereferenceable bytes from current known 4097 /// bytes and accessed bytes. 4098 /// 4099 /// int f(int *A){ 4100 /// *A = 0; 4101 /// *(A+2) = 2; 4102 /// *(A+1) = 1; 4103 /// *(A+10) = 10; 4104 /// } 4105 /// ``` 4106 /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`. 4107 /// AccessedBytesMap is std::map so it is iterated in accending order on 4108 /// key(Offset). So KnownBytes will be updated like this: 4109 /// 4110 /// |Access | KnownBytes 4111 /// |(0, 4)| 0 -> 4 4112 /// |(4, 4)| 4 -> 8 4113 /// |(8, 4)| 8 -> 12 4114 /// |(40, 4) | 12 (break) 4115 void computeKnownDerefBytesFromAccessedMap() { 4116 int64_t KnownBytes = DerefBytesState.getKnown(); 4117 for (auto &Access : AccessedBytesMap) { 4118 if (KnownBytes < Access.first) 4119 break; 4120 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second); 4121 } 4122 4123 DerefBytesState.takeKnownMaximum(KnownBytes); 4124 } 4125 4126 /// State representing that whether the value is globaly dereferenceable. 4127 BooleanState GlobalState; 4128 4129 /// See AbstractState::isValidState() 4130 bool isValidState() const override { return DerefBytesState.isValidState(); } 4131 4132 /// See AbstractState::isAtFixpoint() 4133 bool isAtFixpoint() const override { 4134 return !isValidState() || 4135 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint()); 4136 } 4137 4138 /// See AbstractState::indicateOptimisticFixpoint(...) 4139 ChangeStatus indicateOptimisticFixpoint() override { 4140 DerefBytesState.indicateOptimisticFixpoint(); 4141 GlobalState.indicateOptimisticFixpoint(); 4142 return ChangeStatus::UNCHANGED; 4143 } 4144 4145 /// See AbstractState::indicatePessimisticFixpoint(...) 4146 ChangeStatus indicatePessimisticFixpoint() override { 4147 DerefBytesState.indicatePessimisticFixpoint(); 4148 GlobalState.indicatePessimisticFixpoint(); 4149 return ChangeStatus::CHANGED; 4150 } 4151 4152 /// Update known dereferenceable bytes. 4153 void takeKnownDerefBytesMaximum(uint64_t Bytes) { 4154 DerefBytesState.takeKnownMaximum(Bytes); 4155 4156 // Known bytes might increase. 4157 computeKnownDerefBytesFromAccessedMap(); 4158 } 4159 4160 /// Update assumed dereferenceable bytes. 4161 void takeAssumedDerefBytesMinimum(uint64_t Bytes) { 4162 DerefBytesState.takeAssumedMinimum(Bytes); 4163 } 4164 4165 /// Add accessed bytes to the map. 4166 void addAccessedBytes(int64_t Offset, uint64_t Size) { 4167 uint64_t &AccessedBytes = AccessedBytesMap[Offset]; 4168 AccessedBytes = std::max(AccessedBytes, Size); 4169 4170 // Known bytes might increase. 4171 computeKnownDerefBytesFromAccessedMap(); 4172 } 4173 4174 /// Equality for DerefState. 4175 bool operator==(const DerefState &R) const { 4176 return this->DerefBytesState == R.DerefBytesState && 4177 this->GlobalState == R.GlobalState; 4178 } 4179 4180 /// Inequality for DerefState. 4181 bool operator!=(const DerefState &R) const { return !(*this == R); } 4182 4183 /// See IntegerStateBase::operator^= 4184 DerefState operator^=(const DerefState &R) { 4185 DerefBytesState ^= R.DerefBytesState; 4186 GlobalState ^= R.GlobalState; 4187 return *this; 4188 } 4189 4190 /// See IntegerStateBase::operator+= 4191 DerefState operator+=(const DerefState &R) { 4192 DerefBytesState += R.DerefBytesState; 4193 GlobalState += R.GlobalState; 4194 return *this; 4195 } 4196 4197 /// See IntegerStateBase::operator&= 4198 DerefState operator&=(const DerefState &R) { 4199 DerefBytesState &= R.DerefBytesState; 4200 GlobalState &= R.GlobalState; 4201 return *this; 4202 } 4203 4204 /// See IntegerStateBase::operator|= 4205 DerefState operator|=(const DerefState &R) { 4206 DerefBytesState |= R.DerefBytesState; 4207 GlobalState |= R.GlobalState; 4208 return *this; 4209 } 4210 }; 4211 4212 /// An abstract interface for all dereferenceable attribute. 4213 struct AADereferenceable 4214 : public IRAttribute<Attribute::Dereferenceable, 4215 StateWrapper<DerefState, AbstractAttribute>, 4216 AADereferenceable> { 4217 AADereferenceable(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 4218 4219 /// See AbstractAttribute::isValidIRPositionForInit 4220 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4221 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4222 return false; 4223 return IRAttribute::isValidIRPositionForInit(A, IRP); 4224 } 4225 4226 /// Return true if we assume that underlying value is 4227 /// dereferenceable(_or_null) globally. 4228 bool isAssumedGlobal() const { return GlobalState.getAssumed(); } 4229 4230 /// Return true if we know that underlying value is 4231 /// dereferenceable(_or_null) globally. 4232 bool isKnownGlobal() const { return GlobalState.getKnown(); } 4233 4234 /// Return assumed dereferenceable bytes. 4235 uint32_t getAssumedDereferenceableBytes() const { 4236 return DerefBytesState.getAssumed(); 4237 } 4238 4239 /// Return known dereferenceable bytes. 4240 uint32_t getKnownDereferenceableBytes() const { 4241 return DerefBytesState.getKnown(); 4242 } 4243 4244 /// Create an abstract attribute view for the position \p IRP. 4245 static AADereferenceable &createForPosition(const IRPosition &IRP, 4246 Attributor &A); 4247 4248 /// See AbstractAttribute::getName() 4249 const std::string getName() const override { return "AADereferenceable"; } 4250 4251 /// See AbstractAttribute::getIdAddr() 4252 const char *getIdAddr() const override { return &ID; } 4253 4254 /// This function should return true if the type of the \p AA is 4255 /// AADereferenceable 4256 static bool classof(const AbstractAttribute *AA) { 4257 return (AA->getIdAddr() == &ID); 4258 } 4259 4260 /// Unique ID (due to the unique address) 4261 static const char ID; 4262 }; 4263 4264 using AAAlignmentStateType = 4265 IncIntegerState<uint64_t, Value::MaximumAlignment, 1>; 4266 /// An abstract interface for all align attributes. 4267 struct AAAlign 4268 : public IRAttribute<Attribute::Alignment, 4269 StateWrapper<AAAlignmentStateType, AbstractAttribute>, 4270 AAAlign> { 4271 AAAlign(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 4272 4273 /// See AbstractAttribute::isValidIRPositionForInit 4274 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4275 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4276 return false; 4277 return IRAttribute::isValidIRPositionForInit(A, IRP); 4278 } 4279 4280 /// Return assumed alignment. 4281 Align getAssumedAlign() const { return Align(getAssumed()); } 4282 4283 /// Return known alignment. 4284 Align getKnownAlign() const { return Align(getKnown()); } 4285 4286 /// See AbstractAttribute::getName() 4287 const std::string getName() const override { return "AAAlign"; } 4288 4289 /// See AbstractAttribute::getIdAddr() 4290 const char *getIdAddr() const override { return &ID; } 4291 4292 /// This function should return true if the type of the \p AA is AAAlign 4293 static bool classof(const AbstractAttribute *AA) { 4294 return (AA->getIdAddr() == &ID); 4295 } 4296 4297 /// Create an abstract attribute view for the position \p IRP. 4298 static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A); 4299 4300 /// Unique ID (due to the unique address) 4301 static const char ID; 4302 }; 4303 4304 /// An abstract interface to track if a value leaves it's defining function 4305 /// instance. 4306 /// TODO: We should make it a ternary AA tracking uniqueness, and uniqueness 4307 /// wrt. the Attributor analysis separately. 4308 struct AAInstanceInfo : public StateWrapper<BooleanState, AbstractAttribute> { 4309 AAInstanceInfo(const IRPosition &IRP, Attributor &A) 4310 : StateWrapper<BooleanState, AbstractAttribute>(IRP) {} 4311 4312 /// Return true if we know that the underlying value is unique in its scope 4313 /// wrt. the Attributor analysis. That means it might not be unique but we can 4314 /// still use pointer equality without risking to represent two instances with 4315 /// one `llvm::Value`. 4316 bool isKnownUniqueForAnalysis() const { return isKnown(); } 4317 4318 /// Return true if we assume that the underlying value is unique in its scope 4319 /// wrt. the Attributor analysis. That means it might not be unique but we can 4320 /// still use pointer equality without risking to represent two instances with 4321 /// one `llvm::Value`. 4322 bool isAssumedUniqueForAnalysis() const { return isAssumed(); } 4323 4324 /// Create an abstract attribute view for the position \p IRP. 4325 static AAInstanceInfo &createForPosition(const IRPosition &IRP, 4326 Attributor &A); 4327 4328 /// See AbstractAttribute::getName() 4329 const std::string getName() const override { return "AAInstanceInfo"; } 4330 4331 /// See AbstractAttribute::getIdAddr() 4332 const char *getIdAddr() const override { return &ID; } 4333 4334 /// This function should return true if the type of the \p AA is 4335 /// AAInstanceInfo 4336 static bool classof(const AbstractAttribute *AA) { 4337 return (AA->getIdAddr() == &ID); 4338 } 4339 4340 /// Unique ID (due to the unique address) 4341 static const char ID; 4342 }; 4343 4344 /// An abstract interface for all nocapture attributes. 4345 struct AANoCapture 4346 : public IRAttribute< 4347 Attribute::NoCapture, 4348 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>, 4349 AANoCapture> { 4350 AANoCapture(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 4351 4352 /// See IRAttribute::isImpliedByIR 4353 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 4354 Attribute::AttrKind ImpliedAttributeKind, 4355 bool IgnoreSubsumingPositions = false); 4356 4357 /// Update \p State according to the capture capabilities of \p F for position 4358 /// \p IRP. 4359 static void determineFunctionCaptureCapabilities(const IRPosition &IRP, 4360 const Function &F, 4361 BitIntegerState &State); 4362 4363 /// See AbstractAttribute::isValidIRPositionForInit 4364 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4365 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4366 return false; 4367 return IRAttribute::isValidIRPositionForInit(A, IRP); 4368 } 4369 4370 /// State encoding bits. A set bit in the state means the property holds. 4371 /// NO_CAPTURE is the best possible state, 0 the worst possible state. 4372 enum { 4373 NOT_CAPTURED_IN_MEM = 1 << 0, 4374 NOT_CAPTURED_IN_INT = 1 << 1, 4375 NOT_CAPTURED_IN_RET = 1 << 2, 4376 4377 /// If we do not capture the value in memory or through integers we can only 4378 /// communicate it back as a derived pointer. 4379 NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT, 4380 4381 /// If we do not capture the value in memory, through integers, or as a 4382 /// derived pointer we know it is not captured. 4383 NO_CAPTURE = 4384 NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET, 4385 }; 4386 4387 /// Return true if we know that the underlying value is not captured in its 4388 /// respective scope. 4389 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); } 4390 4391 /// Return true if we assume that the underlying value is not captured in its 4392 /// respective scope. 4393 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); } 4394 4395 /// Return true if we know that the underlying value is not captured in its 4396 /// respective scope but we allow it to escape through a "return". 4397 bool isKnownNoCaptureMaybeReturned() const { 4398 return isKnown(NO_CAPTURE_MAYBE_RETURNED); 4399 } 4400 4401 /// Return true if we assume that the underlying value is not captured in its 4402 /// respective scope but we allow it to escape through a "return". 4403 bool isAssumedNoCaptureMaybeReturned() const { 4404 return isAssumed(NO_CAPTURE_MAYBE_RETURNED); 4405 } 4406 4407 /// Create an abstract attribute view for the position \p IRP. 4408 static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A); 4409 4410 /// See AbstractAttribute::getName() 4411 const std::string getName() const override { return "AANoCapture"; } 4412 4413 /// See AbstractAttribute::getIdAddr() 4414 const char *getIdAddr() const override { return &ID; } 4415 4416 /// This function should return true if the type of the \p AA is AANoCapture 4417 static bool classof(const AbstractAttribute *AA) { 4418 return (AA->getIdAddr() == &ID); 4419 } 4420 4421 /// Unique ID (due to the unique address) 4422 static const char ID; 4423 }; 4424 4425 struct ValueSimplifyStateType : public AbstractState { 4426 4427 ValueSimplifyStateType(Type *Ty) : Ty(Ty) {} 4428 4429 static ValueSimplifyStateType getBestState(Type *Ty) { 4430 return ValueSimplifyStateType(Ty); 4431 } 4432 static ValueSimplifyStateType getBestState(const ValueSimplifyStateType &VS) { 4433 return getBestState(VS.Ty); 4434 } 4435 4436 /// Return the worst possible representable state. 4437 static ValueSimplifyStateType getWorstState(Type *Ty) { 4438 ValueSimplifyStateType DS(Ty); 4439 DS.indicatePessimisticFixpoint(); 4440 return DS; 4441 } 4442 static ValueSimplifyStateType 4443 getWorstState(const ValueSimplifyStateType &VS) { 4444 return getWorstState(VS.Ty); 4445 } 4446 4447 /// See AbstractState::isValidState(...) 4448 bool isValidState() const override { return BS.isValidState(); } 4449 4450 /// See AbstractState::isAtFixpoint(...) 4451 bool isAtFixpoint() const override { return BS.isAtFixpoint(); } 4452 4453 /// Return the assumed state encoding. 4454 ValueSimplifyStateType getAssumed() { return *this; } 4455 const ValueSimplifyStateType &getAssumed() const { return *this; } 4456 4457 /// See AbstractState::indicatePessimisticFixpoint(...) 4458 ChangeStatus indicatePessimisticFixpoint() override { 4459 return BS.indicatePessimisticFixpoint(); 4460 } 4461 4462 /// See AbstractState::indicateOptimisticFixpoint(...) 4463 ChangeStatus indicateOptimisticFixpoint() override { 4464 return BS.indicateOptimisticFixpoint(); 4465 } 4466 4467 /// "Clamp" this state with \p PVS. 4468 ValueSimplifyStateType operator^=(const ValueSimplifyStateType &VS) { 4469 BS ^= VS.BS; 4470 unionAssumed(VS.SimplifiedAssociatedValue); 4471 return *this; 4472 } 4473 4474 bool operator==(const ValueSimplifyStateType &RHS) const { 4475 if (isValidState() != RHS.isValidState()) 4476 return false; 4477 if (!isValidState() && !RHS.isValidState()) 4478 return true; 4479 return SimplifiedAssociatedValue == RHS.SimplifiedAssociatedValue; 4480 } 4481 4482 protected: 4483 /// The type of the original value. 4484 Type *Ty; 4485 4486 /// Merge \p Other into the currently assumed simplified value 4487 bool unionAssumed(std::optional<Value *> Other); 4488 4489 /// Helper to track validity and fixpoint 4490 BooleanState BS; 4491 4492 /// An assumed simplified value. Initially, it is set to std::nullopt, which 4493 /// means that the value is not clear under current assumption. If in the 4494 /// pessimistic state, getAssumedSimplifiedValue doesn't return this value but 4495 /// returns orignal associated value. 4496 std::optional<Value *> SimplifiedAssociatedValue; 4497 }; 4498 4499 /// An abstract interface for value simplify abstract attribute. 4500 struct AAValueSimplify 4501 : public StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *> { 4502 using Base = StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *>; 4503 AAValueSimplify(const IRPosition &IRP, Attributor &A) 4504 : Base(IRP, IRP.getAssociatedType()) {} 4505 4506 /// Create an abstract attribute view for the position \p IRP. 4507 static AAValueSimplify &createForPosition(const IRPosition &IRP, 4508 Attributor &A); 4509 4510 /// See AbstractAttribute::getName() 4511 const std::string getName() const override { return "AAValueSimplify"; } 4512 4513 /// See AbstractAttribute::getIdAddr() 4514 const char *getIdAddr() const override { return &ID; } 4515 4516 /// This function should return true if the type of the \p AA is 4517 /// AAValueSimplify 4518 static bool classof(const AbstractAttribute *AA) { 4519 return (AA->getIdAddr() == &ID); 4520 } 4521 4522 /// Unique ID (due to the unique address) 4523 static const char ID; 4524 4525 private: 4526 /// Return an assumed simplified value if a single candidate is found. If 4527 /// there cannot be one, return original value. If it is not clear yet, return 4528 /// std::nullopt. 4529 /// 4530 /// Use `Attributor::getAssumedSimplified` for value simplification. 4531 virtual std::optional<Value *> 4532 getAssumedSimplifiedValue(Attributor &A) const = 0; 4533 4534 friend struct Attributor; 4535 }; 4536 4537 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute> { 4538 using Base = StateWrapper<BooleanState, AbstractAttribute>; 4539 AAHeapToStack(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 4540 4541 /// Returns true if HeapToStack conversion is assumed to be possible. 4542 virtual bool isAssumedHeapToStack(const CallBase &CB) const = 0; 4543 4544 /// Returns true if HeapToStack conversion is assumed and the CB is a 4545 /// callsite to a free operation to be removed. 4546 virtual bool isAssumedHeapToStackRemovedFree(CallBase &CB) const = 0; 4547 4548 /// Create an abstract attribute view for the position \p IRP. 4549 static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A); 4550 4551 /// See AbstractAttribute::getName() 4552 const std::string getName() const override { return "AAHeapToStack"; } 4553 4554 /// See AbstractAttribute::getIdAddr() 4555 const char *getIdAddr() const override { return &ID; } 4556 4557 /// This function should return true if the type of the \p AA is AAHeapToStack 4558 static bool classof(const AbstractAttribute *AA) { 4559 return (AA->getIdAddr() == &ID); 4560 } 4561 4562 /// Unique ID (due to the unique address) 4563 static const char ID; 4564 }; 4565 4566 /// An abstract interface for privatizability. 4567 /// 4568 /// A pointer is privatizable if it can be replaced by a new, private one. 4569 /// Privatizing pointer reduces the use count, interaction between unrelated 4570 /// code parts. 4571 /// 4572 /// In order for a pointer to be privatizable its value cannot be observed 4573 /// (=nocapture), it is (for now) not written (=readonly & noalias), we know 4574 /// what values are necessary to make the private copy look like the original 4575 /// one, and the values we need can be loaded (=dereferenceable). 4576 struct AAPrivatizablePtr 4577 : public StateWrapper<BooleanState, AbstractAttribute> { 4578 using Base = StateWrapper<BooleanState, AbstractAttribute>; 4579 AAPrivatizablePtr(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 4580 4581 /// See AbstractAttribute::isValidIRPositionForInit 4582 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4583 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4584 return false; 4585 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 4586 } 4587 4588 /// Returns true if pointer privatization is assumed to be possible. 4589 bool isAssumedPrivatizablePtr() const { return getAssumed(); } 4590 4591 /// Returns true if pointer privatization is known to be possible. 4592 bool isKnownPrivatizablePtr() const { return getKnown(); } 4593 4594 /// See AbstractAttribute::requiresCallersForArgOrFunction 4595 static bool requiresCallersForArgOrFunction() { return true; } 4596 4597 /// Return the type we can choose for a private copy of the underlying 4598 /// value. std::nullopt means it is not clear yet, nullptr means there is 4599 /// none. 4600 virtual std::optional<Type *> getPrivatizableType() const = 0; 4601 4602 /// Create an abstract attribute view for the position \p IRP. 4603 static AAPrivatizablePtr &createForPosition(const IRPosition &IRP, 4604 Attributor &A); 4605 4606 /// See AbstractAttribute::getName() 4607 const std::string getName() const override { return "AAPrivatizablePtr"; } 4608 4609 /// See AbstractAttribute::getIdAddr() 4610 const char *getIdAddr() const override { return &ID; } 4611 4612 /// This function should return true if the type of the \p AA is 4613 /// AAPricatizablePtr 4614 static bool classof(const AbstractAttribute *AA) { 4615 return (AA->getIdAddr() == &ID); 4616 } 4617 4618 /// Unique ID (due to the unique address) 4619 static const char ID; 4620 }; 4621 4622 /// An abstract interface for memory access kind related attributes 4623 /// (readnone/readonly/writeonly). 4624 struct AAMemoryBehavior 4625 : public IRAttribute< 4626 Attribute::None, 4627 StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>, 4628 AAMemoryBehavior> { 4629 AAMemoryBehavior(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 4630 4631 /// See AbstractAttribute::hasTrivialInitializer. 4632 static bool hasTrivialInitializer() { return false; } 4633 4634 /// See AbstractAttribute::isValidIRPositionForInit 4635 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4636 if (!IRP.isFunctionScope() && 4637 !IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4638 return false; 4639 return IRAttribute::isValidIRPositionForInit(A, IRP); 4640 } 4641 4642 /// State encoding bits. A set bit in the state means the property holds. 4643 /// BEST_STATE is the best possible state, 0 the worst possible state. 4644 enum { 4645 NO_READS = 1 << 0, 4646 NO_WRITES = 1 << 1, 4647 NO_ACCESSES = NO_READS | NO_WRITES, 4648 4649 BEST_STATE = NO_ACCESSES, 4650 }; 4651 static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value"); 4652 4653 /// Return true if we know that the underlying value is not read or accessed 4654 /// in its respective scope. 4655 bool isKnownReadNone() const { return isKnown(NO_ACCESSES); } 4656 4657 /// Return true if we assume that the underlying value is not read or accessed 4658 /// in its respective scope. 4659 bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); } 4660 4661 /// Return true if we know that the underlying value is not accessed 4662 /// (=written) in its respective scope. 4663 bool isKnownReadOnly() const { return isKnown(NO_WRITES); } 4664 4665 /// Return true if we assume that the underlying value is not accessed 4666 /// (=written) in its respective scope. 4667 bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); } 4668 4669 /// Return true if we know that the underlying value is not read in its 4670 /// respective scope. 4671 bool isKnownWriteOnly() const { return isKnown(NO_READS); } 4672 4673 /// Return true if we assume that the underlying value is not read in its 4674 /// respective scope. 4675 bool isAssumedWriteOnly() const { return isAssumed(NO_READS); } 4676 4677 /// Create an abstract attribute view for the position \p IRP. 4678 static AAMemoryBehavior &createForPosition(const IRPosition &IRP, 4679 Attributor &A); 4680 4681 /// See AbstractAttribute::getName() 4682 const std::string getName() const override { return "AAMemoryBehavior"; } 4683 4684 /// See AbstractAttribute::getIdAddr() 4685 const char *getIdAddr() const override { return &ID; } 4686 4687 /// This function should return true if the type of the \p AA is 4688 /// AAMemoryBehavior 4689 static bool classof(const AbstractAttribute *AA) { 4690 return (AA->getIdAddr() == &ID); 4691 } 4692 4693 /// Unique ID (due to the unique address) 4694 static const char ID; 4695 }; 4696 4697 /// An abstract interface for all memory location attributes 4698 /// (readnone/argmemonly/inaccessiblememonly/inaccessibleorargmemonly). 4699 struct AAMemoryLocation 4700 : public IRAttribute< 4701 Attribute::None, 4702 StateWrapper<BitIntegerState<uint32_t, 511>, AbstractAttribute>, 4703 AAMemoryLocation> { 4704 using MemoryLocationsKind = StateType::base_t; 4705 4706 AAMemoryLocation(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 4707 4708 /// See AbstractAttribute::requiresCalleeForCallBase. 4709 static bool requiresCalleeForCallBase() { return true; } 4710 4711 /// See AbstractAttribute::hasTrivialInitializer. 4712 static bool hasTrivialInitializer() { return false; } 4713 4714 /// See AbstractAttribute::isValidIRPositionForInit 4715 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4716 if (!IRP.isFunctionScope() && 4717 !IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 4718 return false; 4719 return IRAttribute::isValidIRPositionForInit(A, IRP); 4720 } 4721 4722 /// Encoding of different locations that could be accessed by a memory 4723 /// access. 4724 enum { 4725 ALL_LOCATIONS = 0, 4726 NO_LOCAL_MEM = 1 << 0, 4727 NO_CONST_MEM = 1 << 1, 4728 NO_GLOBAL_INTERNAL_MEM = 1 << 2, 4729 NO_GLOBAL_EXTERNAL_MEM = 1 << 3, 4730 NO_GLOBAL_MEM = NO_GLOBAL_INTERNAL_MEM | NO_GLOBAL_EXTERNAL_MEM, 4731 NO_ARGUMENT_MEM = 1 << 4, 4732 NO_INACCESSIBLE_MEM = 1 << 5, 4733 NO_MALLOCED_MEM = 1 << 6, 4734 NO_UNKOWN_MEM = 1 << 7, 4735 NO_LOCATIONS = NO_LOCAL_MEM | NO_CONST_MEM | NO_GLOBAL_INTERNAL_MEM | 4736 NO_GLOBAL_EXTERNAL_MEM | NO_ARGUMENT_MEM | 4737 NO_INACCESSIBLE_MEM | NO_MALLOCED_MEM | NO_UNKOWN_MEM, 4738 4739 // Helper bit to track if we gave up or not. 4740 VALID_STATE = NO_LOCATIONS + 1, 4741 4742 BEST_STATE = NO_LOCATIONS | VALID_STATE, 4743 }; 4744 static_assert(BEST_STATE == getBestState(), "Unexpected BEST_STATE value"); 4745 4746 /// Return true if we know that the associated functions has no observable 4747 /// accesses. 4748 bool isKnownReadNone() const { return isKnown(NO_LOCATIONS); } 4749 4750 /// Return true if we assume that the associated functions has no observable 4751 /// accesses. 4752 bool isAssumedReadNone() const { 4753 return isAssumed(NO_LOCATIONS) || isAssumedStackOnly(); 4754 } 4755 4756 /// Return true if we know that the associated functions has at most 4757 /// local/stack accesses. 4758 bool isKnowStackOnly() const { 4759 return isKnown(inverseLocation(NO_LOCAL_MEM, true, true)); 4760 } 4761 4762 /// Return true if we assume that the associated functions has at most 4763 /// local/stack accesses. 4764 bool isAssumedStackOnly() const { 4765 return isAssumed(inverseLocation(NO_LOCAL_MEM, true, true)); 4766 } 4767 4768 /// Return true if we know that the underlying value will only access 4769 /// inaccesible memory only (see Attribute::InaccessibleMemOnly). 4770 bool isKnownInaccessibleMemOnly() const { 4771 return isKnown(inverseLocation(NO_INACCESSIBLE_MEM, true, true)); 4772 } 4773 4774 /// Return true if we assume that the underlying value will only access 4775 /// inaccesible memory only (see Attribute::InaccessibleMemOnly). 4776 bool isAssumedInaccessibleMemOnly() const { 4777 return isAssumed(inverseLocation(NO_INACCESSIBLE_MEM, true, true)); 4778 } 4779 4780 /// Return true if we know that the underlying value will only access 4781 /// argument pointees (see Attribute::ArgMemOnly). 4782 bool isKnownArgMemOnly() const { 4783 return isKnown(inverseLocation(NO_ARGUMENT_MEM, true, true)); 4784 } 4785 4786 /// Return true if we assume that the underlying value will only access 4787 /// argument pointees (see Attribute::ArgMemOnly). 4788 bool isAssumedArgMemOnly() const { 4789 return isAssumed(inverseLocation(NO_ARGUMENT_MEM, true, true)); 4790 } 4791 4792 /// Return true if we know that the underlying value will only access 4793 /// inaccesible memory or argument pointees (see 4794 /// Attribute::InaccessibleOrArgMemOnly). 4795 bool isKnownInaccessibleOrArgMemOnly() const { 4796 return isKnown( 4797 inverseLocation(NO_INACCESSIBLE_MEM | NO_ARGUMENT_MEM, true, true)); 4798 } 4799 4800 /// Return true if we assume that the underlying value will only access 4801 /// inaccesible memory or argument pointees (see 4802 /// Attribute::InaccessibleOrArgMemOnly). 4803 bool isAssumedInaccessibleOrArgMemOnly() const { 4804 return isAssumed( 4805 inverseLocation(NO_INACCESSIBLE_MEM | NO_ARGUMENT_MEM, true, true)); 4806 } 4807 4808 /// Return true if the underlying value may access memory through arguement 4809 /// pointers of the associated function, if any. 4810 bool mayAccessArgMem() const { return !isAssumed(NO_ARGUMENT_MEM); } 4811 4812 /// Return true if only the memory locations specififed by \p MLK are assumed 4813 /// to be accessed by the associated function. 4814 bool isAssumedSpecifiedMemOnly(MemoryLocationsKind MLK) const { 4815 return isAssumed(MLK); 4816 } 4817 4818 /// Return the locations that are assumed to be not accessed by the associated 4819 /// function, if any. 4820 MemoryLocationsKind getAssumedNotAccessedLocation() const { 4821 return getAssumed(); 4822 } 4823 4824 /// Return the inverse of location \p Loc, thus for NO_XXX the return 4825 /// describes ONLY_XXX. The flags \p AndLocalMem and \p AndConstMem determine 4826 /// if local (=stack) and constant memory are allowed as well. Most of the 4827 /// time we do want them to be included, e.g., argmemonly allows accesses via 4828 /// argument pointers or local or constant memory accesses. 4829 static MemoryLocationsKind 4830 inverseLocation(MemoryLocationsKind Loc, bool AndLocalMem, bool AndConstMem) { 4831 return NO_LOCATIONS & ~(Loc | (AndLocalMem ? NO_LOCAL_MEM : 0) | 4832 (AndConstMem ? NO_CONST_MEM : 0)); 4833 }; 4834 4835 /// Return the locations encoded by \p MLK as a readable string. 4836 static std::string getMemoryLocationsAsStr(MemoryLocationsKind MLK); 4837 4838 /// Simple enum to distinguish read/write/read-write accesses. 4839 enum AccessKind { 4840 NONE = 0, 4841 READ = 1 << 0, 4842 WRITE = 1 << 1, 4843 READ_WRITE = READ | WRITE, 4844 }; 4845 4846 /// Check \p Pred on all accesses to the memory kinds specified by \p MLK. 4847 /// 4848 /// This method will evaluate \p Pred on all accesses (access instruction + 4849 /// underlying accessed memory pointer) and it will return true if \p Pred 4850 /// holds every time. 4851 virtual bool checkForAllAccessesToMemoryKind( 4852 function_ref<bool(const Instruction *, const Value *, AccessKind, 4853 MemoryLocationsKind)> 4854 Pred, 4855 MemoryLocationsKind MLK) const = 0; 4856 4857 /// Create an abstract attribute view for the position \p IRP. 4858 static AAMemoryLocation &createForPosition(const IRPosition &IRP, 4859 Attributor &A); 4860 4861 /// See AbstractState::getAsStr(Attributor). 4862 const std::string getAsStr(Attributor *A) const override { 4863 return getMemoryLocationsAsStr(getAssumedNotAccessedLocation()); 4864 } 4865 4866 /// See AbstractAttribute::getName() 4867 const std::string getName() const override { return "AAMemoryLocation"; } 4868 4869 /// See AbstractAttribute::getIdAddr() 4870 const char *getIdAddr() const override { return &ID; } 4871 4872 /// This function should return true if the type of the \p AA is 4873 /// AAMemoryLocation 4874 static bool classof(const AbstractAttribute *AA) { 4875 return (AA->getIdAddr() == &ID); 4876 } 4877 4878 /// Unique ID (due to the unique address) 4879 static const char ID; 4880 }; 4881 4882 /// An abstract interface for range value analysis. 4883 struct AAValueConstantRange 4884 : public StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t> { 4885 using Base = StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t>; 4886 AAValueConstantRange(const IRPosition &IRP, Attributor &A) 4887 : Base(IRP, IRP.getAssociatedType()->getIntegerBitWidth()) {} 4888 4889 /// See AbstractAttribute::isValidIRPositionForInit 4890 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 4891 if (!IRP.getAssociatedType()->isIntegerTy()) 4892 return false; 4893 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 4894 } 4895 4896 /// See AbstractAttribute::requiresCallersForArgOrFunction 4897 static bool requiresCallersForArgOrFunction() { return true; } 4898 4899 /// See AbstractAttribute::getState(...). 4900 IntegerRangeState &getState() override { return *this; } 4901 const IntegerRangeState &getState() const override { return *this; } 4902 4903 /// Create an abstract attribute view for the position \p IRP. 4904 static AAValueConstantRange &createForPosition(const IRPosition &IRP, 4905 Attributor &A); 4906 4907 /// Return an assumed range for the associated value a program point \p CtxI. 4908 /// If \p I is nullptr, simply return an assumed range. 4909 virtual ConstantRange 4910 getAssumedConstantRange(Attributor &A, 4911 const Instruction *CtxI = nullptr) const = 0; 4912 4913 /// Return a known range for the associated value at a program point \p CtxI. 4914 /// If \p I is nullptr, simply return a known range. 4915 virtual ConstantRange 4916 getKnownConstantRange(Attributor &A, 4917 const Instruction *CtxI = nullptr) const = 0; 4918 4919 /// Return an assumed constant for the associated value a program point \p 4920 /// CtxI. 4921 std::optional<Constant *> 4922 getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const { 4923 ConstantRange RangeV = getAssumedConstantRange(A, CtxI); 4924 if (auto *C = RangeV.getSingleElement()) { 4925 Type *Ty = getAssociatedValue().getType(); 4926 return cast_or_null<Constant>( 4927 AA::getWithType(*ConstantInt::get(Ty->getContext(), *C), *Ty)); 4928 } 4929 if (RangeV.isEmptySet()) 4930 return std::nullopt; 4931 return nullptr; 4932 } 4933 4934 /// See AbstractAttribute::getName() 4935 const std::string getName() const override { return "AAValueConstantRange"; } 4936 4937 /// See AbstractAttribute::getIdAddr() 4938 const char *getIdAddr() const override { return &ID; } 4939 4940 /// This function should return true if the type of the \p AA is 4941 /// AAValueConstantRange 4942 static bool classof(const AbstractAttribute *AA) { 4943 return (AA->getIdAddr() == &ID); 4944 } 4945 4946 /// Unique ID (due to the unique address) 4947 static const char ID; 4948 }; 4949 4950 /// A class for a set state. 4951 /// The assumed boolean state indicates whether the corresponding set is full 4952 /// set or not. If the assumed state is false, this is the worst state. The 4953 /// worst state (invalid state) of set of potential values is when the set 4954 /// contains every possible value (i.e. we cannot in any way limit the value 4955 /// that the target position can take). That never happens naturally, we only 4956 /// force it. As for the conditions under which we force it, see 4957 /// AAPotentialConstantValues. 4958 template <typename MemberTy> struct PotentialValuesState : AbstractState { 4959 using SetTy = SmallSetVector<MemberTy, 8>; 4960 4961 PotentialValuesState() : IsValidState(true), UndefIsContained(false) {} 4962 4963 PotentialValuesState(bool IsValid) 4964 : IsValidState(IsValid), UndefIsContained(false) {} 4965 4966 /// See AbstractState::isValidState(...) 4967 bool isValidState() const override { return IsValidState.isValidState(); } 4968 4969 /// See AbstractState::isAtFixpoint(...) 4970 bool isAtFixpoint() const override { return IsValidState.isAtFixpoint(); } 4971 4972 /// See AbstractState::indicatePessimisticFixpoint(...) 4973 ChangeStatus indicatePessimisticFixpoint() override { 4974 return IsValidState.indicatePessimisticFixpoint(); 4975 } 4976 4977 /// See AbstractState::indicateOptimisticFixpoint(...) 4978 ChangeStatus indicateOptimisticFixpoint() override { 4979 return IsValidState.indicateOptimisticFixpoint(); 4980 } 4981 4982 /// Return the assumed state 4983 PotentialValuesState &getAssumed() { return *this; } 4984 const PotentialValuesState &getAssumed() const { return *this; } 4985 4986 /// Return this set. We should check whether this set is valid or not by 4987 /// isValidState() before calling this function. 4988 const SetTy &getAssumedSet() const { 4989 assert(isValidState() && "This set shoud not be used when it is invalid!"); 4990 return Set; 4991 } 4992 4993 /// Returns whether this state contains an undef value or not. 4994 bool undefIsContained() const { 4995 assert(isValidState() && "This flag shoud not be used when it is invalid!"); 4996 return UndefIsContained; 4997 } 4998 4999 bool operator==(const PotentialValuesState &RHS) const { 5000 if (isValidState() != RHS.isValidState()) 5001 return false; 5002 if (!isValidState() && !RHS.isValidState()) 5003 return true; 5004 if (undefIsContained() != RHS.undefIsContained()) 5005 return false; 5006 return Set == RHS.getAssumedSet(); 5007 } 5008 5009 /// Maximum number of potential values to be tracked. 5010 /// This is set by -attributor-max-potential-values command line option 5011 static unsigned MaxPotentialValues; 5012 5013 /// Return empty set as the best state of potential values. 5014 static PotentialValuesState getBestState() { 5015 return PotentialValuesState(true); 5016 } 5017 5018 static PotentialValuesState getBestState(const PotentialValuesState &PVS) { 5019 return getBestState(); 5020 } 5021 5022 /// Return full set as the worst state of potential values. 5023 static PotentialValuesState getWorstState() { 5024 return PotentialValuesState(false); 5025 } 5026 5027 /// Union assumed set with the passed value. 5028 void unionAssumed(const MemberTy &C) { insert(C); } 5029 5030 /// Union assumed set with assumed set of the passed state \p PVS. 5031 void unionAssumed(const PotentialValuesState &PVS) { unionWith(PVS); } 5032 5033 /// Union assumed set with an undef value. 5034 void unionAssumedWithUndef() { unionWithUndef(); } 5035 5036 /// "Clamp" this state with \p PVS. 5037 PotentialValuesState operator^=(const PotentialValuesState &PVS) { 5038 IsValidState ^= PVS.IsValidState; 5039 unionAssumed(PVS); 5040 return *this; 5041 } 5042 5043 PotentialValuesState operator&=(const PotentialValuesState &PVS) { 5044 IsValidState &= PVS.IsValidState; 5045 unionAssumed(PVS); 5046 return *this; 5047 } 5048 5049 bool contains(const MemberTy &V) const { 5050 return !isValidState() ? true : Set.contains(V); 5051 } 5052 5053 protected: 5054 SetTy &getAssumedSet() { 5055 assert(isValidState() && "This set shoud not be used when it is invalid!"); 5056 return Set; 5057 } 5058 5059 private: 5060 /// Check the size of this set, and invalidate when the size is no 5061 /// less than \p MaxPotentialValues threshold. 5062 void checkAndInvalidate() { 5063 if (Set.size() >= MaxPotentialValues) 5064 indicatePessimisticFixpoint(); 5065 else 5066 reduceUndefValue(); 5067 } 5068 5069 /// If this state contains both undef and not undef, we can reduce 5070 /// undef to the not undef value. 5071 void reduceUndefValue() { UndefIsContained = UndefIsContained & Set.empty(); } 5072 5073 /// Insert an element into this set. 5074 void insert(const MemberTy &C) { 5075 if (!isValidState()) 5076 return; 5077 Set.insert(C); 5078 checkAndInvalidate(); 5079 } 5080 5081 /// Take union with R. 5082 void unionWith(const PotentialValuesState &R) { 5083 /// If this is a full set, do nothing. 5084 if (!isValidState()) 5085 return; 5086 /// If R is full set, change L to a full set. 5087 if (!R.isValidState()) { 5088 indicatePessimisticFixpoint(); 5089 return; 5090 } 5091 for (const MemberTy &C : R.Set) 5092 Set.insert(C); 5093 UndefIsContained |= R.undefIsContained(); 5094 checkAndInvalidate(); 5095 } 5096 5097 /// Take union with an undef value. 5098 void unionWithUndef() { 5099 UndefIsContained = true; 5100 reduceUndefValue(); 5101 } 5102 5103 /// Take intersection with R. 5104 void intersectWith(const PotentialValuesState &R) { 5105 /// If R is a full set, do nothing. 5106 if (!R.isValidState()) 5107 return; 5108 /// If this is a full set, change this to R. 5109 if (!isValidState()) { 5110 *this = R; 5111 return; 5112 } 5113 SetTy IntersectSet; 5114 for (const MemberTy &C : Set) { 5115 if (R.Set.count(C)) 5116 IntersectSet.insert(C); 5117 } 5118 Set = IntersectSet; 5119 UndefIsContained &= R.undefIsContained(); 5120 reduceUndefValue(); 5121 } 5122 5123 /// A helper state which indicate whether this state is valid or not. 5124 BooleanState IsValidState; 5125 5126 /// Container for potential values 5127 SetTy Set; 5128 5129 /// Flag for undef value 5130 bool UndefIsContained; 5131 }; 5132 5133 struct DenormalFPMathState : public AbstractState { 5134 struct DenormalState { 5135 DenormalMode Mode = DenormalMode::getInvalid(); 5136 DenormalMode ModeF32 = DenormalMode::getInvalid(); 5137 5138 bool operator==(const DenormalState Other) const { 5139 return Mode == Other.Mode && ModeF32 == Other.ModeF32; 5140 } 5141 5142 bool operator!=(const DenormalState Other) const { 5143 return Mode != Other.Mode || ModeF32 != Other.ModeF32; 5144 } 5145 5146 bool isValid() const { 5147 return Mode.isValid() && ModeF32.isValid(); 5148 } 5149 5150 static DenormalMode::DenormalModeKind 5151 unionDenormalKind(DenormalMode::DenormalModeKind Callee, 5152 DenormalMode::DenormalModeKind Caller) { 5153 if (Caller == Callee) 5154 return Caller; 5155 if (Callee == DenormalMode::Dynamic) 5156 return Caller; 5157 if (Caller == DenormalMode::Dynamic) 5158 return Callee; 5159 return DenormalMode::Invalid; 5160 } 5161 5162 static DenormalMode unionAssumed(DenormalMode Callee, DenormalMode Caller) { 5163 return DenormalMode{unionDenormalKind(Callee.Output, Caller.Output), 5164 unionDenormalKind(Callee.Input, Caller.Input)}; 5165 } 5166 5167 DenormalState unionWith(DenormalState Caller) const { 5168 DenormalState Callee(*this); 5169 Callee.Mode = unionAssumed(Callee.Mode, Caller.Mode); 5170 Callee.ModeF32 = unionAssumed(Callee.ModeF32, Caller.ModeF32); 5171 return Callee; 5172 } 5173 }; 5174 5175 DenormalState Known; 5176 5177 /// Explicitly track whether we've hit a fixed point. 5178 bool IsAtFixedpoint = false; 5179 5180 DenormalFPMathState() = default; 5181 5182 DenormalState getKnown() const { return Known; } 5183 5184 // There's only really known or unknown, there's no speculatively assumable 5185 // state. 5186 DenormalState getAssumed() const { return Known; } 5187 5188 bool isValidState() const override { 5189 return Known.isValid(); 5190 } 5191 5192 /// Return true if there are no dynamic components to the denormal mode worth 5193 /// specializing. 5194 bool isModeFixed() const { 5195 return Known.Mode.Input != DenormalMode::Dynamic && 5196 Known.Mode.Output != DenormalMode::Dynamic && 5197 Known.ModeF32.Input != DenormalMode::Dynamic && 5198 Known.ModeF32.Output != DenormalMode::Dynamic; 5199 } 5200 5201 bool isAtFixpoint() const override { 5202 return IsAtFixedpoint; 5203 } 5204 5205 ChangeStatus indicateFixpoint() { 5206 bool Changed = !IsAtFixedpoint; 5207 IsAtFixedpoint = true; 5208 return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; 5209 } 5210 5211 ChangeStatus indicateOptimisticFixpoint() override { 5212 return indicateFixpoint(); 5213 } 5214 5215 ChangeStatus indicatePessimisticFixpoint() override { 5216 return indicateFixpoint(); 5217 } 5218 5219 DenormalFPMathState operator^=(const DenormalFPMathState &Caller) { 5220 Known = Known.unionWith(Caller.getKnown()); 5221 return *this; 5222 } 5223 }; 5224 5225 using PotentialConstantIntValuesState = PotentialValuesState<APInt>; 5226 using PotentialLLVMValuesState = 5227 PotentialValuesState<std::pair<AA::ValueAndContext, AA::ValueScope>>; 5228 5229 raw_ostream &operator<<(raw_ostream &OS, 5230 const PotentialConstantIntValuesState &R); 5231 raw_ostream &operator<<(raw_ostream &OS, const PotentialLLVMValuesState &R); 5232 5233 /// An abstract interface for potential values analysis. 5234 /// 5235 /// This AA collects potential values for each IR position. 5236 /// An assumed set of potential values is initialized with the empty set (the 5237 /// best state) and it will grow monotonically as we find more potential values 5238 /// for this position. 5239 /// The set might be forced to the worst state, that is, to contain every 5240 /// possible value for this position in 2 cases. 5241 /// 1. We surpassed the \p MaxPotentialValues threshold. This includes the 5242 /// case that this position is affected (e.g. because of an operation) by a 5243 /// Value that is in the worst state. 5244 /// 2. We tried to initialize on a Value that we cannot handle (e.g. an 5245 /// operator we do not currently handle). 5246 /// 5247 /// For non constant integers see AAPotentialValues. 5248 struct AAPotentialConstantValues 5249 : public StateWrapper<PotentialConstantIntValuesState, AbstractAttribute> { 5250 using Base = StateWrapper<PotentialConstantIntValuesState, AbstractAttribute>; 5251 AAPotentialConstantValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 5252 5253 /// See AbstractAttribute::isValidIRPositionForInit 5254 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 5255 if (!IRP.getAssociatedType()->isIntegerTy()) 5256 return false; 5257 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 5258 } 5259 5260 /// See AbstractAttribute::requiresCallersForArgOrFunction 5261 static bool requiresCallersForArgOrFunction() { return true; } 5262 5263 /// See AbstractAttribute::getState(...). 5264 PotentialConstantIntValuesState &getState() override { return *this; } 5265 const PotentialConstantIntValuesState &getState() const override { 5266 return *this; 5267 } 5268 5269 /// Create an abstract attribute view for the position \p IRP. 5270 static AAPotentialConstantValues &createForPosition(const IRPosition &IRP, 5271 Attributor &A); 5272 5273 /// Return assumed constant for the associated value 5274 std::optional<Constant *> 5275 getAssumedConstant(Attributor &A, const Instruction *CtxI = nullptr) const { 5276 if (!isValidState()) 5277 return nullptr; 5278 if (getAssumedSet().size() == 1) { 5279 Type *Ty = getAssociatedValue().getType(); 5280 return cast_or_null<Constant>(AA::getWithType( 5281 *ConstantInt::get(Ty->getContext(), *(getAssumedSet().begin())), 5282 *Ty)); 5283 } 5284 if (getAssumedSet().size() == 0) { 5285 if (undefIsContained()) 5286 return UndefValue::get(getAssociatedValue().getType()); 5287 return std::nullopt; 5288 } 5289 5290 return nullptr; 5291 } 5292 5293 /// See AbstractAttribute::getName() 5294 const std::string getName() const override { 5295 return "AAPotentialConstantValues"; 5296 } 5297 5298 /// See AbstractAttribute::getIdAddr() 5299 const char *getIdAddr() const override { return &ID; } 5300 5301 /// This function should return true if the type of the \p AA is 5302 /// AAPotentialConstantValues 5303 static bool classof(const AbstractAttribute *AA) { 5304 return (AA->getIdAddr() == &ID); 5305 } 5306 5307 /// Unique ID (due to the unique address) 5308 static const char ID; 5309 }; 5310 5311 struct AAPotentialValues 5312 : public StateWrapper<PotentialLLVMValuesState, AbstractAttribute> { 5313 using Base = StateWrapper<PotentialLLVMValuesState, AbstractAttribute>; 5314 AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 5315 5316 /// See AbstractAttribute::requiresCallersForArgOrFunction 5317 static bool requiresCallersForArgOrFunction() { return true; } 5318 5319 /// See AbstractAttribute::getState(...). 5320 PotentialLLVMValuesState &getState() override { return *this; } 5321 const PotentialLLVMValuesState &getState() const override { return *this; } 5322 5323 /// Create an abstract attribute view for the position \p IRP. 5324 static AAPotentialValues &createForPosition(const IRPosition &IRP, 5325 Attributor &A); 5326 5327 /// Extract the single value in \p Values if any. 5328 static Value *getSingleValue(Attributor &A, const AbstractAttribute &AA, 5329 const IRPosition &IRP, 5330 SmallVectorImpl<AA::ValueAndContext> &Values); 5331 5332 /// See AbstractAttribute::getName() 5333 const std::string getName() const override { return "AAPotentialValues"; } 5334 5335 /// See AbstractAttribute::getIdAddr() 5336 const char *getIdAddr() const override { return &ID; } 5337 5338 /// This function should return true if the type of the \p AA is 5339 /// AAPotentialValues 5340 static bool classof(const AbstractAttribute *AA) { 5341 return (AA->getIdAddr() == &ID); 5342 } 5343 5344 /// Unique ID (due to the unique address) 5345 static const char ID; 5346 5347 private: 5348 virtual bool getAssumedSimplifiedValues( 5349 Attributor &A, SmallVectorImpl<AA::ValueAndContext> &Values, 5350 AA::ValueScope, bool RecurseForSelectAndPHI = false) const = 0; 5351 5352 friend struct Attributor; 5353 }; 5354 5355 /// An abstract interface for all noundef attributes. 5356 struct AANoUndef 5357 : public IRAttribute<Attribute::NoUndef, 5358 StateWrapper<BooleanState, AbstractAttribute>, 5359 AANoUndef> { 5360 AANoUndef(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 5361 5362 /// See IRAttribute::isImpliedByUndef 5363 static bool isImpliedByUndef() { return false; } 5364 5365 /// See IRAttribute::isImpliedByPoison 5366 static bool isImpliedByPoison() { return false; } 5367 5368 /// See IRAttribute::isImpliedByIR 5369 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP, 5370 Attribute::AttrKind ImpliedAttributeKind, 5371 bool IgnoreSubsumingPositions = false); 5372 5373 /// Return true if we assume that the underlying value is noundef. 5374 bool isAssumedNoUndef() const { return getAssumed(); } 5375 5376 /// Return true if we know that underlying value is noundef. 5377 bool isKnownNoUndef() const { return getKnown(); } 5378 5379 /// Create an abstract attribute view for the position \p IRP. 5380 static AANoUndef &createForPosition(const IRPosition &IRP, Attributor &A); 5381 5382 /// See AbstractAttribute::getName() 5383 const std::string getName() const override { return "AANoUndef"; } 5384 5385 /// See AbstractAttribute::getIdAddr() 5386 const char *getIdAddr() const override { return &ID; } 5387 5388 /// This function should return true if the type of the \p AA is AANoUndef 5389 static bool classof(const AbstractAttribute *AA) { 5390 return (AA->getIdAddr() == &ID); 5391 } 5392 5393 /// Unique ID (due to the unique address) 5394 static const char ID; 5395 }; 5396 5397 struct AANoFPClass 5398 : public IRAttribute< 5399 Attribute::NoFPClass, 5400 StateWrapper<BitIntegerState<uint32_t, fcAllFlags, fcNone>, 5401 AbstractAttribute>, 5402 AANoFPClass> { 5403 using Base = StateWrapper<BitIntegerState<uint32_t, fcAllFlags, fcNone>, 5404 AbstractAttribute>; 5405 5406 AANoFPClass(const IRPosition &IRP, Attributor &A) : IRAttribute(IRP) {} 5407 5408 /// See AbstractAttribute::isValidIRPositionForInit 5409 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 5410 Type *Ty = IRP.getAssociatedType(); 5411 do { 5412 if (Ty->isFPOrFPVectorTy()) 5413 return IRAttribute::isValidIRPositionForInit(A, IRP); 5414 if (!Ty->isArrayTy()) 5415 break; 5416 Ty = Ty->getArrayElementType(); 5417 } while (true); 5418 return false; 5419 } 5420 5421 /// Return true if we assume that the underlying value is nofpclass. 5422 FPClassTest getAssumedNoFPClass() const { 5423 return static_cast<FPClassTest>(getAssumed()); 5424 } 5425 5426 /// Create an abstract attribute view for the position \p IRP. 5427 static AANoFPClass &createForPosition(const IRPosition &IRP, Attributor &A); 5428 5429 /// See AbstractAttribute::getName() 5430 const std::string getName() const override { return "AANoFPClass"; } 5431 5432 /// See AbstractAttribute::getIdAddr() 5433 const char *getIdAddr() const override { return &ID; } 5434 5435 /// This function should return true if the type of the \p AA is AANoFPClass 5436 static bool classof(const AbstractAttribute *AA) { 5437 return (AA->getIdAddr() == &ID); 5438 } 5439 5440 /// Unique ID (due to the unique address) 5441 static const char ID; 5442 }; 5443 5444 struct AACallGraphNode; 5445 struct AACallEdges; 5446 5447 /// An Iterator for call edges, creates AACallEdges attributes in a lazy way. 5448 /// This iterator becomes invalid if the underlying edge list changes. 5449 /// So This shouldn't outlive a iteration of Attributor. 5450 class AACallEdgeIterator 5451 : public iterator_adaptor_base<AACallEdgeIterator, 5452 SetVector<Function *>::iterator> { 5453 AACallEdgeIterator(Attributor &A, SetVector<Function *>::iterator Begin) 5454 : iterator_adaptor_base(Begin), A(A) {} 5455 5456 public: 5457 AACallGraphNode *operator*() const; 5458 5459 private: 5460 Attributor &A; 5461 friend AACallEdges; 5462 friend AttributorCallGraph; 5463 }; 5464 5465 struct AACallGraphNode { 5466 AACallGraphNode(Attributor &A) : A(A) {} 5467 virtual ~AACallGraphNode() = default; 5468 5469 virtual AACallEdgeIterator optimisticEdgesBegin() const = 0; 5470 virtual AACallEdgeIterator optimisticEdgesEnd() const = 0; 5471 5472 /// Iterator range for exploring the call graph. 5473 iterator_range<AACallEdgeIterator> optimisticEdgesRange() const { 5474 return iterator_range<AACallEdgeIterator>(optimisticEdgesBegin(), 5475 optimisticEdgesEnd()); 5476 } 5477 5478 protected: 5479 /// Reference to Attributor needed for GraphTraits implementation. 5480 Attributor &A; 5481 }; 5482 5483 /// An abstract state for querying live call edges. 5484 /// This interface uses the Attributor's optimistic liveness 5485 /// information to compute the edges that are alive. 5486 struct AACallEdges : public StateWrapper<BooleanState, AbstractAttribute>, 5487 AACallGraphNode { 5488 using Base = StateWrapper<BooleanState, AbstractAttribute>; 5489 5490 AACallEdges(const IRPosition &IRP, Attributor &A) 5491 : Base(IRP), AACallGraphNode(A) {} 5492 5493 /// See AbstractAttribute::requiresNonAsmForCallBase. 5494 static bool requiresNonAsmForCallBase() { return false; } 5495 5496 /// Get the optimistic edges. 5497 virtual const SetVector<Function *> &getOptimisticEdges() const = 0; 5498 5499 /// Is there any call with a unknown callee. 5500 virtual bool hasUnknownCallee() const = 0; 5501 5502 /// Is there any call with a unknown callee, excluding any inline asm. 5503 virtual bool hasNonAsmUnknownCallee() const = 0; 5504 5505 /// Iterator for exploring the call graph. 5506 AACallEdgeIterator optimisticEdgesBegin() const override { 5507 return AACallEdgeIterator(A, getOptimisticEdges().begin()); 5508 } 5509 5510 /// Iterator for exploring the call graph. 5511 AACallEdgeIterator optimisticEdgesEnd() const override { 5512 return AACallEdgeIterator(A, getOptimisticEdges().end()); 5513 } 5514 5515 /// Create an abstract attribute view for the position \p IRP. 5516 static AACallEdges &createForPosition(const IRPosition &IRP, Attributor &A); 5517 5518 /// See AbstractAttribute::getName() 5519 const std::string getName() const override { return "AACallEdges"; } 5520 5521 /// See AbstractAttribute::getIdAddr() 5522 const char *getIdAddr() const override { return &ID; } 5523 5524 /// This function should return true if the type of the \p AA is AACallEdges. 5525 static bool classof(const AbstractAttribute *AA) { 5526 return (AA->getIdAddr() == &ID); 5527 } 5528 5529 /// Unique ID (due to the unique address) 5530 static const char ID; 5531 }; 5532 5533 // Synthetic root node for the Attributor's internal call graph. 5534 struct AttributorCallGraph : public AACallGraphNode { 5535 AttributorCallGraph(Attributor &A) : AACallGraphNode(A) {} 5536 virtual ~AttributorCallGraph() = default; 5537 5538 AACallEdgeIterator optimisticEdgesBegin() const override { 5539 return AACallEdgeIterator(A, A.Functions.begin()); 5540 } 5541 5542 AACallEdgeIterator optimisticEdgesEnd() const override { 5543 return AACallEdgeIterator(A, A.Functions.end()); 5544 } 5545 5546 /// Force populate the entire call graph. 5547 void populateAll() const { 5548 for (const AACallGraphNode *AA : optimisticEdgesRange()) { 5549 // Nothing else to do here. 5550 (void)AA; 5551 } 5552 } 5553 5554 void print(); 5555 }; 5556 5557 template <> struct GraphTraits<AACallGraphNode *> { 5558 using NodeRef = AACallGraphNode *; 5559 using ChildIteratorType = AACallEdgeIterator; 5560 5561 static AACallEdgeIterator child_begin(AACallGraphNode *Node) { 5562 return Node->optimisticEdgesBegin(); 5563 } 5564 5565 static AACallEdgeIterator child_end(AACallGraphNode *Node) { 5566 return Node->optimisticEdgesEnd(); 5567 } 5568 }; 5569 5570 template <> 5571 struct GraphTraits<AttributorCallGraph *> 5572 : public GraphTraits<AACallGraphNode *> { 5573 using nodes_iterator = AACallEdgeIterator; 5574 5575 static AACallGraphNode *getEntryNode(AttributorCallGraph *G) { 5576 return static_cast<AACallGraphNode *>(G); 5577 } 5578 5579 static AACallEdgeIterator nodes_begin(const AttributorCallGraph *G) { 5580 return G->optimisticEdgesBegin(); 5581 } 5582 5583 static AACallEdgeIterator nodes_end(const AttributorCallGraph *G) { 5584 return G->optimisticEdgesEnd(); 5585 } 5586 }; 5587 5588 template <> 5589 struct DOTGraphTraits<AttributorCallGraph *> : public DefaultDOTGraphTraits { 5590 DOTGraphTraits(bool Simple = false) : DefaultDOTGraphTraits(Simple) {} 5591 5592 std::string getNodeLabel(const AACallGraphNode *Node, 5593 const AttributorCallGraph *Graph) { 5594 const AACallEdges *AACE = static_cast<const AACallEdges *>(Node); 5595 return AACE->getAssociatedFunction()->getName().str(); 5596 } 5597 5598 static bool isNodeHidden(const AACallGraphNode *Node, 5599 const AttributorCallGraph *Graph) { 5600 // Hide the synth root. 5601 return static_cast<const AACallGraphNode *>(Graph) == Node; 5602 } 5603 }; 5604 5605 struct AAExecutionDomain 5606 : public StateWrapper<BooleanState, AbstractAttribute> { 5607 using Base = StateWrapper<BooleanState, AbstractAttribute>; 5608 AAExecutionDomain(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 5609 5610 /// Summary about the execution domain of a block or instruction. 5611 struct ExecutionDomainTy { 5612 using BarriersSetTy = SmallPtrSet<CallBase *, 2>; 5613 using AssumesSetTy = SmallPtrSet<AssumeInst *, 4>; 5614 5615 void addAssumeInst(Attributor &A, AssumeInst &AI) { 5616 EncounteredAssumes.insert(&AI); 5617 } 5618 5619 void addAlignedBarrier(Attributor &A, CallBase &CB) { 5620 AlignedBarriers.insert(&CB); 5621 } 5622 5623 void clearAssumeInstAndAlignedBarriers() { 5624 EncounteredAssumes.clear(); 5625 AlignedBarriers.clear(); 5626 } 5627 5628 bool IsExecutedByInitialThreadOnly = true; 5629 bool IsReachedFromAlignedBarrierOnly = true; 5630 bool IsReachingAlignedBarrierOnly = true; 5631 bool EncounteredNonLocalSideEffect = false; 5632 BarriersSetTy AlignedBarriers; 5633 AssumesSetTy EncounteredAssumes; 5634 }; 5635 5636 /// Create an abstract attribute view for the position \p IRP. 5637 static AAExecutionDomain &createForPosition(const IRPosition &IRP, 5638 Attributor &A); 5639 5640 /// See AbstractAttribute::getName(). 5641 const std::string getName() const override { return "AAExecutionDomain"; } 5642 5643 /// See AbstractAttribute::getIdAddr(). 5644 const char *getIdAddr() const override { return &ID; } 5645 5646 /// Check if an instruction is executed only by the initial thread. 5647 bool isExecutedByInitialThreadOnly(const Instruction &I) const { 5648 return isExecutedByInitialThreadOnly(*I.getParent()); 5649 } 5650 5651 /// Check if a basic block is executed only by the initial thread. 5652 virtual bool isExecutedByInitialThreadOnly(const BasicBlock &) const = 0; 5653 5654 /// Check if the instruction \p I is executed in an aligned region, that is, 5655 /// the synchronizing effects before and after \p I are both aligned barriers. 5656 /// This effectively means all threads execute \p I together. 5657 virtual bool isExecutedInAlignedRegion(Attributor &A, 5658 const Instruction &I) const = 0; 5659 5660 virtual ExecutionDomainTy getExecutionDomain(const BasicBlock &) const = 0; 5661 /// Return the execution domain with which the call \p CB is entered and the 5662 /// one with which it is left. 5663 virtual std::pair<ExecutionDomainTy, ExecutionDomainTy> 5664 getExecutionDomain(const CallBase &CB) const = 0; 5665 virtual ExecutionDomainTy getFunctionExecutionDomain() const = 0; 5666 5667 /// Helper function to determine if \p FI is a no-op given the information 5668 /// about its execution from \p ExecDomainAA. 5669 virtual bool isNoOpFence(const FenceInst &FI) const = 0; 5670 5671 /// This function should return true if the type of the \p AA is 5672 /// AAExecutionDomain. 5673 static bool classof(const AbstractAttribute *AA) { 5674 return (AA->getIdAddr() == &ID); 5675 } 5676 5677 /// Unique ID (due to the unique address) 5678 static const char ID; 5679 }; 5680 5681 /// An abstract Attribute for computing reachability between functions. 5682 struct AAInterFnReachability 5683 : public StateWrapper<BooleanState, AbstractAttribute> { 5684 using Base = StateWrapper<BooleanState, AbstractAttribute>; 5685 5686 AAInterFnReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 5687 5688 /// If the function represented by this possition can reach \p Fn. 5689 bool canReach(Attributor &A, const Function &Fn) const { 5690 Function *Scope = getAnchorScope(); 5691 if (!Scope || Scope->isDeclaration()) 5692 return true; 5693 return instructionCanReach(A, Scope->getEntryBlock().front(), Fn); 5694 } 5695 5696 /// Can \p Inst reach \p Fn. 5697 /// See also AA::isPotentiallyReachable. 5698 virtual bool instructionCanReach( 5699 Attributor &A, const Instruction &Inst, const Function &Fn, 5700 const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0; 5701 5702 /// Create an abstract attribute view for the position \p IRP. 5703 static AAInterFnReachability &createForPosition(const IRPosition &IRP, 5704 Attributor &A); 5705 5706 /// See AbstractAttribute::getName() 5707 const std::string getName() const override { return "AAInterFnReachability"; } 5708 5709 /// See AbstractAttribute::getIdAddr() 5710 const char *getIdAddr() const override { return &ID; } 5711 5712 /// This function should return true if the type of the \p AA is AACallEdges. 5713 static bool classof(const AbstractAttribute *AA) { 5714 return (AA->getIdAddr() == &ID); 5715 } 5716 5717 /// Unique ID (due to the unique address) 5718 static const char ID; 5719 }; 5720 5721 /// An abstract Attribute for determining the necessity of the convergent 5722 /// attribute. 5723 struct AANonConvergent : public StateWrapper<BooleanState, AbstractAttribute> { 5724 using Base = StateWrapper<BooleanState, AbstractAttribute>; 5725 5726 AANonConvergent(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 5727 5728 /// Create an abstract attribute view for the position \p IRP. 5729 static AANonConvergent &createForPosition(const IRPosition &IRP, 5730 Attributor &A); 5731 5732 /// Return true if "non-convergent" is assumed. 5733 bool isAssumedNotConvergent() const { return getAssumed(); } 5734 5735 /// Return true if "non-convergent" is known. 5736 bool isKnownNotConvergent() const { return getKnown(); } 5737 5738 /// See AbstractAttribute::getName() 5739 const std::string getName() const override { return "AANonConvergent"; } 5740 5741 /// See AbstractAttribute::getIdAddr() 5742 const char *getIdAddr() const override { return &ID; } 5743 5744 /// This function should return true if the type of the \p AA is 5745 /// AANonConvergent. 5746 static bool classof(const AbstractAttribute *AA) { 5747 return (AA->getIdAddr() == &ID); 5748 } 5749 5750 /// Unique ID (due to the unique address) 5751 static const char ID; 5752 }; 5753 5754 /// An abstract interface for struct information. 5755 struct AAPointerInfo : public AbstractAttribute { 5756 AAPointerInfo(const IRPosition &IRP) : AbstractAttribute(IRP) {} 5757 5758 /// See AbstractAttribute::isValidIRPositionForInit 5759 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 5760 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 5761 return false; 5762 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 5763 } 5764 5765 enum AccessKind { 5766 // First two bits to distinguish may and must accesses. 5767 AK_MUST = 1 << 0, 5768 AK_MAY = 1 << 1, 5769 5770 // Then two bits for read and write. These are not exclusive. 5771 AK_R = 1 << 2, 5772 AK_W = 1 << 3, 5773 AK_RW = AK_R | AK_W, 5774 5775 // One special case for assumptions about memory content. These 5776 // are neither reads nor writes. They are however always modeled 5777 // as read to avoid using them for write removal. 5778 AK_ASSUMPTION = (1 << 4) | AK_MUST, 5779 5780 // Helper for easy access. 5781 AK_MAY_READ = AK_MAY | AK_R, 5782 AK_MAY_WRITE = AK_MAY | AK_W, 5783 AK_MAY_READ_WRITE = AK_MAY | AK_R | AK_W, 5784 AK_MUST_READ = AK_MUST | AK_R, 5785 AK_MUST_WRITE = AK_MUST | AK_W, 5786 AK_MUST_READ_WRITE = AK_MUST | AK_R | AK_W, 5787 }; 5788 5789 /// A container for a list of ranges. 5790 struct RangeList { 5791 // The set of ranges rarely contains more than one element, and is unlikely 5792 // to contain more than say four elements. So we find the middle-ground with 5793 // a sorted vector. This avoids hard-coding a rarely used number like "four" 5794 // into every instance of a SmallSet. 5795 using RangeTy = AA::RangeTy; 5796 using VecTy = SmallVector<RangeTy>; 5797 using iterator = VecTy::iterator; 5798 using const_iterator = VecTy::const_iterator; 5799 VecTy Ranges; 5800 5801 RangeList(const RangeTy &R) { Ranges.push_back(R); } 5802 RangeList(ArrayRef<int64_t> Offsets, int64_t Size) { 5803 Ranges.reserve(Offsets.size()); 5804 for (unsigned i = 0, e = Offsets.size(); i != e; ++i) { 5805 assert(((i + 1 == e) || Offsets[i] < Offsets[i + 1]) && 5806 "Expected strictly ascending offsets."); 5807 Ranges.emplace_back(Offsets[i], Size); 5808 } 5809 } 5810 RangeList() = default; 5811 5812 iterator begin() { return Ranges.begin(); } 5813 iterator end() { return Ranges.end(); } 5814 const_iterator begin() const { return Ranges.begin(); } 5815 const_iterator end() const { return Ranges.end(); } 5816 5817 // Helpers required for std::set_difference 5818 using value_type = RangeTy; 5819 void push_back(const RangeTy &R) { 5820 assert((Ranges.empty() || RangeTy::OffsetLessThan(Ranges.back(), R)) && 5821 "Ensure the last element is the greatest."); 5822 Ranges.push_back(R); 5823 } 5824 5825 /// Copy ranges from \p L that are not in \p R, into \p D. 5826 static void set_difference(const RangeList &L, const RangeList &R, 5827 RangeList &D) { 5828 std::set_difference(L.begin(), L.end(), R.begin(), R.end(), 5829 std::back_inserter(D), RangeTy::OffsetLessThan); 5830 } 5831 5832 unsigned size() const { return Ranges.size(); } 5833 5834 bool operator==(const RangeList &OI) const { return Ranges == OI.Ranges; } 5835 5836 /// Merge the ranges in \p RHS into the current ranges. 5837 /// - Merging a list of unknown ranges makes the current list unknown. 5838 /// - Ranges with the same offset are merged according to RangeTy::operator& 5839 /// \return true if the current RangeList changed. 5840 bool merge(const RangeList &RHS) { 5841 if (isUnknown()) 5842 return false; 5843 if (RHS.isUnknown()) { 5844 setUnknown(); 5845 return true; 5846 } 5847 5848 if (Ranges.empty()) { 5849 Ranges = RHS.Ranges; 5850 return true; 5851 } 5852 5853 bool Changed = false; 5854 auto LPos = Ranges.begin(); 5855 for (auto &R : RHS.Ranges) { 5856 auto Result = insert(LPos, R); 5857 if (isUnknown()) 5858 return true; 5859 LPos = Result.first; 5860 Changed |= Result.second; 5861 } 5862 return Changed; 5863 } 5864 5865 /// Insert \p R at the given iterator \p Pos, and merge if necessary. 5866 /// 5867 /// This assumes that all ranges before \p Pos are OffsetLessThan \p R, and 5868 /// then maintains the sorted order for the suffix list. 5869 /// 5870 /// \return The place of insertion and true iff anything changed. 5871 std::pair<iterator, bool> insert(iterator Pos, const RangeTy &R) { 5872 if (isUnknown()) 5873 return std::make_pair(Ranges.begin(), false); 5874 if (R.offsetOrSizeAreUnknown()) { 5875 return std::make_pair(setUnknown(), true); 5876 } 5877 5878 // Maintain this as a sorted vector of unique entries. 5879 auto LB = std::lower_bound(Pos, Ranges.end(), R, RangeTy::OffsetLessThan); 5880 if (LB == Ranges.end() || LB->Offset != R.Offset) 5881 return std::make_pair(Ranges.insert(LB, R), true); 5882 bool Changed = *LB != R; 5883 *LB &= R; 5884 if (LB->offsetOrSizeAreUnknown()) 5885 return std::make_pair(setUnknown(), true); 5886 return std::make_pair(LB, Changed); 5887 } 5888 5889 /// Insert the given range \p R, maintaining sorted order. 5890 /// 5891 /// \return The place of insertion and true iff anything changed. 5892 std::pair<iterator, bool> insert(const RangeTy &R) { 5893 return insert(Ranges.begin(), R); 5894 } 5895 5896 /// Add the increment \p Inc to the offset of every range. 5897 void addToAllOffsets(int64_t Inc) { 5898 assert(!isUnassigned() && 5899 "Cannot increment if the offset is not yet computed!"); 5900 if (isUnknown()) 5901 return; 5902 for (auto &R : Ranges) { 5903 R.Offset += Inc; 5904 } 5905 } 5906 5907 /// Return true iff there is exactly one range and it is known. 5908 bool isUnique() const { 5909 return Ranges.size() == 1 && !Ranges.front().offsetOrSizeAreUnknown(); 5910 } 5911 5912 /// Return the unique range, assuming it exists. 5913 const RangeTy &getUnique() const { 5914 assert(isUnique() && "No unique range to return!"); 5915 return Ranges.front(); 5916 } 5917 5918 /// Return true iff the list contains an unknown range. 5919 bool isUnknown() const { 5920 if (isUnassigned()) 5921 return false; 5922 if (Ranges.front().offsetOrSizeAreUnknown()) { 5923 assert(Ranges.size() == 1 && "Unknown is a singleton range."); 5924 return true; 5925 } 5926 return false; 5927 } 5928 5929 /// Discard all ranges and insert a single unknown range. 5930 iterator setUnknown() { 5931 Ranges.clear(); 5932 Ranges.push_back(RangeTy::getUnknown()); 5933 return Ranges.begin(); 5934 } 5935 5936 /// Return true if no ranges have been inserted. 5937 bool isUnassigned() const { return Ranges.size() == 0; } 5938 }; 5939 5940 /// An access description. 5941 struct Access { 5942 Access(Instruction *I, int64_t Offset, int64_t Size, 5943 std::optional<Value *> Content, AccessKind Kind, Type *Ty) 5944 : LocalI(I), RemoteI(I), Content(Content), Ranges(Offset, Size), 5945 Kind(Kind), Ty(Ty) { 5946 verify(); 5947 } 5948 Access(Instruction *LocalI, Instruction *RemoteI, const RangeList &Ranges, 5949 std::optional<Value *> Content, AccessKind K, Type *Ty) 5950 : LocalI(LocalI), RemoteI(RemoteI), Content(Content), Ranges(Ranges), 5951 Kind(K), Ty(Ty) { 5952 if (Ranges.size() > 1) { 5953 Kind = AccessKind(Kind | AK_MAY); 5954 Kind = AccessKind(Kind & ~AK_MUST); 5955 } 5956 verify(); 5957 } 5958 Access(Instruction *LocalI, Instruction *RemoteI, int64_t Offset, 5959 int64_t Size, std::optional<Value *> Content, AccessKind Kind, 5960 Type *Ty) 5961 : LocalI(LocalI), RemoteI(RemoteI), Content(Content), 5962 Ranges(Offset, Size), Kind(Kind), Ty(Ty) { 5963 verify(); 5964 } 5965 Access(const Access &Other) = default; 5966 5967 Access &operator=(const Access &Other) = default; 5968 bool operator==(const Access &R) const { 5969 return LocalI == R.LocalI && RemoteI == R.RemoteI && Ranges == R.Ranges && 5970 Content == R.Content && Kind == R.Kind; 5971 } 5972 bool operator!=(const Access &R) const { return !(*this == R); } 5973 5974 Access &operator&=(const Access &R) { 5975 assert(RemoteI == R.RemoteI && "Expected same instruction!"); 5976 assert(LocalI == R.LocalI && "Expected same instruction!"); 5977 5978 // Note that every Access object corresponds to a unique Value, and only 5979 // accesses to the same Value are merged. Hence we assume that all ranges 5980 // are the same size. If ranges can be different size, then the contents 5981 // must be dropped. 5982 Ranges.merge(R.Ranges); 5983 Content = 5984 AA::combineOptionalValuesInAAValueLatice(Content, R.Content, Ty); 5985 5986 // Combine the access kind, which results in a bitwise union. 5987 // If there is more than one range, then this must be a MAY. 5988 // If we combine a may and a must access we clear the must bit. 5989 Kind = AccessKind(Kind | R.Kind); 5990 if ((Kind & AK_MAY) || Ranges.size() > 1) { 5991 Kind = AccessKind(Kind | AK_MAY); 5992 Kind = AccessKind(Kind & ~AK_MUST); 5993 } 5994 verify(); 5995 return *this; 5996 } 5997 5998 void verify() { 5999 assert(isMustAccess() + isMayAccess() == 1 && 6000 "Expect must or may access, not both."); 6001 assert(isAssumption() + isWrite() <= 1 && 6002 "Expect assumption access or write access, never both."); 6003 assert((isMayAccess() || Ranges.size() == 1) && 6004 "Cannot be a must access if there are multiple ranges."); 6005 } 6006 6007 /// Return the access kind. 6008 AccessKind getKind() const { return Kind; } 6009 6010 /// Return true if this is a read access. 6011 bool isRead() const { return Kind & AK_R; } 6012 6013 /// Return true if this is a write access. 6014 bool isWrite() const { return Kind & AK_W; } 6015 6016 /// Return true if this is a write access. 6017 bool isWriteOrAssumption() const { return isWrite() || isAssumption(); } 6018 6019 /// Return true if this is an assumption access. 6020 bool isAssumption() const { return Kind == AK_ASSUMPTION; } 6021 6022 bool isMustAccess() const { 6023 bool MustAccess = Kind & AK_MUST; 6024 assert((!MustAccess || Ranges.size() < 2) && 6025 "Cannot be a must access if there are multiple ranges."); 6026 return MustAccess; 6027 } 6028 6029 bool isMayAccess() const { 6030 bool MayAccess = Kind & AK_MAY; 6031 assert((MayAccess || Ranges.size() < 2) && 6032 "Cannot be a must access if there are multiple ranges."); 6033 return MayAccess; 6034 } 6035 6036 /// Return the instruction that causes the access with respect to the local 6037 /// scope of the associated attribute. 6038 Instruction *getLocalInst() const { return LocalI; } 6039 6040 /// Return the actual instruction that causes the access. 6041 Instruction *getRemoteInst() const { return RemoteI; } 6042 6043 /// Return true if the value written is not known yet. 6044 bool isWrittenValueYetUndetermined() const { return !Content; } 6045 6046 /// Return true if the value written cannot be determined at all. 6047 bool isWrittenValueUnknown() const { 6048 return Content.has_value() && !*Content; 6049 } 6050 6051 /// Set the value written to nullptr, i.e., unknown. 6052 void setWrittenValueUnknown() { Content = nullptr; } 6053 6054 /// Return the type associated with the access, if known. 6055 Type *getType() const { return Ty; } 6056 6057 /// Return the value writen, if any. 6058 Value *getWrittenValue() const { 6059 assert(!isWrittenValueYetUndetermined() && 6060 "Value needs to be determined before accessing it."); 6061 return *Content; 6062 } 6063 6064 /// Return the written value which can be `llvm::null` if it is not yet 6065 /// determined. 6066 std::optional<Value *> getContent() const { return Content; } 6067 6068 bool hasUniqueRange() const { return Ranges.isUnique(); } 6069 const AA::RangeTy &getUniqueRange() const { return Ranges.getUnique(); } 6070 6071 /// Add a range accessed by this Access. 6072 /// 6073 /// If there are multiple ranges, then this is a "may access". 6074 void addRange(int64_t Offset, int64_t Size) { 6075 Ranges.insert({Offset, Size}); 6076 if (!hasUniqueRange()) { 6077 Kind = AccessKind(Kind | AK_MAY); 6078 Kind = AccessKind(Kind & ~AK_MUST); 6079 } 6080 } 6081 6082 const RangeList &getRanges() const { return Ranges; } 6083 6084 using const_iterator = RangeList::const_iterator; 6085 const_iterator begin() const { return Ranges.begin(); } 6086 const_iterator end() const { return Ranges.end(); } 6087 6088 private: 6089 /// The instruction responsible for the access with respect to the local 6090 /// scope of the associated attribute. 6091 Instruction *LocalI; 6092 6093 /// The instruction responsible for the access. 6094 Instruction *RemoteI; 6095 6096 /// The value written, if any. `std::nullopt` means "not known yet", 6097 /// `nullptr` cannot be determined. 6098 std::optional<Value *> Content; 6099 6100 /// Set of potential ranges accessed from the base pointer. 6101 RangeList Ranges; 6102 6103 /// The access kind, e.g., READ, as bitset (could be more than one). 6104 AccessKind Kind; 6105 6106 /// The type of the content, thus the type read/written, can be null if not 6107 /// available. 6108 Type *Ty; 6109 }; 6110 6111 /// Create an abstract attribute view for the position \p IRP. 6112 static AAPointerInfo &createForPosition(const IRPosition &IRP, Attributor &A); 6113 6114 /// See AbstractAttribute::getName() 6115 const std::string getName() const override { return "AAPointerInfo"; } 6116 6117 /// See AbstractAttribute::getIdAddr() 6118 const char *getIdAddr() const override { return &ID; } 6119 6120 using OffsetBinsTy = DenseMap<AA::RangeTy, SmallSet<unsigned, 4>>; 6121 using const_bin_iterator = OffsetBinsTy::const_iterator; 6122 virtual const_bin_iterator begin() const = 0; 6123 virtual const_bin_iterator end() const = 0; 6124 virtual int64_t numOffsetBins() const = 0; 6125 6126 /// Call \p CB on all accesses that might interfere with \p Range and return 6127 /// true if all such accesses were known and the callback returned true for 6128 /// all of them, false otherwise. An access interferes with an offset-size 6129 /// pair if it might read or write that memory region. 6130 virtual bool forallInterferingAccesses( 6131 AA::RangeTy Range, function_ref<bool(const Access &, bool)> CB) const = 0; 6132 6133 /// Call \p CB on all accesses that might interfere with \p I and 6134 /// return true if all such accesses were known and the callback returned true 6135 /// for all of them, false otherwise. In contrast to forallInterferingAccesses 6136 /// this function will perform reasoning to exclude write accesses that cannot 6137 /// affect the load even if they on the surface look as if they would. The 6138 /// flag \p HasBeenWrittenTo will be set to true if we know that \p I does not 6139 /// read the initial value of the underlying memory. If \p SkipCB is given and 6140 /// returns false for a potentially interfering access, that access is not 6141 /// checked for actual interference. 6142 virtual bool forallInterferingAccesses( 6143 Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I, 6144 bool FindInterferingWrites, bool FindInterferingReads, 6145 function_ref<bool(const Access &, bool)> CB, bool &HasBeenWrittenTo, 6146 AA::RangeTy &Range, 6147 function_ref<bool(const Access &)> SkipCB = nullptr) const = 0; 6148 6149 /// This function should return true if the type of the \p AA is AAPointerInfo 6150 static bool classof(const AbstractAttribute *AA) { 6151 return (AA->getIdAddr() == &ID); 6152 } 6153 6154 /// Unique ID (due to the unique address) 6155 static const char ID; 6156 }; 6157 6158 raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &); 6159 6160 /// An abstract attribute for getting assumption information. 6161 struct AAAssumptionInfo 6162 : public StateWrapper<SetState<StringRef>, AbstractAttribute, 6163 DenseSet<StringRef>> { 6164 using Base = 6165 StateWrapper<SetState<StringRef>, AbstractAttribute, DenseSet<StringRef>>; 6166 6167 AAAssumptionInfo(const IRPosition &IRP, Attributor &A, 6168 const DenseSet<StringRef> &Known) 6169 : Base(IRP, Known) {} 6170 6171 /// Returns true if the assumption set contains the assumption \p Assumption. 6172 virtual bool hasAssumption(const StringRef Assumption) const = 0; 6173 6174 /// Create an abstract attribute view for the position \p IRP. 6175 static AAAssumptionInfo &createForPosition(const IRPosition &IRP, 6176 Attributor &A); 6177 6178 /// See AbstractAttribute::getName() 6179 const std::string getName() const override { return "AAAssumptionInfo"; } 6180 6181 /// See AbstractAttribute::getIdAddr() 6182 const char *getIdAddr() const override { return &ID; } 6183 6184 /// This function should return true if the type of the \p AA is 6185 /// AAAssumptionInfo 6186 static bool classof(const AbstractAttribute *AA) { 6187 return (AA->getIdAddr() == &ID); 6188 } 6189 6190 /// Unique ID (due to the unique address) 6191 static const char ID; 6192 }; 6193 6194 /// An abstract attribute for getting all assumption underlying objects. 6195 struct AAUnderlyingObjects : AbstractAttribute { 6196 AAUnderlyingObjects(const IRPosition &IRP) : AbstractAttribute(IRP) {} 6197 6198 /// See AbstractAttribute::isValidIRPositionForInit 6199 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 6200 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 6201 return false; 6202 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 6203 } 6204 6205 /// See AbstractAttribute::requiresCallersForArgOrFunction 6206 static bool requiresCallersForArgOrFunction() { return true; } 6207 6208 /// Create an abstract attribute biew for the position \p IRP. 6209 static AAUnderlyingObjects &createForPosition(const IRPosition &IRP, 6210 Attributor &A); 6211 6212 /// See AbstractAttribute::getName() 6213 const std::string getName() const override { return "AAUnderlyingObjects"; } 6214 6215 /// See AbstractAttribute::getIdAddr() 6216 const char *getIdAddr() const override { return &ID; } 6217 6218 /// This function should return true if the type of the \p AA is 6219 /// AAUnderlyingObjects. 6220 static bool classof(const AbstractAttribute *AA) { 6221 return (AA->getIdAddr() == &ID); 6222 } 6223 6224 /// Unique ID (due to the unique address) 6225 static const char ID; 6226 6227 /// Check \p Pred on all underlying objects in \p Scope collected so far. 6228 /// 6229 /// This method will evaluate \p Pred on all underlying objects in \p Scope 6230 /// collected so far and return true if \p Pred holds on all of them. 6231 virtual bool 6232 forallUnderlyingObjects(function_ref<bool(Value &)> Pred, 6233 AA::ValueScope Scope = AA::Interprocedural) const = 0; 6234 }; 6235 6236 /// An abstract interface for address space information. 6237 struct AAAddressSpace : public StateWrapper<BooleanState, AbstractAttribute> { 6238 AAAddressSpace(const IRPosition &IRP, Attributor &A) 6239 : StateWrapper<BooleanState, AbstractAttribute>(IRP) {} 6240 6241 /// See AbstractAttribute::isValidIRPositionForInit 6242 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 6243 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 6244 return false; 6245 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 6246 } 6247 6248 /// See AbstractAttribute::requiresCallersForArgOrFunction 6249 static bool requiresCallersForArgOrFunction() { return true; } 6250 6251 /// Return the address space of the associated value. \p NoAddressSpace is 6252 /// returned if the associated value is dead. This functions is not supposed 6253 /// to be called if the AA is invalid. 6254 virtual int32_t getAddressSpace() const = 0; 6255 6256 /// Create an abstract attribute view for the position \p IRP. 6257 static AAAddressSpace &createForPosition(const IRPosition &IRP, 6258 Attributor &A); 6259 6260 /// See AbstractAttribute::getName() 6261 const std::string getName() const override { return "AAAddressSpace"; } 6262 6263 /// See AbstractAttribute::getIdAddr() 6264 const char *getIdAddr() const override { return &ID; } 6265 6266 /// This function should return true if the type of the \p AA is 6267 /// AAAssumptionInfo 6268 static bool classof(const AbstractAttribute *AA) { 6269 return (AA->getIdAddr() == &ID); 6270 } 6271 6272 // No address space which indicates the associated value is dead. 6273 static const int32_t NoAddressSpace = -1; 6274 6275 /// Unique ID (due to the unique address) 6276 static const char ID; 6277 }; 6278 6279 struct AAAllocationInfo : public StateWrapper<BooleanState, AbstractAttribute> { 6280 AAAllocationInfo(const IRPosition &IRP, Attributor &A) 6281 : StateWrapper<BooleanState, AbstractAttribute>(IRP) {} 6282 6283 /// See AbstractAttribute::isValidIRPositionForInit 6284 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 6285 if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) 6286 return false; 6287 return AbstractAttribute::isValidIRPositionForInit(A, IRP); 6288 } 6289 6290 /// Create an abstract attribute view for the position \p IRP. 6291 static AAAllocationInfo &createForPosition(const IRPosition &IRP, 6292 Attributor &A); 6293 6294 virtual std::optional<TypeSize> getAllocatedSize() const = 0; 6295 6296 /// See AbstractAttribute::getName() 6297 const std::string getName() const override { return "AAAllocationInfo"; } 6298 6299 /// See AbstractAttribute::getIdAddr() 6300 const char *getIdAddr() const override { return &ID; } 6301 6302 /// This function should return true if the type of the \p AA is 6303 /// AAAllocationInfo 6304 static bool classof(const AbstractAttribute *AA) { 6305 return (AA->getIdAddr() == &ID); 6306 } 6307 6308 constexpr static const std::optional<TypeSize> HasNoAllocationSize = 6309 std::optional<TypeSize>(TypeSize(-1, true)); 6310 6311 static const char ID; 6312 }; 6313 6314 /// An abstract interface for llvm::GlobalValue information interference. 6315 struct AAGlobalValueInfo 6316 : public StateWrapper<BooleanState, AbstractAttribute> { 6317 AAGlobalValueInfo(const IRPosition &IRP, Attributor &A) 6318 : StateWrapper<BooleanState, AbstractAttribute>(IRP) {} 6319 6320 /// See AbstractAttribute::isValidIRPositionForInit 6321 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 6322 if (IRP.getPositionKind() != IRPosition::IRP_FLOAT) 6323 return false; 6324 auto *GV = dyn_cast<GlobalValue>(&IRP.getAnchorValue()); 6325 if (!GV) 6326 return false; 6327 return GV->hasLocalLinkage(); 6328 } 6329 6330 /// Create an abstract attribute view for the position \p IRP. 6331 static AAGlobalValueInfo &createForPosition(const IRPosition &IRP, 6332 Attributor &A); 6333 6334 /// Return true iff \p U is a potential use of the associated global value. 6335 virtual bool isPotentialUse(const Use &U) const = 0; 6336 6337 /// See AbstractAttribute::getName() 6338 const std::string getName() const override { return "AAGlobalValueInfo"; } 6339 6340 /// See AbstractAttribute::getIdAddr() 6341 const char *getIdAddr() const override { return &ID; } 6342 6343 /// This function should return true if the type of the \p AA is 6344 /// AAGlobalValueInfo 6345 static bool classof(const AbstractAttribute *AA) { 6346 return (AA->getIdAddr() == &ID); 6347 } 6348 6349 /// Unique ID (due to the unique address) 6350 static const char ID; 6351 }; 6352 6353 /// An abstract interface for indirect call information interference. 6354 struct AAIndirectCallInfo 6355 : public StateWrapper<BooleanState, AbstractAttribute> { 6356 AAIndirectCallInfo(const IRPosition &IRP, Attributor &A) 6357 : StateWrapper<BooleanState, AbstractAttribute>(IRP) {} 6358 6359 /// See AbstractAttribute::isValidIRPositionForInit 6360 static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { 6361 if (IRP.getPositionKind() != IRPosition::IRP_CALL_SITE) 6362 return false; 6363 auto *CB = cast<CallBase>(IRP.getCtxI()); 6364 return CB->getOpcode() == Instruction::Call && CB->isIndirectCall() && 6365 !CB->isMustTailCall(); 6366 } 6367 6368 /// Create an abstract attribute view for the position \p IRP. 6369 static AAIndirectCallInfo &createForPosition(const IRPosition &IRP, 6370 Attributor &A); 6371 6372 /// Call \CB on each potential callee value and return true if all were known 6373 /// and \p CB returned true on all of them. Otherwise, return false. 6374 virtual bool foreachCallee(function_ref<bool(Function *)> CB) const = 0; 6375 6376 /// See AbstractAttribute::getName() 6377 const std::string getName() const override { return "AAIndirectCallInfo"; } 6378 6379 /// See AbstractAttribute::getIdAddr() 6380 const char *getIdAddr() const override { return &ID; } 6381 6382 /// This function should return true if the type of the \p AA is 6383 /// AAIndirectCallInfo 6384 /// This function should return true if the type of the \p AA is 6385 /// AADenormalFPMath. 6386 static bool classof(const AbstractAttribute *AA) { 6387 return (AA->getIdAddr() == &ID); 6388 } 6389 6390 /// Unique ID (due to the unique address) 6391 static const char ID; 6392 }; 6393 6394 /// An abstract Attribute for specializing "dynamic" components of 6395 /// "denormal-fp-math" and "denormal-fp-math-f32" to a known denormal mode. 6396 struct AADenormalFPMath 6397 : public StateWrapper<DenormalFPMathState, AbstractAttribute> { 6398 using Base = StateWrapper<DenormalFPMathState, AbstractAttribute>; 6399 6400 AADenormalFPMath(const IRPosition &IRP, Attributor &A) : Base(IRP) {} 6401 6402 /// Create an abstract attribute view for the position \p IRP. 6403 static AADenormalFPMath &createForPosition(const IRPosition &IRP, 6404 Attributor &A); 6405 6406 /// See AbstractAttribute::getName() 6407 const std::string getName() const override { return "AADenormalFPMath"; } 6408 6409 /// See AbstractAttribute::getIdAddr() 6410 const char *getIdAddr() const override { return &ID; } 6411 6412 /// This function should return true if the type of the \p AA is 6413 /// AADenormalFPMath. 6414 static bool classof(const AbstractAttribute *AA) { 6415 return (AA->getIdAddr() == &ID); 6416 } 6417 6418 /// Unique ID (due to the unique address) 6419 static const char ID; 6420 }; 6421 6422 raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &); 6423 6424 /// Run options, used by the pass manager. 6425 enum AttributorRunOption { 6426 NONE = 0, 6427 MODULE = 1 << 0, 6428 CGSCC = 1 << 1, 6429 ALL = MODULE | CGSCC 6430 }; 6431 6432 namespace AA { 6433 /// Helper to avoid creating an AA for IR Attributes that might already be set. 6434 template <Attribute::AttrKind AK, typename AAType = AbstractAttribute> 6435 bool hasAssumedIRAttr(Attributor &A, const AbstractAttribute *QueryingAA, 6436 const IRPosition &IRP, DepClassTy DepClass, bool &IsKnown, 6437 bool IgnoreSubsumingPositions = false, 6438 const AAType **AAPtr = nullptr) { 6439 IsKnown = false; 6440 switch (AK) { 6441 #define CASE(ATTRNAME, AANAME, ...) \ 6442 case Attribute::ATTRNAME: { \ 6443 if (AANAME::isImpliedByIR(A, IRP, AK, IgnoreSubsumingPositions)) \ 6444 return IsKnown = true; \ 6445 if (!QueryingAA) \ 6446 return false; \ 6447 const auto *AA = A.getAAFor<AANAME>(*QueryingAA, IRP, DepClass); \ 6448 if (AAPtr) \ 6449 *AAPtr = reinterpret_cast<const AAType *>(AA); \ 6450 if (!AA || !AA->isAssumed(__VA_ARGS__)) \ 6451 return false; \ 6452 IsKnown = AA->isKnown(__VA_ARGS__); \ 6453 return true; \ 6454 } 6455 CASE(NoUnwind, AANoUnwind, ); 6456 CASE(WillReturn, AAWillReturn, ); 6457 CASE(NoFree, AANoFree, ); 6458 CASE(NoCapture, AANoCapture, ); 6459 CASE(NoRecurse, AANoRecurse, ); 6460 CASE(NoReturn, AANoReturn, ); 6461 CASE(NoSync, AANoSync, ); 6462 CASE(NoAlias, AANoAlias, ); 6463 CASE(NonNull, AANonNull, ); 6464 CASE(MustProgress, AAMustProgress, ); 6465 CASE(NoUndef, AANoUndef, ); 6466 CASE(ReadNone, AAMemoryBehavior, AAMemoryBehavior::NO_ACCESSES); 6467 CASE(ReadOnly, AAMemoryBehavior, AAMemoryBehavior::NO_WRITES); 6468 CASE(WriteOnly, AAMemoryBehavior, AAMemoryBehavior::NO_READS); 6469 #undef CASE 6470 default: 6471 llvm_unreachable("hasAssumedIRAttr not available for this attribute kind"); 6472 }; 6473 } 6474 } // namespace AA 6475 6476 } // end namespace llvm 6477 6478 #endif // LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H 6479