LLVM 19.0.0git
Attributor.h
Go to the documentation of this file.
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"
105#include "llvm/ADT/SetVector.h"
106#include "llvm/ADT/SmallSet.h"
107#include "llvm/ADT/iterator.h"
109#include "llvm/Analysis/CFG.h"
119#include "llvm/IR/Attributes.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"
130#include "llvm/Support/Casting.h"
134#include "llvm/Support/ModRef.h"
139
140#include <limits>
141#include <map>
142#include <optional>
143
144namespace llvm {
145
146class DataLayout;
147class LLVMContext;
148class Pass;
149template <typename Fn> class function_ref;
150struct AADepGraphNode;
151struct AADepGraph;
152struct Attributor;
153struct AbstractAttribute;
154struct InformationCache;
155struct AAIsDead;
156struct AttributorCallGraph;
157struct IRPosition;
158
159class Function;
160
161/// Abstract Attribute helper functions.
162namespace AA {
164
165enum 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).
174bool 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.
179enum ValueScope : uint8_t {
183};
184
185struct ValueAndContext : public std::pair<Value *, const Instruction *> {
186 using Base = std::pair<Value *, const Instruction *>;
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.
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.
205bool 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.
210bool 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.
215bool 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.
220Value *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
230std::optional<Value *>
231combineOptionalValuesInAAValueLatice(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.
236struct RangeTy {
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.
247 }
248
249 /// Return true if offset and size are unknown, thus this is the default
250 /// unknown object.
253 }
254
255 /// Return true if the offset and size are unassigned.
256 bool isUnassigned() const {
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
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;
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
314 OS << "[" << R.Offset << ", " << R.Size << "]";
315 return OS;
316}
317
318inline bool operator==(const RangeTy &A, const RangeTy &B) {
319 return A.Offset == B.Offset && A.Size == B.Size;
320}
321
322inline 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.
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.
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.
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.
364bool 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.
369bool 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.
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.
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.
395 const AbstractAttribute &QueryingAA);
396
397/// Return true if \p I is potentially affected by a barrier.
399 const AbstractAttribute &QueryingAA);
401 const AbstractAttribute &QueryingAA,
402 const Instruction *CtxI);
403} // namespace AA
404
405template <>
406struct DenseMapInfo<AA::ValueAndContext>
407 : public DenseMapInfo<AA::ValueAndContext::Base> {
410 return Base::getEmptyKey();
411 }
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
425template <>
426struct DenseMapInfo<AA::ValueScope> : public DenseMapInfo<unsigned char> {
428 static inline AA::ValueScope getEmptyKey() {
429 return AA::ValueScope(Base::getEmptyKey());
430 }
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
443template <>
444struct DenseMapInfo<const AA::InstExclusionSetTy *>
445 : public DenseMapInfo<void *> {
447 static inline const AA::InstExclusionSetTy *getEmptyKey() {
448 return static_cast<const AA::InstExclusionSetTy *>(super::getEmptyKey());
449 }
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)
459 return H;
460 }
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.
480extern unsigned MaxInitializationChainLength;
481
482///{
483enum class ChangeStatus {
484 CHANGED,
485 UNCHANGED,
486};
487
492
493enum 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
502public:
503 virtual ~AADepGraphNode() = default;
506
507protected:
508 /// Set of dependency graph nodes which should be updated if this one
509 /// is updated. The bit encodes if it is optional.
511
512 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
514 return cast<AbstractAttribute>(DT.getPointer());
515 }
516
517 operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
518
519public:
523
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
545 AADepGraph() = default;
546 ~AADepGraph() = default;
547
549 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
550 using iterator =
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.
558
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.
581 // NOTE: In the future this definition can be changed to support recursive
582 // functions.
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))
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)),
657 }
658
659 /// Create a position describing the argument of \p ACS at position \p ArgNo.
661 unsigned ArgNo) {
662 if (ACS.getNumArgOperands() <= ArgNo)
663 return IRPosition();
664 int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
665 if (CSArgNo >= 0)
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
677 const CallBaseContext *CBContext = nullptr) {
678 if (IRP.isAnyCallSitePosition()) {
680 cast<CallBase>(IRP.getAnchorValue()));
681 }
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.
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.
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.
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()) {
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()) {
745 return true;
746 default:
747 return false;
748 };
749 }
750
751 /// Return the Function surrounding the anchor value.
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.
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.
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.
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()) {
816 break;
827 }
829 "There is no attribute index for a floating or invalid position!");
830 }
831
832 /// Return the value attributes are attached to.
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.
841 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
842 return CB->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 {
858 "Only valid for function/call site positions!");
859 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
860 return CB->arg_size();
862 }
863
864 /// Return theargument \p ArgNo associated with this function or call site
865 /// scope.
866 Value *getArg(unsigned ArgNo) const {
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.
877 char EncodingBits = getEncodingBits();
878 if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
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
893 return IRP_FLOAT;
894 }
895
897 switch (getPositionKind()) {
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()) {
912 return true;
913 default:
914 return false;
915 }
916 }
917
918 /// Return the same position without the call base context.
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;
936 ///}
937
938 /// Conversion into a void * to allow reuse of pointer hashing.
939 operator void *() const { return Enc.getOpaqueValue(); }
940
941private:
942 /// Private constructor for special values only!
943 explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr)
944 : CBContext(CBContext) {
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) {
954 llvm_unreachable("Cannot create invalid IRP with an anchor value!");
955 break;
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;
965 Enc = {&AnchorVal, ENC_VALUE};
966 break;
969 Enc = {&AnchorVal, ENC_RETURNED_VALUE};
970 break;
972 Enc = {&AnchorVal, ENC_VALUE};
973 break;
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()) {
991 return cast<Argument>(getAsValuePtr())->getArgNo();
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) {
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.
1071template <> struct DenseMapInfo<IRPosition> {
1072 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
1073 static inline IRPosition getTombstoneKey() {
1075 }
1076 static unsigned getHashValue(const IRPosition &IRP) {
1077 return (DenseMapInfo<void *>::getHashValue(IRP) << 4) ^
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)
1111 SmallVector<IRPosition, 4> IRPositions;
1112 using iterator = decltype(IRPositions)::iterator;
1113
1114public:
1116 iterator begin() { return IRPositions.begin(); }
1117 iterator end() { return IRPositions.end(); }
1118};
1119
1120/// Wrapper for FunctionAnalysisManager.
1122 // The client may be running the old pass manager, in which case, we need to
1123 // map the requested Analysis to its equivalent wrapper in the old pass
1124 // manager. The scheme implemented here does not require every Analysis to be
1125 // updated. Only those new analyses that the client cares about in the old
1126 // pass manager need to expose a LegacyWrapper type, and that wrapper should
1127 // support a getResult() method that matches the new Analysis.
1128 //
1129 // We need SFINAE to check for the LegacyWrapper, but function templates don't
1130 // allow partial specialization, which is needed in this case. So instead, we
1131 // use a constexpr bool to perform the SFINAE, and then use this information
1132 // inside the function template.
1133 template <typename, typename = void>
1134 static constexpr bool HasLegacyWrapper = false;
1135
1136 template <typename Analysis>
1137 typename Analysis::Result *getAnalysis(const Function &F,
1138 bool RequestCachedOnly = false) {
1139 if (!LegacyPass && !FAM)
1140 return nullptr;
1141 if (FAM) {
1142 if (CachedOnly || RequestCachedOnly)
1143 return FAM->getCachedResult<Analysis>(const_cast<Function &>(F));
1144 return &FAM->getResult<Analysis>(const_cast<Function &>(F));
1145 }
1146 if constexpr (HasLegacyWrapper<Analysis>) {
1147 if (!CachedOnly && !RequestCachedOnly)
1148 return &LegacyPass
1149 ->getAnalysis<typename Analysis::LegacyWrapper>(
1150 const_cast<Function &>(F))
1151 .getResult();
1152 if (auto *P =
1153 LegacyPass
1154 ->getAnalysisIfAvailable<typename Analysis::LegacyWrapper>())
1155 return &P->getResult();
1156 }
1157 return nullptr;
1158 }
1159
1160 /// Invalidates the analyses. Valid only when using the new pass manager.
1162 assert(FAM && "Can only be used from the new PM!");
1163 FAM->clear();
1164 }
1165
1166 AnalysisGetter(FunctionAnalysisManager &FAM, bool CachedOnly = false)
1167 : FAM(&FAM), CachedOnly(CachedOnly) {}
1168 AnalysisGetter(Pass *P, bool CachedOnly = false)
1169 : LegacyPass(P), CachedOnly(CachedOnly) {}
1170 AnalysisGetter() = default;
1171
1172private:
1173 FunctionAnalysisManager *FAM = nullptr;
1174 Pass *LegacyPass = nullptr;
1175
1176 /// If \p CachedOnly is true, no pass is created, just existing results are
1177 /// used. Also available per request.
1178 bool CachedOnly = false;
1179};
1180
1181template <typename Analysis>
1183 Analysis, std::void_t<typename Analysis::LegacyWrapper>> = true;
1184
1185/// Data structure to hold cached (LLVM-IR) information.
1186///
1187/// All attributes are given an InformationCache object at creation time to
1188/// avoid inspection of the IR by all of them individually. This default
1189/// InformationCache will hold information required by 'default' attributes,
1190/// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
1191/// is called.
1192///
1193/// If custom abstract attributes, registered manually through
1194/// Attributor::registerAA(...), need more information, especially if it is not
1195/// reusable, it is advised to inherit from the InformationCache and cast the
1196/// instance down in the abstract attributes.
1200 bool UseExplorer = true)
1201 : CGSCC(CGSCC), DL(M.getDataLayout()), Allocator(Allocator), AG(AG),
1202 TargetTriple(M.getTargetTriple()) {
1203 if (UseExplorer)
1205 /* ExploreInterBlock */ true, /* ExploreCFGForward */ true,
1206 /* ExploreCFGBackward */ true,
1207 /* LIGetter */
1208 [&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); },
1209 /* DTGetter */
1210 [&](const Function &F) {
1212 },
1213 /* PDTGetter */
1214 [&](const Function &F) {
1216 });
1217 }
1218
1220 // The FunctionInfo objects are allocated via a BumpPtrAllocator, we call
1221 // the destructor manually.
1222 for (auto &It : FuncInfoMap)
1223 It.getSecond()->~FunctionInfo();
1224 // Same is true for the instruction exclusions sets.
1226 for (auto *BES : BESets)
1227 BES->~InstExclusionSetTy();
1228 if (Explorer)
1229 Explorer->~MustBeExecutedContextExplorer();
1230 }
1231
1232 /// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is
1233 /// true, constant expression users are not given to \p CB but their uses are
1234 /// traversed transitively.
1235 template <typename CBTy>
1236 static void foreachUse(Function &F, CBTy CB,
1237 bool LookThroughConstantExprUses = true) {
1238 SmallVector<Use *, 8> Worklist(make_pointer_range(F.uses()));
1239
1240 for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
1241 Use &U = *Worklist[Idx];
1242
1243 // Allow use in constant bitcasts and simply look through them.
1244 if (LookThroughConstantExprUses && isa<ConstantExpr>(U.getUser())) {
1245 for (Use &CEU : cast<ConstantExpr>(U.getUser())->uses())
1246 Worklist.push_back(&CEU);
1247 continue;
1248 }
1249
1250 CB(U);
1251 }
1252 }
1253
1254 /// The CG-SCC the pass is run on, or nullptr if it is a module pass.
1255 const SetVector<Function *> *const CGSCC = nullptr;
1256
1257 /// A vector type to hold instructions.
1259
1260 /// A map type from opcodes to instructions with this opcode.
1262
1263 /// Return the map that relates "interesting" opcodes with all instructions
1264 /// with that opcode in \p F.
1266 return getFunctionInfo(F).OpcodeInstMap;
1267 }
1268
1269 /// Return the instructions in \p F that may read or write memory.
1271 return getFunctionInfo(F).RWInsts;
1272 }
1273
1274 /// Return MustBeExecutedContextExplorer
1276 return Explorer;
1277 }
1278
1279 /// Return TargetLibraryInfo for function \p F.
1282 }
1283
1284 /// Return true if \p Arg is involved in a must-tail call, thus the argument
1285 /// of the caller or callee.
1287 FunctionInfo &FI = getFunctionInfo(*Arg.getParent());
1288 return FI.CalledViaMustTail || FI.ContainsMustTailCall;
1289 }
1290
1291 bool isOnlyUsedByAssume(const Instruction &I) const {
1292 return AssumeOnlyValues.contains(&I);
1293 }
1294
1295 /// Invalidates the cached analyses. Valid only when using the new pass
1296 /// manager.
1298
1299 /// Return the analysis result from a pass \p AP for function \p F.
1300 template <typename AP>
1301 typename AP::Result *getAnalysisResultForFunction(const Function &F,
1302 bool CachedOnly = false) {
1303 return AG.getAnalysis<AP>(F, CachedOnly);
1304 }
1305
1306 /// Return datalayout used in the module.
1307 const DataLayout &getDL() { return DL; }
1308
1309 /// Return the map conaining all the knowledge we have from `llvm.assume`s.
1310 const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
1311
1312 /// Given \p BES, return a uniqued version.
1315 auto It = BESets.find(BES);
1316 if (It != BESets.end())
1317 return *It;
1318 auto *UniqueBES = new (Allocator) AA::InstExclusionSetTy(*BES);
1319 bool Success = BESets.insert(UniqueBES).second;
1320 (void)Success;
1321 assert(Success && "Expected only new entries to be added");
1322 return UniqueBES;
1323 }
1324
1325 /// Return true if the stack (llvm::Alloca) can be accessed by other threads.
1327
1328 /// Return true if the target is a GPU.
1330 return TargetTriple.isAMDGPU() || TargetTriple.isNVPTX();
1331 }
1332
1333 /// Return all functions that might be called indirectly, only valid for
1334 /// closed world modules (see isClosedWorldModule).
1337
1338private:
1339 struct FunctionInfo {
1340 ~FunctionInfo();
1341
1342 /// A nested map that remembers all instructions in a function with a
1343 /// certain instruction opcode (Instruction::getOpcode()).
1344 OpcodeInstMapTy OpcodeInstMap;
1345
1346 /// A map from functions to their instructions that may read or write
1347 /// memory.
1348 InstructionVectorTy RWInsts;
1349
1350 /// Function is called by a `musttail` call.
1351 bool CalledViaMustTail;
1352
1353 /// Function contains a `musttail` call.
1354 bool ContainsMustTailCall;
1355 };
1356
1357 /// A map type from functions to informatio about it.
1358 DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
1359
1360 /// Return information about the function \p F, potentially by creating it.
1361 FunctionInfo &getFunctionInfo(const Function &F) {
1362 FunctionInfo *&FI = FuncInfoMap[&F];
1363 if (!FI) {
1364 FI = new (Allocator) FunctionInfo();
1365 initializeInformationCache(F, *FI);
1366 }
1367 return *FI;
1368 }
1369
1370 /// Vector of functions that might be callable indirectly, i.a., via a
1371 /// function pointer.
1372 SmallVector<Function *> IndirectlyCallableFunctions;
1373
1374 /// Initialize the function information cache \p FI for the function \p F.
1375 ///
1376 /// This method needs to be called for all function that might be looked at
1377 /// through the information cache interface *prior* to looking at them.
1378 void initializeInformationCache(const Function &F, FunctionInfo &FI);
1379
1380 /// The datalayout used in the module.
1381 const DataLayout &DL;
1382
1383 /// The allocator used to allocate memory, e.g. for `FunctionInfo`s.
1384 BumpPtrAllocator &Allocator;
1385
1386 /// MustBeExecutedContextExplorer
1387 MustBeExecutedContextExplorer *Explorer = nullptr;
1388
1389 /// A map with knowledge retained in `llvm.assume` instructions.
1390 RetainedKnowledgeMap KnowledgeMap;
1391
1392 /// A container for all instructions that are only used by `llvm.assume`.
1393 SetVector<const Instruction *> AssumeOnlyValues;
1394
1395 /// Cache for block sets to allow reuse.
1396 DenseSet<const AA::InstExclusionSetTy *> BESets;
1397
1398 /// Getters for analysis.
1399 AnalysisGetter &AG;
1400
1401 /// Set of inlineable functions
1402 SmallPtrSet<const Function *, 8> InlineableFunctions;
1403
1404 /// The triple describing the target machine.
1405 Triple TargetTriple;
1406
1407 /// Give the Attributor access to the members so
1408 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
1409 friend struct Attributor;
1410};
1411
1412/// Configuration for the Attributor.
1414
1416
1417 /// Is the user of the Attributor a module pass or not. This determines what
1418 /// IR we can look at and modify. If it is a module pass we might deduce facts
1419 /// outside the initial function set and modify functions outside that set,
1420 /// but only as part of the optimization of the functions in the initial
1421 /// function set. For CGSCC passes we can look at the IR of the module slice
1422 /// but never run any deduction, or perform any modification, outside the
1423 /// initial function set (which we assume is the SCC).
1424 bool IsModulePass = true;
1425
1426 /// Flag to determine if we can delete functions or keep dead ones around.
1427 bool DeleteFns = true;
1428
1429 /// Flag to determine if we rewrite function signatures.
1431
1432 /// Flag to determine if we want to initialize all default AAs for an internal
1433 /// function marked live. See also: InitializationCallback>
1435
1436 /// Flag to determine if we should skip all liveness checks early on.
1437 bool UseLiveness = true;
1438
1439 /// Flag to indicate if the entire world is contained in this module, that
1440 /// is, no outside functions exist.
1442
1443 /// Callback function to be invoked on internal functions marked live.
1444 std::function<void(Attributor &A, const Function &F)> InitializationCallback =
1445 nullptr;
1446
1447 /// Callback function to determine if an indirect call targets should be made
1448 /// direct call targets (with an if-cascade).
1449 std::function<bool(Attributor &A, const AbstractAttribute &AA, CallBase &CB,
1450 Function &AssummedCallee)>
1452
1453 /// Helper to update an underlying call graph and to delete functions.
1455
1456 /// If not null, a set limiting the attribute opportunities.
1458
1459 /// Maximum number of iterations to run until fixpoint.
1460 std::optional<unsigned> MaxFixpointIterations;
1461
1462 /// A callback function that returns an ORE object from a Function pointer.
1463 ///{
1467 ///}
1468
1469 /// The name of the pass running the attributor, used to emit remarks.
1470 const char *PassName = nullptr;
1471
1474};
1475
1476/// A debug counter to limit the number of AAs created.
1477DEBUG_COUNTER(NumAbstractAttributes, "num-abstract-attributes",
1478 "How many AAs should be initialized");
1479
1480/// The fixpoint analysis framework that orchestrates the attribute deduction.
1481///
1482/// The Attributor provides a general abstract analysis framework (guided
1483/// fixpoint iteration) as well as helper functions for the deduction of
1484/// (LLVM-IR) attributes. However, also other code properties can be deduced,
1485/// propagated, and ultimately manifested through the Attributor framework. This
1486/// is particularly useful if these properties interact with attributes and a
1487/// co-scheduled deduction allows to improve the solution. Even if not, thus if
1488/// attributes/properties are completely isolated, they should use the
1489/// Attributor framework to reduce the number of fixpoint iteration frameworks
1490/// in the code base. Note that the Attributor design makes sure that isolated
1491/// attributes are not impacted, in any way, by others derived at the same time
1492/// if there is no cross-reasoning performed.
1493///
1494/// The public facing interface of the Attributor is kept simple and basically
1495/// allows abstract attributes to one thing, query abstract attributes
1496/// in-flight. There are two reasons to do this:
1497/// a) The optimistic state of one abstract attribute can justify an
1498/// optimistic state of another, allowing to framework to end up with an
1499/// optimistic (=best possible) fixpoint instead of one based solely on
1500/// information in the IR.
1501/// b) This avoids reimplementing various kinds of lookups, e.g., to check
1502/// for existing IR attributes, in favor of a single lookups interface
1503/// provided by an abstract attribute subclass.
1504///
1505/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1506/// described in the file comment.
1508
1509 /// Constructor
1510 ///
1511 /// \param Functions The set of functions we are deriving attributes for.
1512 /// \param InfoCache Cache to hold various information accessible for
1513 /// the abstract attributes.
1514 /// \param Configuration The Attributor configuration which determines what
1515 /// generic features to use.
1516 Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
1517 AttributorConfig Configuration);
1518
1519 ~Attributor();
1520
1521 /// Run the analyses until a fixpoint is reached or enforced (timeout).
1522 ///
1523 /// The attributes registered with this Attributor can be used after as long
1524 /// as the Attributor is not destroyed (it owns the attributes now).
1525 ///
1526 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
1527 ChangeStatus run();
1528
1529 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
1530 /// no abstract attribute is found equivalent positions are checked, see
1531 /// SubsumingPositionIterator. Thus, the returned abstract attribute
1532 /// might be anchored at a different position, e.g., the callee if \p IRP is a
1533 /// call base.
1534 ///
1535 /// This method is the only (supported) way an abstract attribute can retrieve
1536 /// information from another abstract attribute. As an example, take an
1537 /// abstract attribute that determines the memory access behavior for a
1538 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
1539 /// most optimistic information for other abstract attributes in-flight, e.g.
1540 /// the one reasoning about the "captured" state for the argument or the one
1541 /// reasoning on the memory access behavior of the function as a whole.
1542 ///
1543 /// If the DepClass enum is set to `DepClassTy::None` the dependence from
1544 /// \p QueryingAA to the return abstract attribute is not automatically
1545 /// recorded. This should only be used if the caller will record the
1546 /// dependence explicitly if necessary, thus if it the returned abstract
1547 /// attribute is used for reasoning. To record the dependences explicitly use
1548 /// the `Attributor::recordDependence` method.
1549 template <typename AAType>
1550 const AAType *getAAFor(const AbstractAttribute &QueryingAA,
1551 const IRPosition &IRP, DepClassTy DepClass) {
1552 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1553 /* ForceUpdate */ false);
1554 }
1555
1556 /// The version of getAAFor that allows to omit a querying abstract
1557 /// attribute. Using this after Attributor started running is restricted to
1558 /// only the Attributor itself. Initial seeding of AAs can be done via this
1559 /// function.
1560 /// NOTE: ForceUpdate is ignored in any stage other than the update stage.
1561 template <typename AAType>
1562 const AAType *getOrCreateAAFor(IRPosition IRP,
1563 const AbstractAttribute *QueryingAA,
1564 DepClassTy DepClass, bool ForceUpdate = false,
1565 bool UpdateAfterInit = true) {
1566 if (!shouldPropagateCallBaseContext(IRP))
1567 IRP = IRP.stripCallBaseContext();
1568
1569 if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1570 /* AllowInvalidState */ true)) {
1571 if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1572 updateAA(*AAPtr);
1573 return AAPtr;
1574 }
1575
1576 bool ShouldUpdateAA;
1577 if (!shouldInitialize<AAType>(IRP, ShouldUpdateAA))
1578 return nullptr;
1579
1580 if (!DebugCounter::shouldExecute(NumAbstractAttributes))
1581 return nullptr;
1582
1583 // No matching attribute found, create one.
1584 // Use the static create method.
1585 auto &AA = AAType::createForPosition(IRP, *this);
1586
1587 // Always register a new attribute to make sure we clean up the allocated
1588 // memory properly.
1589 registerAA(AA);
1590
1591 // If we are currenty seeding attributes, enforce seeding rules.
1592 if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1593 AA.getState().indicatePessimisticFixpoint();
1594 return &AA;
1595 }
1596
1597 // Bootstrap the new attribute with an initial update to propagate
1598 // information, e.g., function -> call site.
1599 {
1600 TimeTraceScope TimeScope("initialize", [&]() {
1601 return AA.getName() +
1602 std::to_string(AA.getIRPosition().getPositionKind());
1603 });
1604 ++InitializationChainLength;
1605 AA.initialize(*this);
1606 --InitializationChainLength;
1607 }
1608
1609 if (!ShouldUpdateAA) {
1610 AA.getState().indicatePessimisticFixpoint();
1611 return &AA;
1612 }
1613
1614 // Allow seeded attributes to declare dependencies.
1615 // Remember the seeding state.
1616 if (UpdateAfterInit) {
1617 AttributorPhase OldPhase = Phase;
1618 Phase = AttributorPhase::UPDATE;
1619
1620 updateAA(AA);
1621
1622 Phase = OldPhase;
1623 }
1624
1625 if (QueryingAA && AA.getState().isValidState())
1626 recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
1627 DepClass);
1628 return &AA;
1629 }
1630
1631 template <typename AAType>
1632 const AAType *getOrCreateAAFor(const IRPosition &IRP) {
1633 return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr,
1635 }
1636
1637 /// Return the attribute of \p AAType for \p IRP if existing and valid. This
1638 /// also allows non-AA users lookup.
1639 template <typename AAType>
1640 AAType *lookupAAFor(const IRPosition &IRP,
1641 const AbstractAttribute *QueryingAA = nullptr,
1643 bool AllowInvalidState = false) {
1644 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1645 "Cannot query an attribute with a type not derived from "
1646 "'AbstractAttribute'!");
1647 // Lookup the abstract attribute of type AAType. If found, return it after
1648 // registering a dependence of QueryingAA on the one returned attribute.
1649 AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP});
1650 if (!AAPtr)
1651 return nullptr;
1652
1653 AAType *AA = static_cast<AAType *>(AAPtr);
1654
1655 // Do not register a dependence on an attribute with an invalid state.
1656 if (DepClass != DepClassTy::NONE && QueryingAA &&
1657 AA->getState().isValidState())
1658 recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
1659 DepClass);
1660
1661 // Return nullptr if this attribute has an invalid state.
1662 if (!AllowInvalidState && !AA->getState().isValidState())
1663 return nullptr;
1664 return AA;
1665 }
1666
1667 /// Allows a query AA to request an update if a new query was received.
1669
1670 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
1671 /// \p FromAA changes \p ToAA should be updated as well.
1672 ///
1673 /// This method should be used in conjunction with the `getAAFor` method and
1674 /// with the DepClass enum passed to the method set to None. This can
1675 /// be beneficial to avoid false dependences but it requires the users of
1676 /// `getAAFor` to explicitly record true dependences through this method.
1677 /// The \p DepClass flag indicates if the dependence is striclty necessary.
1678 /// That means for required dependences, if \p FromAA changes to an invalid
1679 /// state, \p ToAA can be moved to a pessimistic fixpoint because it required
1680 /// information from \p FromAA but none are available anymore.
1681 void recordDependence(const AbstractAttribute &FromAA,
1682 const AbstractAttribute &ToAA, DepClassTy DepClass);
1683
1684 /// Introduce a new abstract attribute into the fixpoint analysis.
1685 ///
1686 /// Note that ownership of the attribute is given to the Attributor. It will
1687 /// invoke delete for the Attributor on destruction of the Attributor.
1688 ///
1689 /// Attributes are identified by their IR position (AAType::getIRPosition())
1690 /// and the address of their static member (see AAType::ID).
1691 template <typename AAType> AAType &registerAA(AAType &AA) {
1692 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1693 "Cannot register an attribute with a type not derived from "
1694 "'AbstractAttribute'!");
1695 // Put the attribute in the lookup map structure and the container we use to
1696 // keep track of all attributes.
1697 const IRPosition &IRP = AA.getIRPosition();
1698 AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
1699
1700 assert(!AAPtr && "Attribute already in map!");
1701 AAPtr = &AA;
1702
1703 // Register AA with the synthetic root only before the manifest stage.
1704 if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1707
1708 return AA;
1709 }
1710
1711 /// Return the internal information cache.
1712 InformationCache &getInfoCache() { return InfoCache; }
1713
1714 /// Return true if this is a module pass, false otherwise.
1715 bool isModulePass() const { return Configuration.IsModulePass; }
1716
1717 /// Return true if we should specialize the call site \b CB for the potential
1718 /// callee \p Fn.
1720 CallBase &CB, Function &Callee) {
1721 return Configuration.IndirectCalleeSpecializationCallback
1722 ? Configuration.IndirectCalleeSpecializationCallback(*this, AA,
1723 CB, Callee)
1724 : true;
1725 }
1726
1727 /// Return true if the module contains the whole world, thus, no outside
1728 /// functions exist.
1729 bool isClosedWorldModule() const;
1730
1731 /// Return true if we derive attributes for \p Fn
1732 bool isRunOn(Function &Fn) const { return isRunOn(&Fn); }
1733 bool isRunOn(Function *Fn) const {
1734 return Functions.empty() || Functions.count(Fn);
1735 }
1736
1737 template <typename AAType> bool shouldUpdateAA(const IRPosition &IRP) {
1738 // If this is queried in the manifest stage, we force the AA to indicate
1739 // pessimistic fixpoint immediately.
1740 if (Phase == AttributorPhase::MANIFEST || Phase == AttributorPhase::CLEANUP)
1741 return false;
1742
1743 Function *AssociatedFn = IRP.getAssociatedFunction();
1744
1745 if (IRP.isAnyCallSitePosition()) {
1746 // Check if we require a callee but there is none.
1747 if (!AssociatedFn && AAType::requiresCalleeForCallBase())
1748 return false;
1749
1750 // Check if we require non-asm but it is inline asm.
1751 if (AAType::requiresNonAsmForCallBase() &&
1752 cast<CallBase>(IRP.getAnchorValue()).isInlineAsm())
1753 return false;
1754 }
1755
1756 // Check if we require a calles but we can't see all.
1757 if (AAType::requiresCallersForArgOrFunction())
1760 if (!AssociatedFn->hasLocalLinkage())
1761 return false;
1762
1763 if (!AAType::isValidIRPositionForUpdate(*this, IRP))
1764 return false;
1765
1766 // We update only AAs associated with functions in the Functions set or
1767 // call sites of them.
1768 return (!AssociatedFn || isModulePass() || isRunOn(AssociatedFn) ||
1769 isRunOn(IRP.getAnchorScope()));
1770 }
1771
1772 template <typename AAType>
1773 bool shouldInitialize(const IRPosition &IRP, bool &ShouldUpdateAA) {
1774 if (!AAType::isValidIRPositionForInit(*this, IRP))
1775 return false;
1776
1777 if (Configuration.Allowed && !Configuration.Allowed->count(&AAType::ID))
1778 return false;
1779
1780 // For now we skip anything in naked and optnone functions.
1781 const Function *AnchorFn = IRP.getAnchorScope();
1782 if (AnchorFn && (AnchorFn->hasFnAttribute(Attribute::Naked) ||
1783 AnchorFn->hasFnAttribute(Attribute::OptimizeNone)))
1784 return false;
1785
1786 // Avoid too many nested initializations to prevent a stack overflow.
1787 if (InitializationChainLength > MaxInitializationChainLength)
1788 return false;
1789
1790 ShouldUpdateAA = shouldUpdateAA<AAType>(IRP);
1791
1792 return !AAType::hasTrivialInitializer() || ShouldUpdateAA;
1793 }
1794
1795 /// Determine opportunities to derive 'default' attributes in \p F and create
1796 /// abstract attribute objects for them.
1797 ///
1798 /// \param F The function that is checked for attribute opportunities.
1799 ///
1800 /// Note that abstract attribute instances are generally created even if the
1801 /// IR already contains the information they would deduce. The most important
1802 /// reason for this is the single interface, the one of the abstract attribute
1803 /// instance, which can be queried without the need to look at the IR in
1804 /// various places.
1806
1807 /// Determine whether the function \p F is IPO amendable
1808 ///
1809 /// If a function is exactly defined or it has alwaysinline attribute
1810 /// and is viable to be inlined, we say it is IPO amendable
1812 return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F) ||
1813 (Configuration.IPOAmendableCB && Configuration.IPOAmendableCB(F));
1814 }
1815
1816 /// Mark the internal function \p F as live.
1817 ///
1818 /// This will trigger the identification and initialization of attributes for
1819 /// \p F.
1821 assert(F.hasLocalLinkage() &&
1822 "Only local linkage is assumed dead initially.");
1823
1824 if (Configuration.DefaultInitializeLiveInternals)
1826 if (Configuration.InitializationCallback)
1827 Configuration.InitializationCallback(*this, F);
1828 }
1829
1830 /// Helper function to remove callsite.
1832 if (!CI)
1833 return;
1834
1835 Configuration.CGUpdater.removeCallSite(*CI);
1836 }
1837
1838 /// Record that \p U is to be replaces with \p NV after information was
1839 /// manifested. This also triggers deletion of trivially dead istructions.
1841 Value *&V = ToBeChangedUses[&U];
1842 if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
1843 isa_and_nonnull<UndefValue>(V)))
1844 return false;
1845 assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1846 "Use was registered twice for replacement with different values!");
1847 V = &NV;
1848 return true;
1849 }
1850
1851 /// Helper function to replace all uses associated with \p IRP with \p NV.
1852 /// Return true if there is any change. The flag \p ChangeDroppable indicates
1853 /// if dropppable uses should be changed too.
1855 bool ChangeDroppable = true) {
1857 auto *CB = cast<CallBase>(IRP.getCtxI());
1859 CB->getArgOperandUse(IRP.getCallSiteArgNo()), NV);
1860 }
1861 Value &V = IRP.getAssociatedValue();
1862 auto &Entry = ToBeChangedValues[&V];
1863 Value *CurNV = get<0>(Entry);
1864 if (CurNV && (CurNV->stripPointerCasts() == NV.stripPointerCasts() ||
1865 isa<UndefValue>(CurNV)))
1866 return false;
1867 assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) &&
1868 "Value replacement was registered twice with different values!");
1869 Entry = {&NV, ChangeDroppable};
1870 return true;
1871 }
1872
1873 /// Record that \p I is to be replaced with `unreachable` after information
1874 /// was manifested.
1876 ToBeChangedToUnreachableInsts.insert(I);
1877 }
1878
1879 /// Record that \p II has at least one dead successor block. This information
1880 /// is used, e.g., to replace \p II with a call, after information was
1881 /// manifested.
1883 InvokeWithDeadSuccessor.insert(&II);
1884 }
1885
1886 /// Record that \p I is deleted after information was manifested. This also
1887 /// triggers deletion of trivially dead istructions.
1888 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
1889
1890 /// Record that \p BB is deleted after information was manifested. This also
1891 /// triggers deletion of trivially dead istructions.
1892 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
1893
1894 // Record that \p BB is added during the manifest of an AA. Added basic blocks
1895 // are preserved in the IR.
1897 ManifestAddedBlocks.insert(&BB);
1898 }
1899
1900 /// Record that \p F is deleted after information was manifested.
1902 if (Configuration.DeleteFns)
1903 ToBeDeletedFunctions.insert(&F);
1904 }
1905
1906 /// Return the attributes of kind \p AK existing in the IR as operand bundles
1907 /// of an llvm.assume.
1910
1911 /// Return true if any kind in \p AKs existing in the IR at a position that
1912 /// will affect this one. See also getAttrs(...).
1913 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1914 /// e.g., the function position if this is an
1915 /// argument position, should be ignored.
1917 bool IgnoreSubsumingPositions = false,
1918 Attribute::AttrKind ImpliedAttributeKind = Attribute::None);
1919
1920 /// Return the attributes of any kind in \p AKs existing in the IR at a
1921 /// position that will affect this one. While each position can only have a
1922 /// single attribute of any kind in \p AKs, there are "subsuming" positions
1923 /// that could have an attribute as well. This method returns all attributes
1924 /// found in \p Attrs.
1925 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1926 /// e.g., the function position if this is an
1927 /// argument position, should be ignored.
1930 bool IgnoreSubsumingPositions = false);
1931
1932 /// Remove all \p AttrKinds attached to \p IRP.
1936
1937 /// Attach \p DeducedAttrs to \p IRP, if \p ForceReplace is set we do this
1938 /// even if the same attribute kind was already present.
1940 ArrayRef<Attribute> DeducedAttrs,
1941 bool ForceReplace = false);
1942
1943private:
1944 /// Helper to check \p Attrs for \p AK, if not found, check if \p
1945 /// AAType::isImpliedByIR is true, and if not, create AAType for \p IRP.
1946 template <Attribute::AttrKind AK, typename AAType>
1947 void checkAndQueryIRAttr(const IRPosition &IRP, AttributeSet Attrs);
1948
1949 /// Helper to apply \p CB on all attributes of type \p AttrDescs of \p IRP.
1950 template <typename DescTy>
1951 ChangeStatus updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs,
1952 function_ref<bool(const DescTy &, AttributeSet,
1954 CB);
1955
1956 /// Mapping from functions/call sites to their attributes.
1958
1959public:
1960 /// If \p IRP is assumed to be a constant, return it, if it is unclear yet,
1961 /// return std::nullopt, otherwise return `nullptr`.
1962 std::optional<Constant *> getAssumedConstant(const IRPosition &IRP,
1963 const AbstractAttribute &AA,
1964 bool &UsedAssumedInformation);
1965 std::optional<Constant *> getAssumedConstant(const Value &V,
1966 const AbstractAttribute &AA,
1967 bool &UsedAssumedInformation) {
1968 return getAssumedConstant(IRPosition::value(V), AA, UsedAssumedInformation);
1969 }
1970
1971 /// If \p V is assumed simplified, return it, if it is unclear yet,
1972 /// return std::nullopt, otherwise return `nullptr`.
1973 std::optional<Value *> getAssumedSimplified(const IRPosition &IRP,
1974 const AbstractAttribute &AA,
1975 bool &UsedAssumedInformation,
1976 AA::ValueScope S) {
1977 return getAssumedSimplified(IRP, &AA, UsedAssumedInformation, S);
1978 }
1979 std::optional<Value *> getAssumedSimplified(const Value &V,
1980 const AbstractAttribute &AA,
1981 bool &UsedAssumedInformation,
1982 AA::ValueScope S) {
1984 UsedAssumedInformation, S);
1985 }
1986
1987 /// If \p V is assumed simplified, return it, if it is unclear yet,
1988 /// return std::nullopt, otherwise return `nullptr`. Same as the public
1989 /// version except that it can be used without recording dependences on any \p
1990 /// AA.
1991 std::optional<Value *> getAssumedSimplified(const IRPosition &V,
1992 const AbstractAttribute *AA,
1993 bool &UsedAssumedInformation,
1994 AA::ValueScope S);
1995
1996 /// Try to simplify \p IRP and in the scope \p S. If successful, true is
1997 /// returned and all potential values \p IRP can take are put into \p Values.
1998 /// If the result in \p Values contains select or PHI instructions it means
1999 /// those could not be simplified to a single value. Recursive calls with
2000 /// these instructions will yield their respective potential values. If false
2001 /// is returned no other information is valid.
2002 bool getAssumedSimplifiedValues(const IRPosition &IRP,
2003 const AbstractAttribute *AA,
2006 bool &UsedAssumedInformation,
2007 bool RecurseForSelectAndPHI = true);
2008
2009 /// Register \p CB as a simplification callback.
2010 /// `Attributor::getAssumedSimplified` will use these callbacks before
2011 /// we it will ask `AAValueSimplify`. It is important to ensure this
2012 /// is called before `identifyDefaultAbstractAttributes`, assuming the
2013 /// latter is called at all.
2014 using SimplifictionCallbackTy = std::function<std::optional<Value *>(
2015 const IRPosition &, const AbstractAttribute *, bool &)>;
2017 const SimplifictionCallbackTy &CB) {
2018 SimplificationCallbacks[IRP].emplace_back(CB);
2019 }
2020
2021 /// Return true if there is a simplification callback for \p IRP.
2023 return SimplificationCallbacks.count(IRP);
2024 }
2025
2026 /// Register \p CB as a simplification callback.
2027 /// Similar to \p registerSimplificationCallback, the call back will be called
2028 /// first when we simplify a global variable \p GV.
2030 std::function<std::optional<Constant *>(
2031 const GlobalVariable &, const AbstractAttribute *, bool &)>;
2033 const GlobalVariable &GV,
2035 GlobalVariableSimplificationCallbacks[&GV].emplace_back(CB);
2036 }
2037
2038 /// Return true if there is a simplification callback for \p GV.
2040 return GlobalVariableSimplificationCallbacks.count(&GV);
2041 }
2042
2043 /// Return \p std::nullopt if there is no call back registered for \p GV or
2044 /// the call back is still not sure if \p GV can be simplified. Return \p
2045 /// nullptr if \p GV can't be simplified.
2046 std::optional<Constant *>
2048 const AbstractAttribute *AA,
2049 bool &UsedAssumedInformation) {
2050 assert(GlobalVariableSimplificationCallbacks.contains(&GV));
2051 for (auto &CB : GlobalVariableSimplificationCallbacks.lookup(&GV)) {
2052 auto SimplifiedGV = CB(GV, AA, UsedAssumedInformation);
2053 // For now we assume the call back will not return a std::nullopt.
2054 assert(SimplifiedGV.has_value() && "SimplifiedGV has not value");
2055 return *SimplifiedGV;
2056 }
2057 llvm_unreachable("there must be a callback registered");
2058 }
2059
2061 std::function<bool(Attributor &, const AbstractAttribute *)>;
2063 const VirtualUseCallbackTy &CB) {
2064 VirtualUseCallbacks[&V].emplace_back(CB);
2065 }
2066
2067private:
2068 /// The vector with all simplification callbacks registered by outside AAs.
2070 SimplificationCallbacks;
2071
2072 /// The vector with all simplification callbacks for global variables
2073 /// registered by outside AAs.
2074 DenseMap<const GlobalVariable *,
2076 GlobalVariableSimplificationCallbacks;
2077
2079 VirtualUseCallbacks;
2080
2081public:
2082 /// Translate \p V from the callee context into the call site context.
2083 std::optional<Value *>
2084 translateArgumentToCallSiteContent(std::optional<Value *> V, CallBase &CB,
2085 const AbstractAttribute &AA,
2086 bool &UsedAssumedInformation);
2087
2088 /// Return true if \p AA (or its context instruction) is assumed dead.
2089 ///
2090 /// If \p LivenessAA is not provided it is queried.
2091 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA,
2092 bool &UsedAssumedInformation,
2093 bool CheckBBLivenessOnly = false,
2094 DepClassTy DepClass = DepClassTy::OPTIONAL);
2095
2096 /// Return true if \p I is assumed dead.
2097 ///
2098 /// If \p LivenessAA is not provided it is queried.
2099 bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA,
2100 const AAIsDead *LivenessAA, bool &UsedAssumedInformation,
2101 bool CheckBBLivenessOnly = false,
2103 bool CheckForDeadStore = false);
2104
2105 /// Return true if \p U is assumed dead.
2106 ///
2107 /// If \p FnLivenessAA is not provided it is queried.
2108 bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA,
2109 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2110 bool CheckBBLivenessOnly = false,
2111 DepClassTy DepClass = DepClassTy::OPTIONAL);
2112
2113 /// Return true if \p IRP is assumed dead.
2114 ///
2115 /// If \p FnLivenessAA is not provided it is queried.
2116 bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA,
2117 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2118 bool CheckBBLivenessOnly = false,
2119 DepClassTy DepClass = DepClassTy::OPTIONAL);
2120
2121 /// Return true if \p BB is assumed dead.
2122 ///
2123 /// If \p LivenessAA is not provided it is queried.
2124 bool isAssumedDead(const BasicBlock &BB, const AbstractAttribute *QueryingAA,
2125 const AAIsDead *FnLivenessAA,
2126 DepClassTy DepClass = DepClassTy::OPTIONAL);
2127
2128 /// Check \p Pred on all potential Callees of \p CB.
2129 ///
2130 /// This method will evaluate \p Pred with all potential callees of \p CB as
2131 /// input and return true if \p Pred does. If some callees might be unknown
2132 /// this function will return false.
2133 bool checkForAllCallees(
2134 function_ref<bool(ArrayRef<const Function *> Callees)> Pred,
2135 const AbstractAttribute &QueryingAA, const CallBase &CB);
2136
2137 /// Check \p Pred on all (transitive) uses of \p V.
2138 ///
2139 /// This method will evaluate \p Pred on all (transitive) uses of the
2140 /// associated value and return true if \p Pred holds every time.
2141 /// If uses are skipped in favor of equivalent ones, e.g., if we look through
2142 /// memory, the \p EquivalentUseCB will be used to give the caller an idea
2143 /// what original used was replaced by a new one (or new ones). The visit is
2144 /// cut short if \p EquivalentUseCB returns false and the function will return
2145 /// false as well.
2146 bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
2147 const AbstractAttribute &QueryingAA, const Value &V,
2148 bool CheckBBLivenessOnly = false,
2149 DepClassTy LivenessDepClass = DepClassTy::OPTIONAL,
2150 bool IgnoreDroppableUses = true,
2151 function_ref<bool(const Use &OldU, const Use &NewU)>
2152 EquivalentUseCB = nullptr);
2153
2154 /// Emit a remark generically.
2155 ///
2156 /// This template function can be used to generically emit a remark. The
2157 /// RemarkKind should be one of the following:
2158 /// - OptimizationRemark to indicate a successful optimization attempt
2159 /// - OptimizationRemarkMissed to report a failed optimization attempt
2160 /// - OptimizationRemarkAnalysis to provide additional information about an
2161 /// optimization attempt
2162 ///
2163 /// The remark is built using a callback function \p RemarkCB that takes a
2164 /// RemarkKind as input and returns a RemarkKind.
2165 template <typename RemarkKind, typename RemarkCallBack>
2167 RemarkCallBack &&RemarkCB) const {
2168 if (!Configuration.OREGetter)
2169 return;
2170
2171 Function *F = I->getFunction();
2172 auto &ORE = Configuration.OREGetter(F);
2173
2174 if (RemarkName.starts_with("OMP"))
2175 ORE.emit([&]() {
2176 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I))
2177 << " [" << RemarkName << "]";
2178 });
2179 else
2180 ORE.emit([&]() {
2181 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I));
2182 });
2183 }
2184
2185 /// Emit a remark on a function.
2186 template <typename RemarkKind, typename RemarkCallBack>
2187 void emitRemark(Function *F, StringRef RemarkName,
2188 RemarkCallBack &&RemarkCB) const {
2189 if (!Configuration.OREGetter)
2190 return;
2191
2192 auto &ORE = Configuration.OREGetter(F);
2193
2194 if (RemarkName.starts_with("OMP"))
2195 ORE.emit([&]() {
2196 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F))
2197 << " [" << RemarkName << "]";
2198 });
2199 else
2200 ORE.emit([&]() {
2201 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F));
2202 });
2203 }
2204
2205 /// Helper struct used in the communication between an abstract attribute (AA)
2206 /// that wants to change the signature of a function and the Attributor which
2207 /// applies the changes. The struct is partially initialized with the
2208 /// information from the AA (see the constructor). All other members are
2209 /// provided by the Attributor prior to invoking any callbacks.
2211 /// Callee repair callback type
2212 ///
2213 /// The function repair callback is invoked once to rewire the replacement
2214 /// arguments in the body of the new function. The argument replacement info
2215 /// is passed, as build from the registerFunctionSignatureRewrite call, as
2216 /// well as the replacement function and an iteratore to the first
2217 /// replacement argument.
2218 using CalleeRepairCBTy = std::function<void(
2220
2221 /// Abstract call site (ACS) repair callback type
2222 ///
2223 /// The abstract call site repair callback is invoked once on every abstract
2224 /// call site of the replaced function (\see ReplacedFn). The callback needs
2225 /// to provide the operands for the call to the new replacement function.
2226 /// The number and type of the operands appended to the provided vector
2227 /// (second argument) is defined by the number and types determined through
2228 /// the replacement type vector (\see ReplacementTypes). The first argument
2229 /// is the ArgumentReplacementInfo object registered with the Attributor
2230 /// through the registerFunctionSignatureRewrite call.
2232 std::function<void(const ArgumentReplacementInfo &, AbstractCallSite,
2234
2235 /// Simple getters, see the corresponding members for details.
2236 ///{
2237
2238 Attributor &getAttributor() const { return A; }
2239 const Function &getReplacedFn() const { return ReplacedFn; }
2240 const Argument &getReplacedArg() const { return ReplacedArg; }
2241 unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
2243 return ReplacementTypes;
2244 }
2245
2246 ///}
2247
2248 private:
2249 /// Constructor that takes the argument to be replaced, the types of
2250 /// the replacement arguments, as well as callbacks to repair the call sites
2251 /// and new function after the replacement happened.
2253 ArrayRef<Type *> ReplacementTypes,
2254 CalleeRepairCBTy &&CalleeRepairCB,
2255 ACSRepairCBTy &&ACSRepairCB)
2256 : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
2257 ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
2258 CalleeRepairCB(std::move(CalleeRepairCB)),
2259 ACSRepairCB(std::move(ACSRepairCB)) {}
2260
2261 /// Reference to the attributor to allow access from the callbacks.
2262 Attributor &A;
2263
2264 /// The "old" function replaced by ReplacementFn.
2265 const Function &ReplacedFn;
2266
2267 /// The "old" argument replaced by new ones defined via ReplacementTypes.
2268 const Argument &ReplacedArg;
2269
2270 /// The types of the arguments replacing ReplacedArg.
2271 const SmallVector<Type *, 8> ReplacementTypes;
2272
2273 /// Callee repair callback, see CalleeRepairCBTy.
2274 const CalleeRepairCBTy CalleeRepairCB;
2275
2276 /// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
2277 const ACSRepairCBTy ACSRepairCB;
2278
2279 /// Allow access to the private members from the Attributor.
2280 friend struct Attributor;
2281 };
2282
2283 /// Check if we can rewrite a function signature.
2284 ///
2285 /// The argument \p Arg is replaced with new ones defined by the number,
2286 /// order, and types in \p ReplacementTypes.
2287 ///
2288 /// \returns True, if the replacement can be registered, via
2289 /// registerFunctionSignatureRewrite, false otherwise.
2291 ArrayRef<Type *> ReplacementTypes);
2292
2293 /// Register a rewrite for a function signature.
2294 ///
2295 /// The argument \p Arg is replaced with new ones defined by the number,
2296 /// order, and types in \p ReplacementTypes. The rewiring at the call sites is
2297 /// done through \p ACSRepairCB and at the callee site through
2298 /// \p CalleeRepairCB.
2299 ///
2300 /// \returns True, if the replacement was registered, false otherwise.
2302 Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2305
2306 /// Check \p Pred on all function call sites.
2307 ///
2308 /// This method will evaluate \p Pred on call sites and return
2309 /// true if \p Pred holds in every call sites. However, this is only possible
2310 /// all call sites are known, hence the function has internal linkage.
2311 /// If true is returned, \p UsedAssumedInformation is set if assumed
2312 /// information was used to skip or simplify potential call sites.
2314 const AbstractAttribute &QueryingAA,
2315 bool RequireAllCallSites,
2316 bool &UsedAssumedInformation);
2317
2318 /// Check \p Pred on all call sites of \p Fn.
2319 ///
2320 /// This method will evaluate \p Pred on call sites and return
2321 /// true if \p Pred holds in every call sites. However, this is only possible
2322 /// all call sites are known, hence the function has internal linkage.
2323 /// If true is returned, \p UsedAssumedInformation is set if assumed
2324 /// information was used to skip or simplify potential call sites.
2326 const Function &Fn, bool RequireAllCallSites,
2327 const AbstractAttribute *QueryingAA,
2328 bool &UsedAssumedInformation,
2329 bool CheckPotentiallyDead = false);
2330
2331 /// Check \p Pred on all values potentially returned by the function
2332 /// associated with \p QueryingAA.
2333 ///
2334 /// This is the context insensitive version of the method above.
2335 bool
2337 const AbstractAttribute &QueryingAA,
2339 bool RecurseForSelectAndPHI = true);
2340
2341 /// Check \p Pred on all instructions in \p Fn with an opcode present in
2342 /// \p Opcodes.
2343 ///
2344 /// This method will evaluate \p Pred on all instructions with an opcode
2345 /// present in \p Opcode and return true if \p Pred holds on all of them.
2347 const Function *Fn,
2348 const AbstractAttribute *QueryingAA,
2349 ArrayRef<unsigned> Opcodes,
2350 bool &UsedAssumedInformation,
2351 bool CheckBBLivenessOnly = false,
2352 bool CheckPotentiallyDead = false);
2353
2354 /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
2355 ///
2356 /// This method will evaluate \p Pred on all instructions with an opcode
2357 /// present in \p Opcode and return true if \p Pred holds on all of them.
2359 const AbstractAttribute &QueryingAA,
2360 ArrayRef<unsigned> Opcodes,
2361 bool &UsedAssumedInformation,
2362 bool CheckBBLivenessOnly = false,
2363 bool CheckPotentiallyDead = false);
2364
2365 /// Check \p Pred on all call-like instructions (=CallBased derived).
2366 ///
2367 /// See checkForAllCallLikeInstructions(...) for more information.
2369 const AbstractAttribute &QueryingAA,
2370 bool &UsedAssumedInformation,
2371 bool CheckBBLivenessOnly = false,
2372 bool CheckPotentiallyDead = false) {
2374 Pred, QueryingAA,
2375 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2376 (unsigned)Instruction::Call},
2377 UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead);
2378 }
2379
2380 /// Check \p Pred on all Read/Write instructions.
2381 ///
2382 /// This method will evaluate \p Pred on all instructions that read or write
2383 /// to memory present in the information cache and return true if \p Pred
2384 /// holds on all of them.
2386 AbstractAttribute &QueryingAA,
2387 bool &UsedAssumedInformation);
2388
2389 /// Create a shallow wrapper for \p F such that \p F has internal linkage
2390 /// afterwards. It also sets the original \p F 's name to anonymous
2391 ///
2392 /// A wrapper is a function with the same type (and attributes) as \p F
2393 /// that will only call \p F and return the result, if any.
2394 ///
2395 /// Assuming the declaration of looks like:
2396 /// rty F(aty0 arg0, ..., atyN argN);
2397 ///
2398 /// The wrapper will then look as follows:
2399 /// rty wrapper(aty0 arg0, ..., atyN argN) {
2400 /// return F(arg0, ..., argN);
2401 /// }
2402 ///
2403 static void createShallowWrapper(Function &F);
2404
2405 /// Returns true if the function \p F can be internalized. i.e. it has a
2406 /// compatible linkage.
2407 static bool isInternalizable(Function &F);
2408
2409 /// Make another copy of the function \p F such that the copied version has
2410 /// internal linkage afterwards and can be analysed. Then we replace all uses
2411 /// of the original function to the copied one
2412 ///
2413 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2414 /// linkage can be internalized because these linkages guarantee that other
2415 /// definitions with the same name have the same semantics as this one.
2416 ///
2417 /// This will only be run if the `attributor-allow-deep-wrappers` option is
2418 /// set, or if the function is called with \p Force set to true.
2419 ///
2420 /// If the function \p F failed to be internalized the return value will be a
2421 /// null pointer.
2422 static Function *internalizeFunction(Function &F, bool Force = false);
2423
2424 /// Make copies of each function in the set \p FnSet such that the copied
2425 /// version has internal linkage afterwards and can be analysed. Then we
2426 /// replace all uses of the original function to the copied one. The map
2427 /// \p FnMap contains a mapping of functions to their internalized versions.
2428 ///
2429 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2430 /// linkage can be internalized because these linkages guarantee that other
2431 /// definitions with the same name have the same semantics as this one.
2432 ///
2433 /// This version will internalize all the functions in the set \p FnSet at
2434 /// once and then replace the uses. This prevents internalized functions being
2435 /// called by external functions when there is an internalized version in the
2436 /// module.
2439
2440 /// Return the data layout associated with the anchor scope.
2441 const DataLayout &getDataLayout() const { return InfoCache.DL; }
2442
2443 /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
2445
2447 return CGModifiedFunctions;
2448 }
2449
2450private:
2451 /// This method will do fixpoint iteration until fixpoint or the
2452 /// maximum iteration count is reached.
2453 ///
2454 /// If the maximum iteration count is reached, This method will
2455 /// indicate pessimistic fixpoint on attributes that transitively depend
2456 /// on attributes that were scheduled for an update.
2457 void runTillFixpoint();
2458
2459 /// Gets called after scheduling, manifests attributes to the LLVM IR.
2460 ChangeStatus manifestAttributes();
2461
2462 /// Gets called after attributes have been manifested, cleans up the IR.
2463 /// Deletes dead functions, blocks and instructions.
2464 /// Rewrites function signitures and updates the call graph.
2465 ChangeStatus cleanupIR();
2466
2467 /// Identify internal functions that are effectively dead, thus not reachable
2468 /// from a live entry point. The functions are added to ToBeDeletedFunctions.
2469 void identifyDeadInternalFunctions();
2470
2471 /// Run `::update` on \p AA and track the dependences queried while doing so.
2472 /// Also adjust the state if we know further updates are not necessary.
2473 ChangeStatus updateAA(AbstractAttribute &AA);
2474
2475 /// Remember the dependences on the top of the dependence stack such that they
2476 /// may trigger further updates. (\see DependenceStack)
2477 void rememberDependences();
2478
2479 /// Determine if CallBase context in \p IRP should be propagated.
2480 bool shouldPropagateCallBaseContext(const IRPosition &IRP);
2481
2482 /// Apply all requested function signature rewrites
2483 /// (\see registerFunctionSignatureRewrite) and return Changed if the module
2484 /// was altered.
2486 rewriteFunctionSignatures(SmallSetVector<Function *, 8> &ModifiedFns);
2487
2488 /// Check if the Attribute \p AA should be seeded.
2489 /// See getOrCreateAAFor.
2490 bool shouldSeedAttribute(AbstractAttribute &AA);
2491
2492 /// A nested map to lookup abstract attributes based on the argument position
2493 /// on the outer level, and the addresses of the static member (AAType::ID) on
2494 /// the inner level.
2495 ///{
2496 using AAMapKeyTy = std::pair<const char *, IRPosition>;
2498 ///}
2499
2500 /// Map to remember all requested signature changes (= argument replacements).
2502 ArgumentReplacementMap;
2503
2504 /// The set of functions we are deriving attributes for.
2505 SetVector<Function *> &Functions;
2506
2507 /// The information cache that holds pre-processed (LLVM-IR) information.
2508 InformationCache &InfoCache;
2509
2510 /// Abstract Attribute dependency graph
2511 AADepGraph DG;
2512
2513 /// Set of functions for which we modified the content such that it might
2514 /// impact the call graph.
2515 SmallSetVector<Function *, 8> CGModifiedFunctions;
2516
2517 /// Information about a dependence. If FromAA is changed ToAA needs to be
2518 /// updated as well.
2519 struct DepInfo {
2520 const AbstractAttribute *FromAA;
2521 const AbstractAttribute *ToAA;
2522 DepClassTy DepClass;
2523 };
2524
2525 /// The dependence stack is used to track dependences during an
2526 /// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be
2527 /// recursive we might have multiple vectors of dependences in here. The stack
2528 /// size, should be adjusted according to the expected recursion depth and the
2529 /// inner dependence vector size to the expected number of dependences per
2530 /// abstract attribute. Since the inner vectors are actually allocated on the
2531 /// stack we can be generous with their size.
2532 using DependenceVector = SmallVector<DepInfo, 8>;
2533 SmallVector<DependenceVector *, 16> DependenceStack;
2534
2535 /// A set to remember the functions we already assume to be live and visited.
2536 DenseSet<const Function *> VisitedFunctions;
2537
2538 /// Uses we replace with a new value after manifest is done. We will remove
2539 /// then trivially dead instructions as well.
2540 SmallMapVector<Use *, Value *, 32> ToBeChangedUses;
2541
2542 /// Values we replace with a new value after manifest is done. We will remove
2543 /// then trivially dead instructions as well.
2544 SmallMapVector<Value *, PointerIntPair<Value *, 1, bool>, 32>
2545 ToBeChangedValues;
2546
2547 /// Instructions we replace with `unreachable` insts after manifest is done.
2548 SmallSetVector<WeakVH, 16> ToBeChangedToUnreachableInsts;
2549
2550 /// Invoke instructions with at least a single dead successor block.
2551 SmallSetVector<WeakVH, 16> InvokeWithDeadSuccessor;
2552
2553 /// A flag that indicates which stage of the process we are in. Initially, the
2554 /// phase is SEEDING. Phase is changed in `Attributor::run()`
2555 enum class AttributorPhase {
2556 SEEDING,
2557 UPDATE,
2558 MANIFEST,
2559 CLEANUP,
2560 } Phase = AttributorPhase::SEEDING;
2561
2562 /// The current initialization chain length. Tracked to avoid stack overflows.
2563 unsigned InitializationChainLength = 0;
2564
2565 /// Functions, blocks, and instructions we delete after manifest is done.
2566 ///
2567 ///{
2568 SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks;
2569 SmallSetVector<Function *, 8> ToBeDeletedFunctions;
2570 SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks;
2571 SmallSetVector<WeakVH, 8> ToBeDeletedInsts;
2572 ///}
2573
2574 /// Container with all the query AAs that requested an update via
2575 /// registerForUpdate.
2576 SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate;
2577
2578 /// User provided configuration for this Attributor instance.
2579 const AttributorConfig Configuration;
2580
2581 friend AADepGraph;
2582 friend AttributorCallGraph;
2583};
2584
2585/// An interface to query the internal state of an abstract attribute.
2586///
2587/// The abstract state is a minimal interface that allows the Attributor to
2588/// communicate with the abstract attributes about their internal state without
2589/// enforcing or exposing implementation details, e.g., the (existence of an)
2590/// underlying lattice.
2591///
2592/// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
2593/// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
2594/// was reached or (4) a pessimistic fixpoint was enforced.
2595///
2596/// All methods need to be implemented by the subclass. For the common use case,
2597/// a single boolean state or a bit-encoded state, the BooleanState and
2598/// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
2599/// attribute can inherit from them to get the abstract state interface and
2600/// additional methods to directly modify the state based if needed. See the
2601/// class comments for help.
2603 virtual ~AbstractState() = default;
2604
2605 /// Return if this abstract state is in a valid state. If false, no
2606 /// information provided should be used.
2607 virtual bool isValidState() const = 0;
2608
2609 /// Return if this abstract state is fixed, thus does not need to be updated
2610 /// if information changes as it cannot change itself.
2611 virtual bool isAtFixpoint() const = 0;
2612
2613 /// Indicate that the abstract state should converge to the optimistic state.
2614 ///
2615 /// This will usually make the optimistically assumed state the known to be
2616 /// true state.
2617 ///
2618 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
2620
2621 /// Indicate that the abstract state should converge to the pessimistic state.
2622 ///
2623 /// This will usually revert the optimistically assumed state to the known to
2624 /// be true state.
2625 ///
2626 /// \returns ChangeStatus::CHANGED as the assumed value may change.
2628};
2629
2630/// Simple state with integers encoding.
2631///
2632/// The interface ensures that the assumed bits are always a subset of the known
2633/// bits. Users can only add known bits and, except through adding known bits,
2634/// they can only remove assumed bits. This should guarantee monotonicity and
2635/// thereby the existence of a fixpoint (if used correctly). The fixpoint is
2636/// reached when the assumed and known state/bits are equal. Users can
2637/// force/inidicate a fixpoint. If an optimistic one is indicated, the known
2638/// state will catch up with the assumed one, for a pessimistic fixpoint it is
2639/// the other way around.
2640template <typename base_ty, base_ty BestState, base_ty WorstState>
2642 using base_t = base_ty;
2643
2644 IntegerStateBase() = default;
2646
2647 /// Return the best possible representable state.
2648 static constexpr base_t getBestState() { return BestState; }
2649 static constexpr base_t getBestState(const IntegerStateBase &) {
2650 return getBestState();
2651 }
2652
2653 /// Return the worst possible representable state.
2654 static constexpr base_t getWorstState() { return WorstState; }
2655 static constexpr base_t getWorstState(const IntegerStateBase &) {
2656 return getWorstState();
2657 }
2658
2659 /// See AbstractState::isValidState()
2660 /// NOTE: For now we simply pretend that the worst possible state is invalid.
2661 bool isValidState() const override { return Assumed != getWorstState(); }
2662
2663 /// See AbstractState::isAtFixpoint()
2664 bool isAtFixpoint() const override { return Assumed == Known; }
2665
2666 /// See AbstractState::indicateOptimisticFixpoint(...)
2668 Known = Assumed;
2670 }
2671
2672 /// See AbstractState::indicatePessimisticFixpoint(...)
2674 Assumed = Known;
2675 return ChangeStatus::CHANGED;
2676 }
2677
2678 /// Return the known state encoding
2679 base_t getKnown() const { return Known; }
2680
2681 /// Return the assumed state encoding.
2682 base_t getAssumed() const { return Assumed; }
2683
2684 /// Equality for IntegerStateBase.
2685 bool
2687 return this->getAssumed() == R.getAssumed() &&
2688 this->getKnown() == R.getKnown();
2689 }
2690
2691 /// Inequality for IntegerStateBase.
2692 bool
2694 return !(*this == R);
2695 }
2696
2697 /// "Clamp" this state with \p R. The result is subtype dependent but it is
2698 /// intended that only information assumed in both states will be assumed in
2699 /// this one afterwards.
2701 handleNewAssumedValue(R.getAssumed());
2702 }
2703
2704 /// "Clamp" this state with \p R. The result is subtype dependent but it is
2705 /// intended that information known in either state will be known in
2706 /// this one afterwards.
2708 handleNewKnownValue(R.getKnown());
2709 }
2710
2712 joinOR(R.getAssumed(), R.getKnown());
2713 }
2714
2716 joinAND(R.getAssumed(), R.getKnown());
2717 }
2718
2719protected:
2720 /// Handle a new assumed value \p Value. Subtype dependent.
2722
2723 /// Handle a new known value \p Value. Subtype dependent.
2725
2726 /// Handle a value \p Value. Subtype dependent.
2727 virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
2728
2729 /// Handle a new assumed value \p Value. Subtype dependent.
2730 virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
2731
2732 /// The known state encoding in an integer of type base_t.
2734
2735 /// The assumed state encoding in an integer of type base_t.
2737};
2738
2739/// Specialization of the integer state for a bit-wise encoding.
2740template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2741 base_ty WorstState = 0>
2743 : public IntegerStateBase<base_ty, BestState, WorstState> {
2745 using base_t = base_ty;
2746 BitIntegerState() = default;
2748
2749 /// Return true if the bits set in \p BitsEncoding are "known bits".
2750 bool isKnown(base_t BitsEncoding = BestState) const {
2751 return (this->Known & BitsEncoding) == BitsEncoding;
2752 }
2753
2754 /// Return true if the bits set in \p BitsEncoding are "assumed bits".
2755 bool isAssumed(base_t BitsEncoding = BestState) const {
2756 return (this->Assumed & BitsEncoding) == BitsEncoding;
2757 }
2758
2759 /// Add the bits in \p BitsEncoding to the "known bits".
2761 // Make sure we never miss any "known bits".
2762 this->Assumed |= Bits;
2763 this->Known |= Bits;
2764 return *this;
2765 }
2766
2767 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
2769 return intersectAssumedBits(~BitsEncoding);
2770 }
2771
2772 /// Remove the bits in \p BitsEncoding from the "known bits".
2774 this->Known = (this->Known & ~BitsEncoding);
2775 return *this;
2776 }
2777
2778 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
2780 // Make sure we never lose any "known bits".
2781 this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
2782 return *this;
2783 }
2784
2785private:
2786 void handleNewAssumedValue(base_t Value) override {
2788 }
2789 void handleNewKnownValue(base_t Value) override { addKnownBits(Value); }
2790 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2791 this->Known |= KnownValue;
2792 this->Assumed |= AssumedValue;
2793 }
2794 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2795 this->Known &= KnownValue;
2796 this->Assumed &= AssumedValue;
2797 }
2798};
2799
2800/// Specialization of the integer state for an increasing value, hence ~0u is
2801/// the best state and 0 the worst.
2802template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2803 base_ty WorstState = 0>
2805 : public IntegerStateBase<base_ty, BestState, WorstState> {
2807 using base_t = base_ty;
2808
2811
2812 /// Return the best possible representable state.
2813 static constexpr base_t getBestState() { return BestState; }
2814 static constexpr base_t
2816 return getBestState();
2817 }
2818
2819 /// Take minimum of assumed and \p Value.
2821 // Make sure we never lose "known value".
2822 this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
2823 return *this;
2824 }
2825
2826 /// Take maximum of known and \p Value.
2828 // Make sure we never lose "known value".
2829 this->Assumed = std::max(Value, this->Assumed);
2830 this->Known = std::max(Value, this->Known);
2831 return *this;
2832 }
2833
2834private:
2835 void handleNewAssumedValue(base_t Value) override {
2837 }
2838 void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
2839 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2840 this->Known = std::max(this->Known, KnownValue);
2841 this->Assumed = std::max(this->Assumed, AssumedValue);
2842 }
2843 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2844 this->Known = std::min(this->Known, KnownValue);
2845 this->Assumed = std::min(this->Assumed, AssumedValue);
2846 }
2847};
2848
2849/// Specialization of the integer state for a decreasing value, hence 0 is the
2850/// best state and ~0u the worst.
2851template <typename base_ty = uint32_t>
2852struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
2853 using base_t = base_ty;
2854
2855 /// Take maximum of assumed and \p Value.
2857 // Make sure we never lose "known value".
2858 this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
2859 return *this;
2860 }
2861
2862 /// Take minimum of known and \p Value.
2864 // Make sure we never lose "known value".
2865 this->Assumed = std::min(Value, this->Assumed);
2866 this->Known = std::min(Value, this->Known);
2867 return *this;
2868 }
2869
2870private:
2871 void handleNewAssumedValue(base_t Value) override {
2873 }
2874 void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
2875 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2876 this->Assumed = std::min(this->Assumed, KnownValue);
2877 this->Assumed = std::min(this->Assumed, AssumedValue);
2878 }
2879 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2880 this->Assumed = std::max(this->Assumed, KnownValue);
2881 this->Assumed = std::max(this->Assumed, AssumedValue);
2882 }
2883};
2884
2885/// Simple wrapper for a single bit (boolean) state.
2886struct BooleanState : public IntegerStateBase<bool, true, false> {
2889
2890 BooleanState() = default;
2892
2893 /// Set the assumed value to \p Value but never below the known one.
2894 void setAssumed(bool Value) { Assumed &= (Known | Value); }
2895
2896 /// Set the known and asssumed value to \p Value.
2897 void setKnown(bool Value) {
2898 Known |= Value;
2899 Assumed |= Value;
2900 }
2901
2902 /// Return true if the state is assumed to hold.
2903 bool isAssumed() const { return getAssumed(); }
2904
2905 /// Return true if the state is known to hold.
2906 bool isKnown() const { return getKnown(); }
2907
2908private:
2909 void handleNewAssumedValue(base_t Value) override {
2910 if (!Value)
2911 Assumed = Known;
2912 }
2913 void handleNewKnownValue(base_t Value) override {
2914 if (Value)
2915 Known = (Assumed = Value);
2916 }
2917 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2918 Known |= KnownValue;
2919 Assumed |= AssumedValue;
2920 }
2921 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2922 Known &= KnownValue;
2923 Assumed &= AssumedValue;
2924 }
2925};
2926
2927/// State for an integer range.
2929
2930 /// Bitwidth of the associated value.
2932
2933 /// State representing assumed range, initially set to empty.
2935
2936 /// State representing known range, initially set to [-inf, inf].
2938
2941 Known(ConstantRange::getFull(BitWidth)) {}
2942
2944 : BitWidth(CR.getBitWidth()), Assumed(CR),
2946
2947 /// Return the worst possible representable state.
2949 return ConstantRange::getFull(BitWidth);
2950 }
2951
2952 /// Return the best possible representable state.
2954 return ConstantRange::getEmpty(BitWidth);
2955 }
2957 return getBestState(IRS.getBitWidth());
2958 }
2959
2960 /// Return associated values' bit width.
2961 uint32_t getBitWidth() const { return BitWidth; }
2962
2963 /// See AbstractState::isValidState()
2964 bool isValidState() const override {
2965 return BitWidth > 0 && !Assumed.isFullSet();
2966 }
2967
2968 /// See AbstractState::isAtFixpoint()
2969 bool isAtFixpoint() const override { return Assumed == Known; }
2970
2971 /// See AbstractState::indicateOptimisticFixpoint(...)
2973 Known = Assumed;
2974 return ChangeStatus::CHANGED;
2975 }
2976
2977 /// See AbstractState::indicatePessimisticFixpoint(...)
2979 Assumed = Known;
2980 return ChangeStatus::CHANGED;
2981 }
2982
2983 /// Return the known state encoding
2984 ConstantRange getKnown() const { return Known; }
2985
2986 /// Return the assumed state encoding.
2988
2989 /// Unite assumed range with the passed state.
2991 // Don't lose a known range.
2993 }
2994
2995 /// See IntegerRangeState::unionAssumed(..).
2997 unionAssumed(R.getAssumed());
2998 }
2999
3000 /// Intersect known range with the passed state.
3004 }
3005
3006 /// See IntegerRangeState::intersectKnown(..).
3008 intersectKnown(R.getKnown());
3009 }
3010
3011 /// Equality for IntegerRangeState.
3012 bool operator==(const IntegerRangeState &R) const {
3013 return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
3014 }
3015
3016 /// "Clamp" this state with \p R. The result is subtype dependent but it is
3017 /// intended that only information assumed in both states will be assumed in
3018 /// this one afterwards.
3020 // NOTE: `^=` operator seems like `intersect` but in this case, we need to
3021 // take `union`.
3022 unionAssumed(R);
3023 return *this;
3024 }
3025
3027 // NOTE: `&=` operator seems like `intersect` but in this case, we need to
3028 // take `union`.
3029 Known = Known.unionWith(R.getKnown());
3030 Assumed = Assumed.unionWith(R.getAssumed());
3031 return *this;
3032 }
3033};
3034
3035/// Simple state for a set.
3036///
3037/// This represents a state containing a set of values. The interface supports
3038/// modelling sets that contain all possible elements. The state's internal
3039/// value is modified using union or intersection operations.
3040template <typename BaseTy> struct SetState : public AbstractState {
3041 /// A wrapper around a set that has semantics for handling unions and
3042 /// intersections with a "universal" set that contains all elements.
3044 /// Creates a universal set with no concrete elements or an empty set.
3045 SetContents(bool Universal) : Universal(Universal) {}
3046
3047 /// Creates a non-universal set with concrete values.
3048 SetContents(const DenseSet<BaseTy> &Assumptions)
3049 : Universal(false), Set(Assumptions) {}
3050
3051 SetContents(bool Universal, const DenseSet<BaseTy> &Assumptions)
3052 : Universal(Universal), Set(Assumptions) {}
3053
3054 const DenseSet<BaseTy> &getSet() const { return Set; }
3055
3056 bool isUniversal() const { return Universal; }
3057
3058 bool empty() const { return Set.empty() && !Universal; }
3059
3060 /// Finds A := A ^ B where A or B could be the "Universal" set which
3061 /// contains every possible attribute. Returns true if changes were made.
3063 bool IsUniversal = Universal;
3064 unsigned Size = Set.size();
3065
3066 // A := A ^ U = A
3067 if (RHS.isUniversal())
3068 return false;
3069
3070 // A := U ^ B = B
3071 if (Universal)
3072 Set = RHS.getSet();
3073 else
3074 set_intersect(Set, RHS.getSet());
3075
3076 Universal &= RHS.isUniversal();
3077 return IsUniversal != Universal || Size != Set.size();
3078 }
3079
3080 /// Finds A := A u B where A or B could be the "Universal" set which
3081 /// contains every possible attribute. returns true if changes were made.
3082 bool getUnion(const SetContents &RHS) {
3083 bool IsUniversal = Universal;
3084 unsigned Size = Set.size();
3085
3086 // A := A u U = U = U u B
3087 if (!RHS.isUniversal() && !Universal)
3088 set_union(Set, RHS.getSet());
3089
3090 Universal |= RHS.isUniversal();
3091 return IsUniversal != Universal || Size != Set.size();
3092 }
3093
3094 private:
3095 /// Indicates if this set is "universal", containing every possible element.
3096 bool Universal;
3097
3098 /// The set of currently active assumptions.
3099 DenseSet<BaseTy> Set;
3100 };
3101
3102 SetState() : Known(false), Assumed(true), IsAtFixedpoint(false) {}
3103
3104 /// Initializes the known state with an initial set and initializes the
3105 /// assumed state as universal.
3107 : Known(Known), Assumed(true), IsAtFixedpoint(false) {}
3108
3109 /// See AbstractState::isValidState()
3110 bool isValidState() const override { return !Assumed.empty(); }
3111
3112 /// See AbstractState::isAtFixpoint()
3113 bool isAtFixpoint() const override { return IsAtFixedpoint; }
3114
3115 /// See AbstractState::indicateOptimisticFixpoint(...)
3117 IsAtFixedpoint = true;
3118 Known = Assumed;
3120 }
3121
3122 /// See AbstractState::indicatePessimisticFixpoint(...)
3124 IsAtFixedpoint = true;
3125 Assumed = Known;
3126 return ChangeStatus::CHANGED;
3127 }
3128
3129 /// Return the known state encoding.
3130 const SetContents &getKnown() const { return Known; }
3131
3132 /// Return the assumed state encoding.
3133 const SetContents &getAssumed() const { return Assumed; }
3134
3135 /// Returns if the set state contains the element.
3136 bool setContains(const BaseTy &Elem) const {
3137 return Assumed.getSet().contains(Elem) || Known.getSet().contains(Elem);
3138 }
3139
3140 /// Performs the set intersection between this set and \p RHS. Returns true if
3141 /// changes were made.
3143 bool IsUniversal = Assumed.isUniversal();
3144 unsigned SizeBefore = Assumed.getSet().size();
3145
3146 // Get intersection and make sure that the known set is still a proper
3147 // subset of the assumed set. A := K u (A ^ R).
3148 Assumed.getIntersection(RHS);
3149 Assumed.getUnion(Known);
3150
3151 return SizeBefore != Assumed.getSet().size() ||
3152 IsUniversal != Assumed.isUniversal();
3153 }
3154
3155 /// Performs the set union between this set and \p RHS. Returns true if
3156 /// changes were made.
3157 bool getUnion(const SetContents &RHS) { return Assumed.getUnion(RHS); }
3158
3159private:
3160 /// The set of values known for this state.
3161 SetContents Known;
3162
3163 /// The set of assumed values for this state.
3164 SetContents Assumed;
3165
3166 bool IsAtFixedpoint;
3167};
3168
3169/// Helper to tie a abstract state implementation to an abstract attribute.
3170template <typename StateTy, typename BaseType, class... Ts>
3171struct StateWrapper : public BaseType, public StateTy {
3172 /// Provide static access to the type of the state.
3174
3175 StateWrapper(const IRPosition &IRP, Ts... Args)
3176 : BaseType(IRP), StateTy(Args...) {}
3177
3178 /// See AbstractAttribute::getState(...).
3179 StateType &getState() override { return *this; }
3180
3181 /// See AbstractAttribute::getState(...).
3182 const StateType &getState() const override { return *this; }
3183};
3184
3185/// Helper class that provides common functionality to manifest IR attributes.
3186template <Attribute::AttrKind AK, typename BaseType, typename AAType>
3187struct IRAttribute : public BaseType {
3188 IRAttribute(const IRPosition &IRP) : BaseType(IRP) {}
3189
3190 /// Most boolean IRAttribute AAs don't do anything non-trivial
3191 /// in their initializers while non-boolean ones often do. Subclasses can
3192 /// change this.
3194
3195 /// Compile time access to the IR attribute kind.
3197
3198 /// Return true if the IR attribute(s) associated with this AA are implied for
3199 /// an undef value.
3200 static bool isImpliedByUndef() { return true; }
3201
3202 /// Return true if the IR attribute(s) associated with this AA are implied for
3203 /// an poison value.
3204 static bool isImpliedByPoison() { return true; }
3205
3206 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3207 Attribute::AttrKind ImpliedAttributeKind = AK,
3208 bool IgnoreSubsumingPositions = false) {
3209 if (AAType::isImpliedByUndef() && isa<UndefValue>(IRP.getAssociatedValue()))
3210 return true;
3211 if (AAType::isImpliedByPoison() &&
3212 isa<PoisonValue>(IRP.getAssociatedValue()))
3213 return true;
3214 return A.hasAttr(IRP, {ImpliedAttributeKind}, IgnoreSubsumingPositions,
3215 ImpliedAttributeKind);
3216 }
3217
3218 /// See AbstractAttribute::manifest(...).
3220 if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
3222 SmallVector<Attribute, 4> DeducedAttrs;
3223 getDeducedAttributes(A, this->getAnchorValue().getContext(), DeducedAttrs);
3224 if (DeducedAttrs.empty())
3226 return A.manifestAttrs(this->getIRPosition(), DeducedAttrs);
3227 }
3228
3229 /// Return the kind that identifies the abstract attribute implementation.
3230 Attribute::AttrKind getAttrKind() const { return AK; }
3231
3232 /// Return the deduced attributes in \p Attrs.
3234 SmallVectorImpl<Attribute> &Attrs) const {
3235 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
3236 }
3237};
3238
3239/// Base struct for all "concrete attribute" deductions.
3240///
3241/// The abstract attribute is a minimal interface that allows the Attributor to
3242/// orchestrate the abstract/fixpoint analysis. The design allows to hide away
3243/// implementation choices made for the subclasses but also to structure their
3244/// implementation and simplify the use of other abstract attributes in-flight.
3245///
3246/// To allow easy creation of new attributes, most methods have default
3247/// implementations. The ones that do not are generally straight forward, except
3248/// `AbstractAttribute::updateImpl` which is the location of most reasoning
3249/// associated with the abstract attribute. The update is invoked by the
3250/// Attributor in case the situation used to justify the current optimistic
3251/// state might have changed. The Attributor determines this automatically
3252/// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
3253///
3254/// The `updateImpl` method should inspect the IR and other abstract attributes
3255/// in-flight to justify the best possible (=optimistic) state. The actual
3256/// implementation is, similar to the underlying abstract state encoding, not
3257/// exposed. In the most common case, the `updateImpl` will go through a list of
3258/// reasons why its optimistic state is valid given the current information. If
3259/// any combination of them holds and is sufficient to justify the current
3260/// optimistic state, the method shall return UNCHAGED. If not, the optimistic
3261/// state is adjusted to the situation and the method shall return CHANGED.
3262///
3263/// If the manifestation of the "concrete attribute" deduced by the subclass
3264/// differs from the "default" behavior, which is a (set of) LLVM-IR
3265/// attribute(s) for an argument, call site argument, function return value, or
3266/// function, the `AbstractAttribute::manifest` method should be overloaded.
3267///
3268/// NOTE: If the state obtained via getState() is INVALID, thus if
3269/// AbstractAttribute::getState().isValidState() returns false, no
3270/// information provided by the methods of this class should be used.
3271/// NOTE: The Attributor currently has certain limitations to what we can do.
3272/// As a general rule of thumb, "concrete" abstract attributes should *for
3273/// now* only perform "backward" information propagation. That means
3274/// optimistic information obtained through abstract attributes should
3275/// only be used at positions that precede the origin of the information
3276/// with regards to the program flow. More practically, information can
3277/// *now* be propagated from instructions to their enclosing function, but
3278/// *not* from call sites to the called function. The mechanisms to allow
3279/// both directions will be added in the future.
3280/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
3281/// described in the file comment.
3284
3286
3287 /// Virtual destructor.
3288 virtual ~AbstractAttribute() = default;
3289
3290 /// Compile time access to the IR attribute kind.
3292
3293 /// This function is used to identify if an \p DGN is of type
3294 /// AbstractAttribute so that the dyn_cast and cast can use such information
3295 /// to cast an AADepGraphNode to an AbstractAttribute.
3296 ///
3297 /// We eagerly return true here because all AADepGraphNodes except for the
3298 /// Synthethis Node are of type AbstractAttribute
3299 static bool classof(const AADepGraphNode *DGN) { return true; }
3300
3301 /// Return false if this AA does anything non-trivial (hence not done by
3302 /// default) in its initializer.
3303 static bool hasTrivialInitializer() { return false; }
3304
3305 /// Return true if this AA requires a "callee" (or an associted function) for
3306 /// a call site positon. Default is optimistic to minimize AAs.
3307 static bool requiresCalleeForCallBase() { return false; }
3308
3309 /// Return true if this AA requires non-asm "callee" for a call site positon.
3310 static bool requiresNonAsmForCallBase() { return true; }
3311
3312 /// Return true if this AA requires all callees for an argument or function
3313 /// positon.
3314 static bool requiresCallersForArgOrFunction() { return false; }
3315
3316 /// Return false if an AA should not be created for \p IRP.
3318 return true;
3319 }
3320
3321 /// Return false if an AA should not be updated for \p IRP.
3323 Function *AssociatedFn = IRP.getAssociatedFunction();
3324 bool IsFnInterface = IRP.isFnInterfaceKind();
3325 assert((!IsFnInterface || AssociatedFn) &&
3326 "Function interface without a function?");
3327
3328 // TODO: Not all attributes require an exact definition. Find a way to
3329 // enable deduction for some but not all attributes in case the
3330 // definition might be changed at runtime, see also
3331 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
3332 // TODO: We could always determine abstract attributes and if sufficient
3333 // information was found we could duplicate the functions that do not
3334 // have an exact definition.
3335 return !IsFnInterface || A.isFunctionIPOAmendable(*AssociatedFn);
3336 }
3337
3338 /// Initialize the state with the information in the Attributor \p A.
3339 ///
3340 /// This function is called by the Attributor once all abstract attributes
3341 /// have been identified. It can and shall be used for task like:
3342 /// - identify existing knowledge in the IR and use it for the "known state"
3343 /// - perform any work that is not going to change over time, e.g., determine
3344 /// a subset of the IR, or attributes in-flight, that have to be looked at
3345 /// in the `updateImpl` method.
3346 virtual void initialize(Attributor &A) {}
3347
3348 /// A query AA is always scheduled as long as we do updates because it does
3349 /// lazy computation that cannot be determined to be done from the outside.
3350 /// However, while query AAs will not be fixed if they do not have outstanding
3351 /// dependences, we will only schedule them like other AAs. If a query AA that
3352 /// received a new query it needs to request an update via
3353 /// `Attributor::requestUpdateForAA`.
3354 virtual bool isQueryAA() const { return false; }
3355
3356 /// Return the internal abstract state for inspection.
3357 virtual StateType &getState() = 0;
3358 virtual const StateType &getState() const = 0;
3359
3360 /// Return an IR position, see struct IRPosition.
3361 const IRPosition &getIRPosition() const { return *this; };
3362 IRPosition &getIRPosition() { return *this; };
3363
3364 /// Helper functions, for debug purposes only.
3365 ///{
3366 void print(raw_ostream &OS) const { print(nullptr, OS); }
3367 void print(Attributor *, raw_ostream &OS) const override;
3368 virtual void printWithDeps(raw_ostream &OS) const;
3369 void dump() const { this->print(dbgs()); }
3370
3371 /// This function should return the "summarized" assumed state as string.
3372 virtual const std::string getAsStr(Attributor *A) const = 0;
3373
3374 /// This function should return the name of the AbstractAttribute
3375 virtual const std::string getName() const = 0;
3376
3377 /// This function should return the address of the ID of the AbstractAttribute
3378 virtual const char *getIdAddr() const = 0;
3379 ///}
3380
3381 /// Allow the Attributor access to the protected methods.
3382 friend struct Attributor;
3383
3384protected:
3385 /// Hook for the Attributor to trigger an update of the internal state.
3386 ///
3387 /// If this attribute is already fixed, this method will return UNCHANGED,
3388 /// otherwise it delegates to `AbstractAttribute::updateImpl`.
3389 ///
3390 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3392
3393 /// Hook for the Attributor to trigger the manifestation of the information
3394 /// represented by the abstract attribute in the LLVM-IR.
3395 ///
3396 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
3399 }
3400
3401 /// Hook to enable custom statistic tracking, called after manifest that
3402 /// resulted in a change if statistics are enabled.
3403 ///
3404 /// We require subclasses to provide an implementation so we remember to
3405 /// add statistics for them.
3406 virtual void trackStatistics() const = 0;
3407
3408 /// The actual update/transfer function which has to be implemented by the
3409 /// derived classes.
3410 ///
3411 /// If it is called, the environment has changed and we have to determine if
3412 /// the current information is still valid or adjust it otherwise.
3413 ///
3414 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3416};
3417
3418/// Forward declarations of output streams for debug purposes.
3419///
3420///{
3426template <typename base_ty, base_ty BestState, base_ty WorstState>
3430 return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
3431 << static_cast<const AbstractState &>(S);
3432}
3433raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
3434///}
3435
3436struct AttributorPass : public PassInfoMixin<AttributorPass> {
3438};
3439struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> {
3442};
3443
3444/// A more lightweight version of the Attributor which only runs attribute
3445/// inference but no simplifications.
3446struct AttributorLightPass : public PassInfoMixin<AttributorLightPass> {
3448};
3449
3450/// A more lightweight version of the Attributor which only runs attribute
3451/// inference but no simplifications.
3453 : public PassInfoMixin<AttributorLightCGSCCPass> {
3456};
3457
3458/// Helper function to clamp a state \p S of type \p StateType with the
3459/// information in \p R and indicate/return if \p S did change (as-in update is
3460/// required to be run again).
3461template <typename StateType>
3462ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) {
3463 auto Assumed = S.getAssumed();
3464 S ^= R;
3465 return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
3467}
3468
3469/// ----------------------------------------------------------------------------
3470/// Abstract Attribute Classes
3471/// ----------------------------------------------------------------------------
3472
3474 : public IRAttribute<Attribute::NoUnwind,
3475 StateWrapper<BooleanState, AbstractAttribute>,
3476 AANoUnwind> {
3478
3479 /// Returns true if nounwind is assumed.
3480 bool isAssumedNoUnwind() const { return getAssumed(); }
3481
3482 /// Returns true if nounwind is known.
3483 bool isKnownNoUnwind() const { return getKnown(); }
3484
3485 /// Create an abstract attribute view for the position \p IRP.
3487
3488 /// See AbstractAttribute::getName()
3489 const std::string getName() const override { return "AANoUnwind"; }
3490
3491 /// See AbstractAttribute::getIdAddr()
3492 const char *getIdAddr() const override { return &ID; }
3493
3494 /// This function should return true if the type of the \p AA is AANoUnwind
3495 static bool classof(const AbstractAttribute *AA) {
3496 return (AA->getIdAddr() == &ID);
3497 }
3498
3499 /// Unique ID (due to the unique address)
3500 static const char ID;
3501};
3502
3504 : public IRAttribute<Attribute::NoSync,
3505 StateWrapper<BooleanState, AbstractAttribute>,
3506 AANoSync> {
3508
3509 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3510 Attribute::AttrKind ImpliedAttributeKind,
3511 bool IgnoreSubsumingPositions = false) {
3512 // Note: This is also run for non-IPO amendable functions.
3513 assert(ImpliedAttributeKind == Attribute::NoSync);
3514 if (A.hasAttr(IRP, {Attribute::NoSync}, IgnoreSubsumingPositions,
3515 Attribute::NoSync))
3516 return true;
3517
3518 // Check for readonly + non-convergent.
3519 // TODO: We should be able to use hasAttr for Attributes, not only
3520 // AttrKinds.
3522 if (!F || F->isConvergent())
3523 return false;
3524
3526 A.getAttrs(IRP, {Attribute::Memory}, Attrs, IgnoreSubsumingPositions);
3527
3529 for (const Attribute &Attr : Attrs)
3530 ME &= Attr.getMemoryEffects();
3531
3532 if (!ME.onlyReadsMemory())
3533 return false;
3534
3535 A.manifestAttrs(IRP, Attribute::get(F->getContext(), Attribute::NoSync));
3536 return true;
3537 }
3538
3539 /// See AbstractAttribute::isValidIRPositionForInit
3541 if (!IRP.isFunctionScope() &&
3543 return false;
3544 return IRAttribute::isValidIRPositionForInit(A, IRP);
3545 }
3546
3547 /// Returns true if "nosync" is assumed.
3548 bool isAssumedNoSync() const { return getAssumed(); }
3549
3550 /// Returns true if "nosync" is known.
3551 bool isKnownNoSync() const { return getKnown(); }
3552
3553 /// Helper function used to determine whether an instruction is non-relaxed
3554 /// atomic. In other words, if an atomic instruction does not have unordered
3555 /// or monotonic ordering
3556 static bool isNonRelaxedAtomic(const Instruction *I);
3557
3558 /// Helper function specific for intrinsics which are potentially volatile.
3559 static bool isNoSyncIntrinsic(const Instruction *I);
3560
3561 /// Helper function to determine if \p CB is an aligned (GPU) barrier. Aligned
3562 /// barriers have to be executed by all threads. The flag \p ExecutedAligned
3563 /// indicates if the call is executed by all threads in a (thread) block in an
3564 /// aligned way. If that is the case, non-aligned barriers are effectively
3565 /// aligned barriers.
3566 static bool isAlignedBarrier(const CallBase &CB, bool ExecutedAligned);
3567
3568 /// Create an abstract attribute view for the position \p IRP.
3570
3571 /// See AbstractAttribute::getName()
3572 const std::string getName() const override { return "AANoSync"; }
3573
3574 /// See AbstractAttribute::getIdAddr()
3575 const char *getIdAddr() const override { return &ID; }
3576
3577 /// This function should return true if the type of the \p AA is AANoSync
3578 static bool classof(const AbstractAttribute *AA) {
3579 return (AA->getIdAddr() == &ID);
3580 }
3581
3582 /// Unique ID (due to the unique address)
3583 static const char ID;
3584};
3585
3586/// An abstract interface for all nonnull attributes.
3588 : public IRAttribute<Attribute::MustProgress,
3589 StateWrapper<BooleanState, AbstractAttribute>,
3590 AAMustProgress> {
3592
3593 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3594 Attribute::AttrKind ImpliedAttributeKind,
3595 bool IgnoreSubsumingPositions = false) {
3596 // Note: This is also run for non-IPO amendable functions.
3597 assert(ImpliedAttributeKind == Attribute::MustProgress);
3598 return A.hasAttr(IRP, {Attribute::MustProgress, Attribute::WillReturn},
3599 IgnoreSubsumingPositions, Attribute::MustProgress);
3600 }
3601
3602 /// Return true if we assume that the underlying value is nonnull.
3603 bool isAssumedMustProgress() const { return getAssumed(); }
3604
3605 /// Return true if we know that underlying value is nonnull.
3606 bool isKnownMustProgress() const { return getKnown(); }
3607
3608 /// Create an abstract attribute view for the position \p IRP.
3610 Attributor &A);
3611
3612 /// See AbstractAttribute::getName()
3613 const std::string getName() const override { return "AAMustProgress"; }
3614
3615 /// See AbstractAttribute::getIdAddr()
3616 const char *getIdAddr() const override { return &ID; }
3617
3618 /// This function should return true if the type of the \p AA is
3619 /// AAMustProgress
3620 static bool classof(const AbstractAttribute *AA) {
3621 return (AA->getIdAddr() == &ID);
3622 }
3623
3624 /// Unique ID (due to the unique address)
3625 static const char ID;
3626};
3627
3628/// An abstract interface for all nonnull attributes.
3630 : public IRAttribute<Attribute::NonNull,
3631 StateWrapper<BooleanState, AbstractAttribute>,
3632 AANonNull> {
3634
3635 /// See AbstractAttribute::hasTrivialInitializer.
3636 static bool hasTrivialInitializer() { return false; }
3637
3638 /// See IRAttribute::isImpliedByUndef.
3639 /// Undef is not necessarily nonnull as nonnull + noundef would cause poison.
3640 /// Poison implies nonnull though.
3641 static bool isImpliedByUndef() { return false; }
3642
3643 /// See AbstractAttribute::isValidIRPositionForInit
3646 return false;
3647 return IRAttribute::isValidIRPositionForInit(A, IRP);
3648 }
3649
3650 /// See AbstractAttribute::isImpliedByIR(...).
3651 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3652 Attribute::AttrKind ImpliedAttributeKind,
3653 bool IgnoreSubsumingPositions = false);
3654
3655 /// Return true if we assume that the underlying value is nonnull.
3656 bool isAssumedNonNull() const { return getAssumed(); }
3657
3658 /// Return true if we know that underlying value is nonnull.
3659 bool isKnownNonNull() const { return getKnown(); }
3660
3661 /// Create an abstract attribute view for the position \p IRP.
3663
3664 /// See AbstractAttribute::getName()
3665 const std::string getName() const override { return "AANonNull"; }
3666
3667 /// See AbstractAttribute::getIdAddr()
3668 const char *getIdAddr() const override { return &ID; }
3669
3670 /// This function should return true if the type of the \p AA is AANonNull
3671 static bool classof(const AbstractAttribute *AA) {
3672 return (AA->getIdAddr() == &ID);
3673 }
3674
3675 /// Unique ID (due to the unique address)
3676 static const char ID;
3677};
3678
3679/// An abstract attribute for norecurse.
3681 : public IRAttribute<Attribute::NoRecurse,
3682 StateWrapper<BooleanState, AbstractAttribute>,
3683 AANoRecurse> {
3685
3686 /// Return true if "norecurse" is assumed.
3687 bool isAssumedNoRecurse() const { return getAssumed(); }
3688
3689 /// Return true if "norecurse" is known.
3690 bool isKnownNoRecurse() const { return getKnown(); }
3691
3692 /// Create an abstract attribute view for the position \p IRP.
3694
3695 /// See AbstractAttribute::getName()
3696 const std::string getName() const override { return "AANoRecurse"; }
3697
3698 /// See AbstractAttribute::getIdAddr()
3699 const char *getIdAddr() const override { return &ID; }
3700
3701 /// This function should return true if the type of the \p AA is AANoRecurse
3702 static bool classof(const AbstractAttribute *AA) {
3703 return (AA->getIdAddr() == &ID);
3704 }
3705
3706 /// Unique ID (due to the unique address)
3707 static const char ID;
3708};
3709
3710/// An abstract attribute for willreturn.
3712 : public IRAttribute<Attribute::WillReturn,
3713 StateWrapper<BooleanState, AbstractAttribute>,
3714 AAWillReturn> {
3716
3717 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3718 Attribute::AttrKind ImpliedAttributeKind,
3719 bool IgnoreSubsumingPositions = false) {
3720 // Note: This is also run for non-IPO amendable functions.
3721 assert(ImpliedAttributeKind == Attribute::WillReturn);
3722 if (IRAttribute::isImpliedByIR(A, IRP, ImpliedAttributeKind,
3723 IgnoreSubsumingPositions))
3724 return true;
3726 return false;
3727 A.manifestAttrs(IRP, Attribute::get(IRP.getAnchorValue().getContext(),
3728 Attribute::WillReturn));
3729 return true;
3730 }
3731
3732 /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
3734 const IRPosition &IRP) {
3735 // Check for `mustprogress` in the scope and the associated function which
3736 // might be different if this is a call site.
3737 if (!A.hasAttr(IRP, {Attribute::MustProgress}))
3738 return false;
3739
3741 A.getAttrs(IRP, {Attribute::Memory}, Attrs,
3742 /* IgnoreSubsumingPositions */ false);
3743
3745 for (const Attribute &Attr : Attrs)
3746 ME &= Attr.getMemoryEffects();
3747 return ME.onlyReadsMemory();
3748 }
3749
3750 /// Return true if "willreturn" is assumed.
3751 bool isAssumedWillReturn() const { return getAssumed(); }
3752
3753 /// Return true if "willreturn" is known.
3754 bool isKnownWillReturn() const { return getKnown(); }
3755
3756 /// Create an abstract attribute view for the position \p IRP.
3758
3759 /// See AbstractAttribute::getName()
3760 const std::string getName() const override { return "AAWillReturn"; }
3761
3762 /// See AbstractAttribute::getIdAddr()
3763 const char *getIdAddr() const override { return &ID; }
3764
3765 /// This function should return true if the type of the \p AA is AAWillReturn
3766 static bool classof(const AbstractAttribute *AA) {
3767 return (AA->getIdAddr() == &ID);
3768 }
3769
3770 /// Unique ID (due to the unique address)
3771 static const char ID;
3772};
3773
3774/// An abstract attribute for undefined behavior.
3776 : public StateWrapper<BooleanState, AbstractAttribute> {
3779
3780 /// Return true if "undefined behavior" is assumed.
3781 bool isAssumedToCauseUB() const { return getAssumed(); }
3782
3783 /// Return true if "undefined behavior" is assumed for a specific instruction.
3784 virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
3785
3786 /// Return true if "undefined behavior" is known.
3787 bool isKnownToCauseUB() const { return getKnown(); }
3788
3789 /// Return true if "undefined behavior" is known for a specific instruction.
3790 virtual bool isKnownToCauseUB(Instruction *I) const = 0;
3791
3792 /// Create an abstract attribute view for the position \p IRP.
3794 Attributor &A);
3795
3796 /// See AbstractAttribute::getName()
3797 const std::string getName() const override { return "AAUndefinedBehavior"; }
3798
3799 /// See AbstractAttribute::getIdAddr()
3800 const char *getIdAddr() const override { return &ID; }
3801
3802 /// This function should return true if the type of the \p AA is
3803 /// AAUndefineBehavior
3804 static bool classof(const AbstractAttribute *AA) {
3805 return (AA->getIdAddr() == &ID);
3806 }
3807
3808 /// Unique ID (due to the unique address)
3809 static const char ID;
3810};
3811
3812/// An abstract interface to determine reachability of point A to B.
3814 : public StateWrapper<BooleanState, AbstractAttribute> {
3817
3818 /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
3819 /// Users should provide two positions they are interested in, and the class
3820 /// determines (and caches) reachability.
3822 Attributor &A, const Instruction &From, const Instruction &To,
3823 const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0;
3824
3825 /// Create an abstract attribute view for the position \p IRP.
3827 Attributor &A);
3828
3829 /// See AbstractAttribute::getName()
3830 const std::string getName() const override { return "AAIntraFnReachability"; }
3831
3832 /// See AbstractAttribute::getIdAddr()
3833 const char *getIdAddr() const override { return &ID; }
3834
3835 /// This function should return true if the type of the \p AA is
3836 /// AAIntraFnReachability
3837 static bool classof(const AbstractAttribute *AA) {
3838 return (AA->getIdAddr() == &ID);
3839 }
3840
3841 /// Unique ID (due to the unique address)
3842 static const char ID;
3843};
3844
3845/// An abstract interface for all noalias attributes.
3847 : public IRAttribute<Attribute::NoAlias,
3848 StateWrapper<BooleanState, AbstractAttribute>,
3849 AANoAlias> {
3851
3852 /// See AbstractAttribute::isValidIRPositionForInit
3855 return false;
3856 return IRAttribute::isValidIRPositionForInit(A, IRP);
3857 }
3858
3859 /// See IRAttribute::isImpliedByIR
3860 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3861 Attribute::AttrKind ImpliedAttributeKind,
3862 bool IgnoreSubsumingPositions = false);
3863
3864 /// See AbstractAttribute::requiresCallersForArgOrFunction
3865 static bool requiresCallersForArgOrFunction() { return true; }
3866
3867 /// Return true if we assume that the underlying value is alias.
3868 bool isAssumedNoAlias() const { return getAssumed(); }
3869
3870 /// Return true if we know that underlying value is noalias.
3871 bool isKnownNoAlias() const { return getKnown(); }
3872
3873 /// Create an abstract attribute view for the position \p IRP.
3875
3876 /// See AbstractAttribute::getName()
3877 const std::string getName() const override { return "AANoAlias"; }
3878
3879 /// See AbstractAttribute::getIdAddr()
3880 const char *getIdAddr() const override { return &ID; }
3881
3882 /// This function should return true if the type of the \p AA is AANoAlias
3883 static bool classof(const AbstractAttribute *AA) {
3884 return (AA->getIdAddr() == &ID);
3885 }
3886
3887 /// Unique ID (due to the unique address)
3888 static const char ID;
3889};
3890
3891/// An AbstractAttribute for nofree.
3893 : public IRAttribute<Attribute::NoFree,
3894 StateWrapper<BooleanState, AbstractAttribute>,
3895 AANoFree> {
3897
3898 /// See IRAttribute::isImpliedByIR
3899 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3900 Attribute::AttrKind ImpliedAttributeKind,
3901 bool IgnoreSubsumingPositions = false) {
3902 // Note: This is also run for non-IPO amendable functions.
3903 assert(ImpliedAttributeKind == Attribute::NoFree);
3904 return A.hasAttr(
3905 IRP, {Attribute::ReadNone, Attribute::ReadOnly, Attribute::NoFree},
3906 IgnoreSubsumingPositions, Attribute::NoFree);
3907 }
3908
3909 /// See AbstractAttribute::isValidIRPositionForInit
3911 if (!IRP.isFunctionScope() &&
3913 return false;
3914 return IRAttribute::isValidIRPositionForInit(A, IRP);
3915 }
3916
3917 /// Return true if "nofree" is assumed.
3918 bool isAssumedNoFree() const { return getAssumed(); }
3919
3920 /// Return true if "nofree" is known.
3921 bool isKnownNoFree() const { return getKnown(); }
3922
3923 /// Create an abstract attribute view for the position \p IRP.
3925
3926 /// See AbstractAttribute::getName()
3927 const std::string getName() const override { return "AANoFree"; }
3928
3929 /// See AbstractAttribute::getIdAddr()
3930 const char *getIdAddr() const override { return &ID; }
3931
3932 /// This function should return true if the type of the \p AA is AANoFree
3933 static bool classof(const AbstractAttribute *AA) {
3934 return (AA->getIdAddr() == &ID);
3935 }
3936
3937 /// Unique ID (due to the unique address)
3938 static const char ID;
3939};
3940
3941/// An AbstractAttribute for noreturn.
3943 : public IRAttribute<Attribute::NoReturn,
3944 StateWrapper<BooleanState, AbstractAttribute>,
3945 AANoReturn> {
3947
3948 /// Return true if the underlying object is assumed to never return.
3949 bool isAssumedNoReturn() const { return getAssumed(); }
3950
3951 /// Return true if the underlying object is known to never return.
3952 bool isKnownNoReturn() const { return getKnown(); }
3953
3954 /// Create an abstract attribute view for the position \p IRP.
3956
3957 /// See AbstractAttribute::getName()
3958 const std::string getName() const override { return "AANoReturn"; }
3959
3960 /// See AbstractAttribute::getIdAddr()
3961 const char *getIdAddr() const override { return &ID; }
3962
3963 /// This function should return true if the type of the \p AA is AANoReturn
3964 static bool classof(const AbstractAttribute *AA) {
3965 return (AA->getIdAddr() == &ID);
3966 }
3967
3968 /// Unique ID (due to the unique address)
3969 static const char ID;
3970};
3971
3972/// An abstract interface for liveness abstract attribute.
3974 : public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> {
3976 AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3977
3978 /// See AbstractAttribute::isValidIRPositionForInit
3981 return isa<Function>(IRP.getAnchorValue()) &&
3982 !cast<Function>(IRP.getAnchorValue()).isDeclaration();
3983 return true;
3984 }
3985
3986 /// State encoding bits. A set bit in the state means the property holds.
3987 enum {
3990
3992 };
3993 static_assert(IS_DEAD == getBestState(), "Unexpected BEST_STATE value");
3994
3995protected:
3996 /// The query functions are protected such that other attributes need to go
3997 /// through the Attributor interfaces: `Attributor::isAssumedDead(...)`
3998
3999 /// Returns true if the underlying value is assumed dead.
4000 virtual bool isAssumedDead() const = 0;
4001
4002 /// Returns true if the underlying value is known dead.
4003 virtual bool isKnownDead() const = 0;
4004
4005 /// Returns true if \p BB is known dead.
4006 virtual bool isKnownDead(const BasicBlock *BB) const = 0;
4007
4008 /// Returns true if \p I is assumed dead.
4009 virtual bool isAssumedDead(const Instruction *I) const = 0;
4010
4011 /// Returns true if \p I is known dead.
4012 virtual bool isKnownDead(const Instruction *I) const = 0;
4013
4014 /// Return true if the underlying value is a store that is known to be
4015 /// removable. This is different from dead stores as the removable store
4016 /// can have an effect on live values, especially loads, but that effect
4017 /// is propagated which allows us to remove the store in turn.
4018 virtual bool isRemovableStore() const { return false; }
4019
4020 /// This method is used to check if at least one instruction in a collection
4021 /// of instructions is live.
4022 template <typename T> bool isLiveInstSet(T begin, T end) const {
4023 for (const auto &I : llvm::make_range(begin, end)) {
4024 assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
4025 "Instruction must be in the same anchor scope function.");
4026
4027 if (!isAssumedDead(I))
4028 return true;
4029 }
4030
4031 return false;
4032 }
4033
4034public:
4035 /// Create an abstract attribute view for the position \p IRP.
4037
4038 /// Determine if \p F might catch asynchronous exceptions.
4040 return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
4041 }
4042
4043 /// Returns true if \p BB is assumed dead.
4044 virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
4045
4046 /// Return if the edge from \p From BB to \p To BB is assumed dead.
4047 /// This is specifically useful in AAReachability.
4048 virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const {
4049 return false;
4050 }
4051
4052 /// See AbstractAttribute::getName()
4053 const std::string getName() const override { return "AAIsDead"; }
4054
4055 /// See AbstractAttribute::getIdAddr()
4056 const char *getIdAddr() const override { return &ID; }
4057
4058 /// This function should return true if the type of the \p AA is AAIsDead
4059 static bool classof(const AbstractAttribute *AA) {
4060 return (AA->getIdAddr() == &ID);
4061 }
4062
4063 /// Unique ID (due to the unique address)
4064 static const char ID;
4065
4066 friend struct Attributor;
4067};
4068
4069/// State for dereferenceable attribute
4071
4072 static DerefState getBestState() { return DerefState(); }
4073 static DerefState getBestState(const DerefState &) { return getBestState(); }
4074
4075 /// Return the worst possible representable state.
4077 DerefState DS;
4078 DS.indicatePessimisticFixpoint();
4079 return DS;
4080 }
4082 return getWorstState();
4083 }
4084
4085 /// State representing for dereferenceable bytes.
4087
4088 /// Map representing for accessed memory offsets and sizes.
4089 /// A key is Offset and a value is size.
4090 /// If there is a load/store instruction something like,
4091 /// p[offset] = v;
4092 /// (offset, sizeof(v)) will be inserted to this map.
4093 /// std::map is used because we want to iterate keys in ascending order.
4094 std::map<int64_t, uint64_t> AccessedBytesMap;
4095
4096 /// Helper function to calculate dereferenceable bytes from current known
4097 /// bytes and accessed bytes.
4098 ///
4099 /// int f(int *A){
4100 /// *A = 0;
4101 /// *(A+2) = 2;
4102 /// *(A+1) = 1;
4103 /// *(A+10) = 10;
4104 /// }
4105 /// ```
4106 /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
4107 /// AccessedBytesMap is std::map so it is iterated in accending order on
4108 /// key(Offset). So KnownBytes will be updated like this:
4109 ///
4110 /// |Access | KnownBytes
4111 /// |(0, 4)| 0 -> 4
4112 /// |(4, 4)| 4 -> 8
4113 /// |(8, 4)| 8 -> 12
4114 /// |(40, 4) | 12 (break)
4115 void computeKnownDerefBytesFromAccessedMap() {
4116 int64_t KnownBytes = DerefBytesState.getKnown();
4117 for (auto &Access : AccessedBytesMap) {
4118 if (KnownBytes < Access.first)
4119 break;
4120 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
4121 }
4122
4124 }
4125
4126 /// State representing that whether the value is globaly dereferenceable.
4127 BooleanState GlobalState;
4128
4129 /// See AbstractState::isValidState()
4130 bool isValidState() const override { return DerefBytesState.isValidState(); }
4131
4132 /// See AbstractState::isAtFixpoint()
4133 bool isAtFixpoint() const override {
4134 return !isValidState() ||
4135 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
4136 }
4137
4138 /// See AbstractState::indicateOptimisticFixpoint(...)
4141 GlobalState.indicateOptimisticFixpoint();
4143 }
4144
4145 /// See AbstractState::indicatePessimisticFixpoint(...)
4148 GlobalState.indicatePessimisticFixpoint();
4149 return ChangeStatus::CHANGED;
4150 }
4151
4152 /// Update known dereferenceable bytes.
4153 void takeKnownDerefBytesMaximum(uint64_t Bytes) {
4155
4156 // Known bytes might increase.
4157 computeKnownDerefBytesFromAccessedMap();
4158 }
4159
4160 /// Update assumed dereferenceable bytes.
4161 void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
4163 }
4164
4165 /// Add accessed bytes to the map.
4166 void addAccessedBytes(int64_t Offset, uint64_t Size) {
4167 uint64_t &AccessedBytes = AccessedBytesMap[Offset];
4168 AccessedBytes = std::max(AccessedBytes, Size);
4169
4170 // Known bytes might increase.
4171 computeKnownDerefBytesFromAccessedMap();
4172 }
4173
4174 /// Equality for DerefState.
4175 bool operator==(const DerefState &R) const {
4176 return this->DerefBytesState == R.DerefBytesState &&
4177 this->GlobalState == R.GlobalState;
4178 }
4179
4180 /// Inequality for DerefState.
4181 bool operator!=(const DerefState &R) const { return !(*this == R); }
4182
4183 /// See IntegerStateBase::operator^=
4184 DerefState operator^=(const DerefState &R) {
4185 DerefBytesState ^= R.DerefBytesState;
4186 GlobalState ^= R.GlobalState;
4187 return *this;
4188 }
4189
4190 /// See IntegerStateBase::operator+=
4191 DerefState operator+=(const DerefState &R) {
4192 DerefBytesState += R.DerefBytesState;
4193 GlobalState += R.GlobalState;
4194 return *this;
4195 }
4196
4197 /// See IntegerStateBase::operator&=
4198 DerefState operator&=(const DerefState &R) {
4199 DerefBytesState &= R.DerefBytesState;
4200 GlobalState &= R.GlobalState;
4201 return *this;
4202 }
4203
4204 /// See IntegerStateBase::operator|=
4205 DerefState operator|=(const DerefState &R) {
4206 DerefBytesState |= R.DerefBytesState;
4207 GlobalState |= R.GlobalState;
4208 return *this;
4209 }
4210};
4211
4212/// An abstract interface for all dereferenceable attribute.
4214 : public IRAttribute<Attribute::Dereferenceable,
4215 StateWrapper<DerefState, AbstractAttribute>,
4216 AADereferenceable> {
4218
4219 /// See AbstractAttribute::isValidIRPositionForInit
4222 return false;
4223 return IRAttribute::isValidIRPositionForInit(A, IRP);
4224 }
4225
4226 /// Return true if we assume that underlying value is
4227 /// dereferenceable(_or_null) globally.
4228 bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
4229
4230 /// Return true if we know that underlying value is
4231 /// dereferenceable(_or_null) globally.
4232 bool isKnownGlobal() const { return GlobalState.getKnown(); }
4233
4234 /// Return assumed dereferenceable bytes.
4236 return DerefBytesState.getAssumed();
4237 }
4238
4239 /// Return known dereferenceable bytes.
4241 return DerefBytesState.getKnown();
4242 }
4243
4244 /// Create an abstract attribute view for the position \p IRP.
4246 Attributor &A);
4247
4248 /// See AbstractAttribute::getName()
4249 const std::string getName() const override { return "AADereferenceable"; }
4250
4251 /// See AbstractAttribute::getIdAddr()
4252 const char *getIdAddr() const override { return &ID; }
4253
4254 /// This function should return true if the type of the \p AA is
4255 /// AADereferenceable
4256 static bool classof(const AbstractAttribute *AA) {
4257 return (AA->getIdAddr() == &ID);
4258 }
4259
4260 /// Unique ID (due to the unique address)
4261 static const char ID;
4262};
4263
4266/// An abstract interface for all align attributes.
4268 : public IRAttribute<Attribute::Alignment,
4269 StateWrapper<AAAlignmentStateType, AbstractAttribute>,
4270 AAAlign> {
4272
4273 /// See AbstractAttribute::isValidIRPositionForInit
4276 return false;
4277 return IRAttribute::isValidIRPositionForInit(A, IRP);
4278 }
4279
4280 /// Return assumed alignment.
4281 Align getAssumedAlign() const { return Align(getAssumed()); }
4282
4283 /// Return known alignment.
4284 Align getKnownAlign() const { return Align(getKnown()); }
4285
4286 /// See AbstractAttribute::getName()
4287 const std::string getName() const override { return "AAAlign"; }
4288
4289 /// See AbstractAttribute::getIdAddr()
4290 const char *getIdAddr() const override { return &ID; }
4291
4292 /// This function should return true if the type of the \p AA is AAAlign
4293 static bool classof(const AbstractAttribute *AA) {
4294 return (AA->getIdAddr() == &ID);
4295 }
4296
4297 /// Create an abstract attribute view for the position \p IRP.
4299
4300 /// Unique ID (due to the unique address)
4301 static const char ID;
4302};
4303
4304/// An abstract interface to track if a value leaves it's defining function
4305/// instance.
4306/// TODO: We should make it a ternary AA tracking uniqueness, and uniqueness
4307/// wrt. the Attributor analysis separately.
4308struct AAInstanceInfo : public StateWrapper<BooleanState, AbstractAttribute> {
4311
4312 /// Return true if we know that the underlying value is unique in its scope
4313 /// wrt. the Attributor analysis. That means it might not be unique but we can
4314 /// still use pointer equality without risking to represent two instances with
4315 /// one `llvm::Value`.
4316 bool isKnownUniqueForAnalysis() const { return isKnown(); }
4317
4318 /// Return true if we assume that the underlying value is unique in its scope
4319 /// wrt. the Attributor analysis. That means it might not be unique but we can
4320 /// still use pointer equality without risking to represent two instances with
4321 /// one `llvm::Value`.
4322 bool isAssumedUniqueForAnalysis() const { return isAssumed(); }
4323
4324 /// Create an abstract attribute view for the position \p IRP.
4326 Attributor &A);
4327
4328 /// See AbstractAttribute::getName()
4329 const std::string getName() const override { return "AAInstanceInfo"; }
4330
4331 /// See AbstractAttribute::getIdAddr()
4332 const char *getIdAddr() const override { return &ID; }
4333
4334 /// This function should return true if the type of the \p AA is
4335 /// AAInstanceInfo
4336 static bool classof(const AbstractAttribute *AA) {
4337 return (AA->getIdAddr() == &ID);
4338 }
4339
4340 /// Unique ID (due to the unique address)
4341 static const char ID;
4342};
4343
4344/// An abstract interface for all nocapture attributes.
4346 : public IRAttribute<
4347 Attribute::NoCapture,
4348 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>,
4349 AANoCapture> {
4351
4352 /// See IRAttribute::isImpliedByIR
4353 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
4354 Attribute::AttrKind ImpliedAttributeKind,
4355 bool IgnoreSubsumingPositions = false);
4356
4357 /// Update \p State according to the capture capabilities of \p F for position
4358 /// \p IRP.
4359 static void determineFunctionCaptureCapabilities(const IRPosition &IRP,
4360 const Function &F,
4361 BitIntegerState &State);
4362
4363 /// See AbstractAttribute::isValidIRPositionForInit
4366 return false;
4367 return IRAttribute::isValidIRPositionForInit(A, IRP);
4368 }
4369
4370 /// State encoding bits. A set bit in the state means the property holds.
4371 /// NO_CAPTURE is the best possible state, 0 the worst possible state.
4372 enum {
4376
4377 /// If we do not capture the value in memory or through integers we can only
4378 /// communicate it back as a derived pointer.
4380
4381 /// If we do not capture the value in memory, through integers, or as a
4382 /// derived pointer we know it is not captured.
4383 NO_CAPTURE =
4385 };
4386
4387 /// Return true if we know that the underlying value is not captured in its
4388 /// respective scope.
4389 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
4390
4391 /// Return true if we assume that the underlying value is not captured in its
4392 /// respective scope.
4393 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
4394
4395 /// Return true if we know that the underlying value is not captured in its
4396 /// respective scope but we allow it to escape through a "return".
4399 }
4400
4401 /// Return true if we assume that the underlying value is not captured in its
4402 /// respective scope but we allow it to escape through a "return".
4405 }
4406
4407 /// Create an abstract attribute view for the position \p IRP.
4409
4410 /// See AbstractAttribute::getName()
4411 const std::string getName() const override { return "AANoCapture"; }
4412
4413 /// See AbstractAttribute::getIdAddr()
4414 const char *getIdAddr() const override { return &ID; }
4415
4416 /// This function should return true if the type of the \p AA is AANoCapture
4417 static bool classof(const AbstractAttribute *AA) {
4418 return (AA->getIdAddr() == &ID);
4419 }
4420
4421 /// U