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