LLVM 20.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/Module.h"
127#include "llvm/IR/PassManager.h"
128#include "llvm/IR/Value.h"
131#include "llvm/Support/Casting.h"
135#include "llvm/Support/ModRef.h"
140
141#include <limits>
142#include <map>
143#include <optional>
144
145namespace llvm {
146
147class DataLayout;
148class LLVMContext;
149class Pass;
150template <typename Fn> class function_ref;
151struct AADepGraphNode;
152struct AADepGraph;
153struct Attributor;
154struct AbstractAttribute;
155struct InformationCache;
156struct AAIsDead;
157struct AttributorCallGraph;
158struct IRPosition;
159
160class Function;
161
162/// Abstract Attribute helper functions.
163namespace AA {
165
166enum class GPUAddressSpace : unsigned {
167 Generic = 0,
168 Global = 1,
169 Shared = 3,
170 Constant = 4,
171 Local = 5,
172};
173
174/// Return true iff \p M target a GPU (and we can use GPU AS reasoning).
175bool isGPU(const Module &M);
176
177/// Flags to distinguish intra-procedural queries from *potentially*
178/// inter-procedural queries. Not that information can be valid for both and
179/// therefore both bits might be set.
184};
185
186struct ValueAndContext : public std::pair<Value *, const Instruction *> {
187 using Base = std::pair<Value *, const Instruction *>;
189 ValueAndContext(Value &V, const Instruction *CtxI) : Base(&V, CtxI) {}
190 ValueAndContext(Value &V, const Instruction &CtxI) : Base(&V, &CtxI) {}
191
192 Value *getValue() const { return this->first; }
193 const Instruction *getCtxI() const { return this->second; }
194};
195
196/// Return true if \p I is a `nosync` instruction. Use generic reasoning and
197/// potentially the corresponding AANoSync.
199 const AbstractAttribute &QueryingAA);
200
201/// Return true if \p V is dynamically unique, that is, there are no two
202/// "instances" of \p V at runtime with different values.
203/// Note: If \p ForAnalysisOnly is set we only check that the Attributor will
204/// never use \p V to represent two "instances" not that \p V could not
205/// technically represent them.
206bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
207 const Value &V, bool ForAnalysisOnly = true);
208
209/// Return true if \p V is a valid value in \p Scope, that is a constant or an
210/// instruction/argument of \p Scope.
211bool isValidInScope(const Value &V, const Function *Scope);
212
213/// Return true if the value of \p VAC is a valid at the position of \p VAC,
214/// that is a constant, an argument of the same function, or an instruction in
215/// that function that dominates the position.
216bool isValidAtPosition(const ValueAndContext &VAC, InformationCache &InfoCache);
217
218/// Try to convert \p V to type \p Ty without introducing new instructions. If
219/// this is not possible return `nullptr`. Note: this function basically knows
220/// how to cast various constants.
221Value *getWithType(Value &V, Type &Ty);
222
223/// Return the combination of \p A and \p B such that the result is a possible
224/// value of both. \p B is potentially casted to match the type \p Ty or the
225/// type of \p A if \p Ty is null.
226///
227/// Examples:
228/// X + none => X
229/// not_none + undef => not_none
230/// V1 + V2 => nullptr
231std::optional<Value *>
232combineOptionalValuesInAAValueLatice(const std::optional<Value *> &A,
233 const std::optional<Value *> &B, Type *Ty);
234
235/// Helper to represent an access offset and size, with logic to deal with
236/// uncertainty and check for overlapping accesses.
237struct RangeTy {
239 int64_t Size = Unassigned;
240
241 RangeTy(int64_t Offset, int64_t Size) : Offset(Offset), Size(Size) {}
242 RangeTy() = default;
243 static RangeTy getUnknown() { return RangeTy{Unknown, Unknown}; }
244
245 /// Return true if offset or size are unknown.
248 }
249
250 /// Return true if offset and size are unknown, thus this is the default
251 /// unknown object.
254 }
255
256 /// Return true if the offset and size are unassigned.
257 bool isUnassigned() const {
259 "Inconsistent state!");
260 return Offset == RangeTy::Unassigned;
261 }
262
263 /// Return true if this offset and size pair might describe an address that
264 /// overlaps with \p Range.
265 bool mayOverlap(const RangeTy &Range) const {
266 // Any unknown value and we are giving up -> overlap.
267 if (offsetOrSizeAreUnknown() || Range.offsetOrSizeAreUnknown())
268 return true;
269
270 // Check if one offset point is in the other interval [offset,
271 // offset+size].
272 return Range.Offset + Range.Size > Offset && Range.Offset < Offset + Size;
273 }
274
276 if (R.isUnassigned())
277 return *this;
278 if (isUnassigned())
279 return *this = R;
280 if (Offset == Unknown || R.Offset == Unknown)
281 Offset = Unknown;
282 if (Size == Unknown || R.Size == Unknown)
283 Size = Unknown;
285 return *this;
286 if (Offset == Unknown) {
287 Size = std::max(Size, R.Size);
288 } else if (Size == Unknown) {
289 Offset = std::min(Offset, R.Offset);
290 } else {
291 Offset = std::min(Offset, R.Offset);
292 Size = std::max(Offset + Size, R.Offset + R.Size) - Offset;
293 }
294 return *this;
295 }
296
297 /// Comparison for sorting ranges.
298 ///
299 /// Returns true if the offset of \p L is less than that of \p R. If the two
300 /// offsets are same, compare the sizes instead.
301 inline static bool LessThan(const RangeTy &L, const RangeTy &R) {
302 if (L.Offset < R.Offset)
303 return true;
304 if (L.Offset == R.Offset)
305 return L.Size < R.Size;
306 return false;
307 }
308
309 /// Constants used to represent special offsets or sizes.
310 /// - We cannot assume that Offsets and Size are non-negative.
311 /// - The constants should not clash with DenseMapInfo, such as EmptyKey
312 /// (INT64_MAX) and TombstoneKey (INT64_MIN).
313 /// We use values "in the middle" of the 64 bit range to represent these
314 /// special cases.
315 static constexpr int64_t Unassigned = std::numeric_limits<int32_t>::min();
316 static constexpr int64_t Unknown = std::numeric_limits<int32_t>::max();
317};
318
320 OS << "[" << R.Offset << ", " << R.Size << "]";
321 return OS;
322}
323
324inline bool operator==(const RangeTy &A, const RangeTy &B) {
325 return A.Offset == B.Offset && A.Size == B.Size;
326}
327
328inline bool operator!=(const RangeTy &A, const RangeTy &B) { return !(A == B); }
329
330/// Return the initial value of \p Obj with type \p Ty if that is a constant.
332 const AbstractAttribute &QueryingAA, Value &Obj,
333 Type &Ty, const TargetLibraryInfo *TLI,
334 const DataLayout &DL,
335 RangeTy *RangePtr = nullptr);
336
337/// Collect all potential values \p LI could read into \p PotentialValues. That
338/// is, the only values read by \p LI are assumed to be known and all are in
339/// \p PotentialValues. \p PotentialValueOrigins will contain all the
340/// instructions that might have put a potential value into \p PotentialValues.
341/// Dependences onto \p QueryingAA are properly tracked, \p
342/// UsedAssumedInformation will inform the caller if assumed information was
343/// used.
344///
345/// \returns True if the assumed potential copies are all in \p PotentialValues,
346/// false if something went wrong and the copies could not be
347/// determined.
349 Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues,
350 SmallSetVector<Instruction *, 4> &PotentialValueOrigins,
351 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
352 bool OnlyExact = false);
353
354/// Collect all potential values of the one stored by \p SI into
355/// \p PotentialCopies. That is, the only copies that were made via the
356/// store are assumed to be known and all are in \p PotentialCopies. Dependences
357/// onto \p QueryingAA are properly tracked, \p UsedAssumedInformation will
358/// inform the caller if assumed information was used.
359///
360/// \returns True if the assumed potential copies are all in \p PotentialCopies,
361/// false if something went wrong and the copies could not be
362/// determined.
364 Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
365 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
366 bool OnlyExact = false);
367
368/// Return true if \p IRP is readonly. This will query respective AAs that
369/// deduce the information and introduce dependences for \p QueryingAA.
370bool isAssumedReadOnly(Attributor &A, const IRPosition &IRP,
371 const AbstractAttribute &QueryingAA, bool &IsKnown);
372
373/// Return true if \p IRP is readnone. This will query respective AAs that
374/// deduce the information and introduce dependences for \p QueryingAA.
375bool isAssumedReadNone(Attributor &A, const IRPosition &IRP,
376 const AbstractAttribute &QueryingAA, bool &IsKnown);
377
378/// Return true if \p ToI is potentially reachable from \p FromI without running
379/// into any instruction in \p ExclusionSet The two instructions do not need to
380/// be in the same function. \p GoBackwardsCB can be provided to convey domain
381/// knowledge about the "lifespan" the user is interested in. By default, the
382/// callers of \p FromI are checked as well to determine if \p ToI can be
383/// reached. If the query is not interested in callers beyond a certain point,
384/// e.g., a GPU kernel entry or the function containing an alloca, the
385/// \p GoBackwardsCB should return false.
387 Attributor &A, const Instruction &FromI, const Instruction &ToI,
388 const AbstractAttribute &QueryingAA,
389 const AA::InstExclusionSetTy *ExclusionSet = nullptr,
390 std::function<bool(const Function &F)> GoBackwardsCB = nullptr);
391
392/// Same as above but it is sufficient to reach any instruction in \p ToFn.
394 Attributor &A, const Instruction &FromI, const Function &ToFn,
395 const AbstractAttribute &QueryingAA,
396 const AA::InstExclusionSetTy *ExclusionSet = nullptr,
397 std::function<bool(const Function &F)> GoBackwardsCB = nullptr);
398
399/// Return true if \p Obj is assumed to be a thread local object.
401 const AbstractAttribute &QueryingAA);
402
403/// Return true if \p I is potentially affected by a barrier.
405 const AbstractAttribute &QueryingAA);
407 const AbstractAttribute &QueryingAA,
408 const Instruction *CtxI);
409} // namespace AA
410
411template <>
412struct DenseMapInfo<AA::ValueAndContext>
413 : public DenseMapInfo<AA::ValueAndContext::Base> {
416 return Base::getEmptyKey();
417 }
419 return Base::getTombstoneKey();
420 }
421 static unsigned getHashValue(const AA::ValueAndContext &VAC) {
422 return Base::getHashValue(VAC);
423 }
424
425 static bool isEqual(const AA::ValueAndContext &LHS,
426 const AA::ValueAndContext &RHS) {
427 return Base::isEqual(LHS, RHS);
428 }
429};
430
431template <>
432struct DenseMapInfo<AA::ValueScope> : public DenseMapInfo<unsigned char> {
434 static inline AA::ValueScope getEmptyKey() {
435 return AA::ValueScope(Base::getEmptyKey());
436 }
438 return AA::ValueScope(Base::getTombstoneKey());
439 }
440 static unsigned getHashValue(const AA::ValueScope &S) {
441 return Base::getHashValue(S);
442 }
443
444 static bool isEqual(const AA::ValueScope &LHS, const AA::ValueScope &RHS) {
445 return Base::isEqual(LHS, RHS);
446 }
447};
448
449template <>
450struct DenseMapInfo<const AA::InstExclusionSetTy *>
451 : public DenseMapInfo<void *> {
453 static inline const AA::InstExclusionSetTy *getEmptyKey() {
454 return static_cast<const AA::InstExclusionSetTy *>(super::getEmptyKey());
455 }
457 return static_cast<const AA::InstExclusionSetTy *>(
458 super::getTombstoneKey());
459 }
460 static unsigned getHashValue(const AA::InstExclusionSetTy *BES) {
461 unsigned H = 0;
462 if (BES)
463 for (const auto *II : *BES)
465 return H;
466 }
469 if (LHS == RHS)
470 return true;
471 if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
472 LHS == getTombstoneKey() || RHS == getTombstoneKey())
473 return false;
474 auto SizeLHS = LHS ? LHS->size() : 0;
475 auto SizeRHS = RHS ? RHS->size() : 0;
476 if (SizeLHS != SizeRHS)
477 return false;
478 if (SizeRHS == 0)
479 return true;
480 return llvm::set_is_subset(*LHS, *RHS);
481 }
482};
483
484/// The value passed to the line option that defines the maximal initialization
485/// chain length.
486extern unsigned MaxInitializationChainLength;
487
488///{
489enum class ChangeStatus {
490 CHANGED,
491 UNCHANGED,
492};
493
498
499enum class DepClassTy {
500 REQUIRED, ///< The target cannot be valid if the source is not.
501 OPTIONAL, ///< The target may be valid if the source is not.
502 NONE, ///< Do not track a dependence between source and target.
503};
504///}
505
506/// The data structure for the nodes of a dependency graph
508public:
509 virtual ~AADepGraphNode() = default;
512
513protected:
514 /// Set of dependency graph nodes which should be updated if this one
515 /// is updated. The bit encodes if it is optional.
517
518 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
520 return cast<AbstractAttribute>(DT.getPointer());
521 }
522
523 operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
524
525public:
529
534
535 void print(raw_ostream &OS) const { print(nullptr, OS); }
536 virtual void print(Attributor *, raw_ostream &OS) const {
537 OS << "AADepNode Impl\n";
538 }
539 DepSetTy &getDeps() { return Deps; }
540
541 friend struct Attributor;
542 friend struct AADepGraph;
543};
544
545/// The data structure for the dependency graph
546///
547/// Note that in this graph if there is an edge from A to B (A -> B),
548/// then it means that B depends on A, and when the state of A is
549/// updated, node B should also be updated
551 AADepGraph() = default;
552 ~AADepGraph() = default;
553
555 static AADepGraphNode *DepGetVal(const DepTy &DT) { return DT.getPointer(); }
556 using iterator =
558
559 /// There is no root node for the dependency graph. But the SCCIterator
560 /// requires a single entry point, so we maintain a fake("synthetic") root
561 /// node that depends on every node.
564
567
568 void viewGraph();
569
570 /// Dump graph to file
571 void dumpGraph();
572
573 /// Print dependency graph
574 void print();
575};
576
577/// Helper to describe and deal with positions in the LLVM-IR.
578///
579/// A position in the IR is described by an anchor value and an "offset" that
580/// could be the argument number, for call sites and arguments, or an indicator
581/// of the "position kind". The kinds, specified in the Kind enum below, include
582/// the locations in the attribute list, i.a., function scope and return value,
583/// as well as a distinction between call sites and functions. Finally, there
584/// are floating values that do not have a corresponding attribute list
585/// position.
587 // NOTE: In the future this definition can be changed to support recursive
588 // functions.
590
591 /// The positions we distinguish in the IR.
592 enum Kind : char {
593 IRP_INVALID, ///< An invalid position.
594 IRP_FLOAT, ///< A position that is not associated with a spot suitable
595 ///< for attributes. This could be any value or instruction.
596 IRP_RETURNED, ///< An attribute for the function return value.
597 IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value.
598 IRP_FUNCTION, ///< An attribute for a function (scope).
599 IRP_CALL_SITE, ///< An attribute for a call site (function scope).
600 IRP_ARGUMENT, ///< An attribute for a function argument.
601 IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
602 };
603
604 /// Default constructor available to create invalid positions implicitly. All
605 /// other positions need to be created explicitly through the appropriate
606 /// static member function.
607 IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
608
609 /// Create a position describing the value of \p V.
610 static const IRPosition value(const Value &V,
611 const CallBaseContext *CBContext = nullptr) {
612 if (auto *Arg = dyn_cast<Argument>(&V))
613 return IRPosition::argument(*Arg, CBContext);
614 if (auto *CB = dyn_cast<CallBase>(&V))
616 return IRPosition(const_cast<Value &>(V), IRP_FLOAT, CBContext);
617 }
618
619 /// Create a position describing the instruction \p I. This is different from
620 /// the value version because call sites are treated as intrusctions rather
621 /// than their return value in this function.
622 static const IRPosition inst(const Instruction &I,
623 const CallBaseContext *CBContext = nullptr) {
624 return IRPosition(const_cast<Instruction &>(I), IRP_FLOAT, CBContext);
625 }
626
627 /// Create a position describing the function scope of \p F.
628 /// \p CBContext is used for call base specific analysis.
629 static const IRPosition function(const Function &F,
630 const CallBaseContext *CBContext = nullptr) {
631 return IRPosition(const_cast<Function &>(F), IRP_FUNCTION, CBContext);
632 }
633
634 /// Create a position describing the returned value of \p F.
635 /// \p CBContext is used for call base specific analysis.
636 static const IRPosition returned(const Function &F,
637 const CallBaseContext *CBContext = nullptr) {
638 return IRPosition(const_cast<Function &>(F), IRP_RETURNED, CBContext);
639 }
640
641 /// Create a position describing the argument \p Arg.
642 /// \p CBContext is used for call base specific analysis.
643 static const IRPosition argument(const Argument &Arg,
644 const CallBaseContext *CBContext = nullptr) {
645 return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT, CBContext);
646 }
647
648 /// Create a position describing the function scope of \p CB.
649 static const IRPosition callsite_function(const CallBase &CB) {
650 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
651 }
652
653 /// Create a position describing the returned value of \p CB.
654 static const IRPosition callsite_returned(const CallBase &CB) {
655 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
656 }
657
658 /// Create a position describing the argument of \p CB at position \p ArgNo.
659 static const IRPosition callsite_argument(const CallBase &CB,
660 unsigned ArgNo) {
661 return IRPosition(const_cast<Use &>(CB.getArgOperandUse(ArgNo)),
663 }
664
665 /// Create a position describing the argument of \p ACS at position \p ArgNo.
667 unsigned ArgNo) {
668 if (ACS.getNumArgOperands() <= ArgNo)
669 return IRPosition();
670 int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
671 if (CSArgNo >= 0)
673 cast<CallBase>(*ACS.getInstruction()), CSArgNo);
674 return IRPosition();
675 }
676
677 /// Create a position with function scope matching the "context" of \p IRP.
678 /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
679 /// will be a call site position, otherwise the function position of the
680 /// associated function.
681 static const IRPosition
683 const CallBaseContext *CBContext = nullptr) {
684 if (IRP.isAnyCallSitePosition()) {
686 cast<CallBase>(IRP.getAnchorValue()));
687 }
689 return IRPosition::function(*IRP.getAssociatedFunction(), CBContext);
690 }
691
692 bool operator==(const IRPosition &RHS) const {
693 return Enc == RHS.Enc && RHS.CBContext == CBContext;
694 }
695 bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
696
697 /// Return the value this abstract attribute is anchored with.
698 ///
699 /// The anchor value might not be the associated value if the latter is not
700 /// sufficient to determine where arguments will be manifested. This is, so
701 /// far, only the case for call site arguments as the value is not sufficient
702 /// to pinpoint them. Instead, we can use the call site as an anchor.
704 switch (getEncodingBits()) {
705 case ENC_VALUE:
706 case ENC_RETURNED_VALUE:
707 case ENC_FLOATING_FUNCTION:
708 return *getAsValuePtr();
709 case ENC_CALL_SITE_ARGUMENT_USE:
710 return *(getAsUsePtr()->getUser());
711 default:
712 llvm_unreachable("Unkown encoding!");
713 };
714 }
715
716 /// Return the associated function, if any.
718 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue())) {
719 // We reuse the logic that associates callback calles to arguments of a
720 // call site here to identify the callback callee as the associated
721 // function.
722 if (Argument *Arg = getAssociatedArgument())
723 return Arg->getParent();
724 return dyn_cast_if_present<Function>(
725 CB->getCalledOperand()->stripPointerCasts());
726 }
727 return getAnchorScope();
728 }
729
730 /// Return the associated argument, if any.
732
733 /// Return true if the position refers to a function interface, that is the
734 /// function scope, the function return, or an argument.
735 bool isFnInterfaceKind() const {
736 switch (getPositionKind()) {
740 return true;
741 default:
742 return false;
743 }
744 }
745
746 /// Return true if this is a function or call site position.
747 bool isFunctionScope() const {
748 switch (getPositionKind()) {
751 return true;
752 default:
753 return false;
754 };
755 }
756
757 /// Return the Function surrounding the anchor value.
759 Value &V = getAnchorValue();
760 if (isa<Function>(V))
761 return &cast<Function>(V);
762 if (isa<Argument>(V))
763 return cast<Argument>(V).getParent();
764 if (isa<Instruction>(V))
765 return cast<Instruction>(V).getFunction();
766 return nullptr;
767 }
768
769 /// Return the context instruction, if any.
771 Value &V = getAnchorValue();
772 if (auto *I = dyn_cast<Instruction>(&V))
773 return I;
774 if (auto *Arg = dyn_cast<Argument>(&V))
775 if (!Arg->getParent()->isDeclaration())
776 return &Arg->getParent()->getEntryBlock().front();
777 if (auto *F = dyn_cast<Function>(&V))
778 if (!F->isDeclaration())
779 return &(F->getEntryBlock().front());
780 return nullptr;
781 }
782
783 /// Return the value this abstract attribute is associated with.
785 if (getCallSiteArgNo() < 0 || isa<Argument>(&getAnchorValue()))
786 return getAnchorValue();
787 assert(isa<CallBase>(&getAnchorValue()) && "Expected a call base!");
788 return *cast<CallBase>(&getAnchorValue())
789 ->getArgOperand(getCallSiteArgNo());
790 }
791
792 /// Return the type this abstract attribute is associated with.
796 return getAssociatedValue().getType();
797 }
798
799 /// Return the callee argument number of the associated value if it is an
800 /// argument or call site argument, otherwise a negative value. In contrast to
801 /// `getCallSiteArgNo` this method will always return the "argument number"
802 /// from the perspective of the callee. This may not the same as the call site
803 /// if this is a callback call.
804 int getCalleeArgNo() const {
805 return getArgNo(/* CallbackCalleeArgIfApplicable */ true);
806 }
807
808 /// Return the call site argument number of the associated value if it is an
809 /// argument or call site argument, otherwise a negative value. In contrast to
810 /// `getCalleArgNo` this method will always return the "operand number" from
811 /// the perspective of the call site. This may not the same as the callee
812 /// perspective if this is a callback call.
813 int getCallSiteArgNo() const {
814 return getArgNo(/* CallbackCalleeArgIfApplicable */ false);
815 }
816
817 /// Return the index in the attribute list for this position.
818 unsigned getAttrIdx() const {
819 switch (getPositionKind()) {
822 break;
833 }
835 "There is no attribute index for a floating or invalid position!");
836 }
837
838 /// Return the value attributes are attached to.
840 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
841 return CB;
842 return getAssociatedFunction();
843 }
844
845 /// Return the attributes associated with this function or call site scope.
847 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
848 return CB->getAttributes();
850 }
851
852 /// Update the attributes associated with this function or call site scope.
853 void setAttrList(const AttributeList &AttrList) const {
854 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
855 return CB->setAttributes(AttrList);
856 return getAssociatedFunction()->setAttributes(AttrList);
857 }
858
859 /// Return the number of arguments associated with this function or call site
860 /// scope.
861 unsigned getNumArgs() const {
864 "Only valid for function/call site positions!");
865 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
866 return CB->arg_size();
868 }
869
870 /// Return theargument \p ArgNo associated with this function or call site
871 /// scope.
872 Value *getArg(unsigned ArgNo) const {
875 "Only valid for function/call site positions!");
876 if (auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
877 return CB->getArgOperand(ArgNo);
878 return getAssociatedFunction()->getArg(ArgNo);
879 }
880
881 /// Return the associated position kind.
883 char EncodingBits = getEncodingBits();
884 if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
886 if (EncodingBits == ENC_FLOATING_FUNCTION)
887 return IRP_FLOAT;
888
889 Value *V = getAsValuePtr();
890 if (!V)
891 return IRP_INVALID;
892 if (isa<Argument>(V))
893 return IRP_ARGUMENT;
894 if (isa<Function>(V))
895 return isReturnPosition(EncodingBits) ? IRP_RETURNED : IRP_FUNCTION;
896 if (isa<CallBase>(V))
897 return isReturnPosition(EncodingBits) ? IRP_CALL_SITE_RETURNED
899 return IRP_FLOAT;
900 }
901
903 switch (getPositionKind()) {
907 return true;
908 default:
909 return false;
910 }
911 }
912
913 /// Return true if the position is an argument or call site argument.
914 bool isArgumentPosition() const {
915 switch (getPositionKind()) {
918 return true;
919 default:
920 return false;
921 }
922 }
923
924 /// Return the same position without the call base context.
926 IRPosition Result = *this;
927 Result.CBContext = nullptr;
928 return Result;
929 }
930
931 /// Get the call base context from the position.
932 const CallBaseContext *getCallBaseContext() const { return CBContext; }
933
934 /// Check if the position has any call base context.
935 bool hasCallBaseContext() const { return CBContext != nullptr; }
936
937 /// Special DenseMap key values.
938 ///
939 ///{
940 static const IRPosition EmptyKey;
942 ///}
943
944 /// Conversion into a void * to allow reuse of pointer hashing.
945 operator void *() const { return Enc.getOpaqueValue(); }
946
947private:
948 /// Private constructor for special values only!
949 explicit IRPosition(void *Ptr, const CallBaseContext *CBContext = nullptr)
950 : CBContext(CBContext) {
952 }
953
954 /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
955 explicit IRPosition(Value &AnchorVal, Kind PK,
956 const CallBaseContext *CBContext = nullptr)
957 : CBContext(CBContext) {
958 switch (PK) {
960 llvm_unreachable("Cannot create invalid IRP with an anchor value!");
961 break;
963 // Special case for floating functions.
964 if (isa<Function>(AnchorVal) || isa<CallBase>(AnchorVal))
965 Enc = {&AnchorVal, ENC_FLOATING_FUNCTION};
966 else
967 Enc = {&AnchorVal, ENC_VALUE};
968 break;
971 Enc = {&AnchorVal, ENC_VALUE};
972 break;
975 Enc = {&AnchorVal, ENC_RETURNED_VALUE};
976 break;
978 Enc = {&AnchorVal, ENC_VALUE};
979 break;
982 "Cannot create call site argument IRP with an anchor value!");
983 break;
984 }
985 verify();
986 }
987
988 /// Return the callee argument number of the associated value if it is an
989 /// argument or call site argument. See also `getCalleeArgNo` and
990 /// `getCallSiteArgNo`.
991 int getArgNo(bool CallbackCalleeArgIfApplicable) const {
992 if (CallbackCalleeArgIfApplicable)
993 if (Argument *Arg = getAssociatedArgument())
994 return Arg->getArgNo();
995 switch (getPositionKind()) {
997 return cast<Argument>(getAsValuePtr())->getArgNo();
999 Use &U = *getAsUsePtr();
1000 return cast<CallBase>(U.getUser())->getArgOperandNo(&U);
1001 }
1002 default:
1003 return -1;
1004 }
1005 }
1006
1007 /// IRPosition for the use \p U. The position kind \p PK needs to be
1008 /// IRP_CALL_SITE_ARGUMENT, the anchor value is the user, the associated value
1009 /// the used value.
1010 explicit IRPosition(Use &U, Kind PK) {
1012 "Use constructor is for call site arguments only!");
1013 Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE};
1014 verify();
1015 }
1016
1017 /// Verify internal invariants.
1018 void verify();
1019
1020 /// Return the underlying pointer as Value *, valid for all positions but
1021 /// IRP_CALL_SITE_ARGUMENT.
1022 Value *getAsValuePtr() const {
1023 assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE &&
1024 "Not a value pointer!");
1025 return reinterpret_cast<Value *>(Enc.getPointer());
1026 }
1027
1028 /// Return the underlying pointer as Use *, valid only for
1029 /// IRP_CALL_SITE_ARGUMENT positions.
1030 Use *getAsUsePtr() const {
1031 assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE &&
1032 "Not a value pointer!");
1033 return reinterpret_cast<Use *>(Enc.getPointer());
1034 }
1035
1036 /// Return true if \p EncodingBits describe a returned or call site returned
1037 /// position.
1038 static bool isReturnPosition(char EncodingBits) {
1039 return EncodingBits == ENC_RETURNED_VALUE;
1040 }
1041
1042 /// Return true if the encoding bits describe a returned or call site returned
1043 /// position.
1044 bool isReturnPosition() const { return isReturnPosition(getEncodingBits()); }
1045
1046 /// The encoding of the IRPosition is a combination of a pointer and two
1047 /// encoding bits. The values of the encoding bits are defined in the enum
1048 /// below. The pointer is either a Value* (for the first three encoding bit
1049 /// combinations) or Use* (for ENC_CALL_SITE_ARGUMENT_USE).
1050 ///
1051 ///{
1052 enum {
1053 ENC_VALUE = 0b00,
1054 ENC_RETURNED_VALUE = 0b01,
1055 ENC_FLOATING_FUNCTION = 0b10,
1056 ENC_CALL_SITE_ARGUMENT_USE = 0b11,
1057 };
1058
1059 // Reserve the maximal amount of bits so there is no need to mask out the
1060 // remaining ones. We will not encode anything else in the pointer anyway.
1061 static constexpr int NumEncodingBits =
1062 PointerLikeTypeTraits<void *>::NumLowBitsAvailable;
1063 static_assert(NumEncodingBits >= 2, "At least two bits are required!");
1064
1065 /// The pointer with the encoding bits.
1066 PointerIntPair<void *, NumEncodingBits, char> Enc;
1067 ///}
1068
1069 /// Call base context. Used for callsite specific analysis.
1070 const CallBaseContext *CBContext = nullptr;
1071
1072 /// Return the encoding bits.
1073 char getEncodingBits() const { return Enc.getInt(); }
1074};
1075
1076/// Helper that allows IRPosition as a key in a DenseMap.
1077template <> struct DenseMapInfo<IRPosition> {
1078 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
1079 static inline IRPosition getTombstoneKey() {
1081 }
1082 static unsigned getHashValue(const IRPosition &IRP) {
1083 return (DenseMapInfo<void *>::getHashValue(IRP) << 4) ^
1085 }
1086
1087 static bool isEqual(const IRPosition &a, const IRPosition &b) {
1088 return a == b;
1089 }
1090};
1091
1092/// A visitor class for IR positions.
1093///
1094/// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
1095/// positions" wrt. attributes/information. Thus, if a piece of information
1096/// holds for a subsuming position, it also holds for the position P.
1097///
1098/// The subsuming positions always include the initial position and then,
1099/// depending on the position kind, additionally the following ones:
1100/// - for IRP_RETURNED:
1101/// - the function (IRP_FUNCTION)
1102/// - for IRP_ARGUMENT:
1103/// - the function (IRP_FUNCTION)
1104/// - for IRP_CALL_SITE:
1105/// - the callee (IRP_FUNCTION), if known
1106/// - for IRP_CALL_SITE_RETURNED:
1107/// - the callee (IRP_RETURNED), if known
1108/// - the call site (IRP_FUNCTION)
1109/// - the callee (IRP_FUNCTION), if known
1110/// - for IRP_CALL_SITE_ARGUMENT:
1111/// - the argument of the callee (IRP_ARGUMENT), if known
1112/// - the callee (IRP_FUNCTION), if known
1113/// - the position the call site argument is associated with if it is not
1114/// anchored to the call site, e.g., if it is an argument then the argument
1115/// (IRP_ARGUMENT)
1117 SmallVector<IRPosition, 4> IRPositions;
1118 using iterator = decltype(IRPositions)::iterator;
1119
1120public:
1122 iterator begin() { return IRPositions.begin(); }
1123 iterator end() { return IRPositions.end(); }
1124};
1125
1126/// Wrapper for FunctionAnalysisManager.
1128 // The client may be running the old pass manager, in which case, we need to
1129 // map the requested Analysis to its equivalent wrapper in the old pass
1130 // manager. The scheme implemented here does not require every Analysis to be
1131 // updated. Only those new analyses that the client cares about in the old
1132 // pass manager need to expose a LegacyWrapper type, and that wrapper should
1133 // support a getResult() method that matches the new Analysis.
1134 //
1135 // We need SFINAE to check for the LegacyWrapper, but function templates don't
1136 // allow partial specialization, which is needed in this case. So instead, we
1137 // use a constexpr bool to perform the SFINAE, and then use this information
1138 // inside the function template.
1139 template <typename, typename = void>
1140 static constexpr bool HasLegacyWrapper = false;
1141
1142 template <typename Analysis>
1143 typename Analysis::Result *getAnalysis(const Function &F,
1144 bool RequestCachedOnly = false) {
1145 if (!LegacyPass && !FAM)
1146 return nullptr;
1147 if (FAM) {
1148 if (CachedOnly || RequestCachedOnly)
1149 return FAM->getCachedResult<Analysis>(const_cast<Function &>(F));
1150 return &FAM->getResult<Analysis>(const_cast<Function &>(F));
1151 }
1152 if constexpr (HasLegacyWrapper<Analysis>) {
1153 if (!CachedOnly && !RequestCachedOnly)
1154 return &LegacyPass
1155 ->getAnalysis<typename Analysis::LegacyWrapper>(
1156 const_cast<Function &>(F))
1157 .getResult();
1158 if (auto *P =
1159 LegacyPass
1160 ->getAnalysisIfAvailable<typename Analysis::LegacyWrapper>())
1161 return &P->getResult();
1162 }
1163 return nullptr;
1164 }
1165
1166 /// Invalidates the analyses. Valid only when using the new pass manager.
1168 assert(FAM && "Can only be used from the new PM!");
1169 FAM->clear();
1170 }
1171
1172 AnalysisGetter(FunctionAnalysisManager &FAM, bool CachedOnly = false)
1173 : FAM(&FAM), CachedOnly(CachedOnly) {}
1174 AnalysisGetter(Pass *P, bool CachedOnly = false)
1175 : LegacyPass(P), CachedOnly(CachedOnly) {}
1176 AnalysisGetter() = default;
1177
1178private:
1179 FunctionAnalysisManager *FAM = nullptr;
1180 Pass *LegacyPass = nullptr;
1181
1182 /// If \p CachedOnly is true, no pass is created, just existing results are
1183 /// used. Also available per request.
1184 bool CachedOnly = false;
1185};
1186
1187template <typename Analysis>
1189 Analysis, std::void_t<typename Analysis::LegacyWrapper>> = true;
1190
1191/// Data structure to hold cached (LLVM-IR) information.
1192///
1193/// All attributes are given an InformationCache object at creation time to
1194/// avoid inspection of the IR by all of them individually. This default
1195/// InformationCache will hold information required by 'default' attributes,
1196/// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
1197/// is called.
1198///
1199/// If custom abstract attributes, registered manually through
1200/// Attributor::registerAA(...), need more information, especially if it is not
1201/// reusable, it is advised to inherit from the InformationCache and cast the
1202/// instance down in the abstract attributes.
1206 bool UseExplorer = true)
1207 : CGSCC(CGSCC), DL(M.getDataLayout()), Allocator(Allocator), AG(AG),
1208 TargetTriple(M.getTargetTriple()) {
1209 if (UseExplorer)
1211 /* ExploreInterBlock */ true, /* ExploreCFGForward */ true,
1212 /* ExploreCFGBackward */ true,
1213 /* LIGetter */
1214 [&](const Function &F) { return AG.getAnalysis<LoopAnalysis>(F); },
1215 /* DTGetter */
1216 [&](const Function &F) {
1218 },
1219 /* PDTGetter */
1220 [&](const Function &F) {
1222 });
1223 }
1224
1226 // The FunctionInfo objects are allocated via a BumpPtrAllocator, we call
1227 // the destructor manually.
1228 for (auto &It : FuncInfoMap)
1229 It.getSecond()->~FunctionInfo();
1230 // Same is true for the instruction exclusions sets.
1232 for (auto *BES : BESets)
1233 BES->~InstExclusionSetTy();
1234 if (Explorer)
1235 Explorer->~MustBeExecutedContextExplorer();
1236 }
1237
1238 /// Apply \p CB to all uses of \p F. If \p LookThroughConstantExprUses is
1239 /// true, constant expression users are not given to \p CB but their uses are
1240 /// traversed transitively.
1241 template <typename CBTy>
1242 static void foreachUse(Function &F, CBTy CB,
1243 bool LookThroughConstantExprUses = true) {
1244 SmallVector<Use *, 8> Worklist(make_pointer_range(F.uses()));
1245
1246 for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
1247 Use &U = *Worklist[Idx];
1248
1249 // Allow use in constant bitcasts and simply look through them.
1250 if (LookThroughConstantExprUses && isa<ConstantExpr>(U.getUser())) {
1251 for (Use &CEU : cast<ConstantExpr>(U.getUser())->uses())
1252 Worklist.push_back(&CEU);
1253 continue;
1254 }
1255
1256 CB(U);
1257 }
1258 }
1259
1260 /// The CG-SCC the pass is run on, or nullptr if it is a module pass.
1261 const SetVector<Function *> *const CGSCC = nullptr;
1262
1263 /// A vector type to hold instructions.
1265
1266 /// A map type from opcodes to instructions with this opcode.
1268
1269 /// Return the map that relates "interesting" opcodes with all instructions
1270 /// with that opcode in \p F.
1272 return getFunctionInfo(F).OpcodeInstMap;
1273 }
1274
1275 /// Return the instructions in \p F that may read or write memory.
1277 return getFunctionInfo(F).RWInsts;
1278 }
1279
1280 /// Return MustBeExecutedContextExplorer
1282 return Explorer;
1283 }
1284
1285 /// Return TargetLibraryInfo for function \p F.
1288 }
1289
1290 /// Return true if \p Arg is involved in a must-tail call, thus the argument
1291 /// of the caller or callee.
1293 FunctionInfo &FI = getFunctionInfo(*Arg.getParent());
1294 return FI.CalledViaMustTail || FI.ContainsMustTailCall;
1295 }
1296
1297 bool isOnlyUsedByAssume(const Instruction &I) const {
1298 return AssumeOnlyValues.contains(&I);
1299 }
1300
1301 /// Invalidates the cached analyses. Valid only when using the new pass
1302 /// manager.
1304
1305 /// Return the analysis result from a pass \p AP for function \p F.
1306 template <typename AP>
1307 typename AP::Result *getAnalysisResultForFunction(const Function &F,
1308 bool CachedOnly = false) {
1309 return AG.getAnalysis<AP>(F, CachedOnly);
1310 }
1311
1312 /// Return datalayout used in the module.
1313 const DataLayout &getDL() { return DL; }
1314
1315 /// Return the map conaining all the knowledge we have from `llvm.assume`s.
1316 const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
1317
1318 /// Given \p BES, return a uniqued version.
1321 auto It = BESets.find(BES);
1322 if (It != BESets.end())
1323 return *It;
1324 auto *UniqueBES = new (Allocator) AA::InstExclusionSetTy(*BES);
1325 bool Success = BESets.insert(UniqueBES).second;
1326 (void)Success;
1327 assert(Success && "Expected only new entries to be added");
1328 return UniqueBES;
1329 }
1330
1331 /// Return true if the stack (llvm::Alloca) can be accessed by other threads.
1333
1334 /// Return true if the target is a GPU.
1336 return TargetTriple.isAMDGPU() || TargetTriple.isNVPTX();
1337 }
1338
1339 /// Return all functions that might be called indirectly, only valid for
1340 /// closed world modules (see isClosedWorldModule).
1343
1344 /// Return the flat address space if the associated target has.
1345 std::optional<unsigned> getFlatAddressSpace() const;
1346
1347private:
1348 struct FunctionInfo {
1349 ~FunctionInfo();
1350
1351 /// A nested map that remembers all instructions in a function with a
1352 /// certain instruction opcode (Instruction::getOpcode()).
1353 OpcodeInstMapTy OpcodeInstMap;
1354
1355 /// A map from functions to their instructions that may read or write
1356 /// memory.
1357 InstructionVectorTy RWInsts;
1358
1359 /// Function is called by a `musttail` call.
1360 bool CalledViaMustTail;
1361
1362 /// Function contains a `musttail` call.
1363 bool ContainsMustTailCall;
1364 };
1365
1366 /// A map type from functions to informatio about it.
1367 DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
1368
1369 /// Return information about the function \p F, potentially by creating it.
1370 FunctionInfo &getFunctionInfo(const Function &F) {
1371 FunctionInfo *&FI = FuncInfoMap[&F];
1372 if (!FI) {
1373 FI = new (Allocator) FunctionInfo();
1374 initializeInformationCache(F, *FI);
1375 }
1376 return *FI;
1377 }
1378
1379 /// Vector of functions that might be callable indirectly, i.a., via a
1380 /// function pointer.
1381 SmallVector<Function *> IndirectlyCallableFunctions;
1382
1383 /// Initialize the function information cache \p FI for the function \p F.
1384 ///
1385 /// This method needs to be called for all function that might be looked at
1386 /// through the information cache interface *prior* to looking at them.
1387 void initializeInformationCache(const Function &F, FunctionInfo &FI);
1388
1389 /// The datalayout used in the module.
1390 const DataLayout &DL;
1391
1392 /// The allocator used to allocate memory, e.g. for `FunctionInfo`s.
1393 BumpPtrAllocator &Allocator;
1394
1395 /// MustBeExecutedContextExplorer
1396 MustBeExecutedContextExplorer *Explorer = nullptr;
1397
1398 /// A map with knowledge retained in `llvm.assume` instructions.
1399 RetainedKnowledgeMap KnowledgeMap;
1400
1401 /// A container for all instructions that are only used by `llvm.assume`.
1402 SetVector<const Instruction *> AssumeOnlyValues;
1403
1404 /// Cache for block sets to allow reuse.
1405 DenseSet<const AA::InstExclusionSetTy *> BESets;
1406
1407 /// Getters for analysis.
1408 AnalysisGetter &AG;
1409
1410 /// Set of inlineable functions
1411 SmallPtrSet<const Function *, 8> InlineableFunctions;
1412
1413 /// The triple describing the target machine.
1414 Triple TargetTriple;
1415
1416 /// Give the Attributor access to the members so
1417 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
1418 friend struct Attributor;
1419};
1420
1421/// Configuration for the Attributor.
1423
1425
1426 /// Is the user of the Attributor a module pass or not. This determines what
1427 /// IR we can look at and modify. If it is a module pass we might deduce facts
1428 /// outside the initial function set and modify functions outside that set,
1429 /// but only as part of the optimization of the functions in the initial
1430 /// function set. For CGSCC passes we can look at the IR of the module slice
1431 /// but never run any deduction, or perform any modification, outside the
1432 /// initial function set (which we assume is the SCC).
1433 bool IsModulePass = true;
1434
1435 /// Flag to determine if we can delete functions or keep dead ones around.
1436 bool DeleteFns = true;
1437
1438 /// Flag to determine if we rewrite function signatures.
1440
1441 /// Flag to determine if we want to initialize all default AAs for an internal
1442 /// function marked live. See also: InitializationCallback>
1444
1445 /// Flag to determine if we should skip all liveness checks early on.
1446 bool UseLiveness = true;
1447
1448 /// Flag to indicate if the entire world is contained in this module, that
1449 /// is, no outside functions exist.
1451
1452 /// Callback function to be invoked on internal functions marked live.
1453 std::function<void(Attributor &A, const Function &F)> InitializationCallback =
1454 nullptr;
1455
1456 /// Callback function to determine if an indirect call targets should be made
1457 /// direct call targets (with an if-cascade).
1458 std::function<bool(Attributor &A, const AbstractAttribute &AA, CallBase &CB,
1459 Function &AssumedCallee, unsigned NumAssumedCallees)>
1461
1462 /// Helper to update an underlying call graph and to delete functions.
1464
1465 /// If not null, a set limiting the attribute opportunities.
1467
1468 /// Maximum number of iterations to run until fixpoint.
1469 std::optional<unsigned> MaxFixpointIterations;
1470
1471 /// A callback function that returns an ORE object from a Function pointer.
1472 ///{
1476 ///}
1477
1478 /// The name of the pass running the attributor, used to emit remarks.
1479 const char *PassName = nullptr;
1480
1483};
1484
1485/// A debug counter to limit the number of AAs created.
1486DEBUG_COUNTER(NumAbstractAttributes, "num-abstract-attributes",
1487 "How many AAs should be initialized");
1488
1489/// The fixpoint analysis framework that orchestrates the attribute deduction.
1490///
1491/// The Attributor provides a general abstract analysis framework (guided
1492/// fixpoint iteration) as well as helper functions for the deduction of
1493/// (LLVM-IR) attributes. However, also other code properties can be deduced,
1494/// propagated, and ultimately manifested through the Attributor framework. This
1495/// is particularly useful if these properties interact with attributes and a
1496/// co-scheduled deduction allows to improve the solution. Even if not, thus if
1497/// attributes/properties are completely isolated, they should use the
1498/// Attributor framework to reduce the number of fixpoint iteration frameworks
1499/// in the code base. Note that the Attributor design makes sure that isolated
1500/// attributes are not impacted, in any way, by others derived at the same time
1501/// if there is no cross-reasoning performed.
1502///
1503/// The public facing interface of the Attributor is kept simple and basically
1504/// allows abstract attributes to one thing, query abstract attributes
1505/// in-flight. There are two reasons to do this:
1506/// a) The optimistic state of one abstract attribute can justify an
1507/// optimistic state of another, allowing to framework to end up with an
1508/// optimistic (=best possible) fixpoint instead of one based solely on
1509/// information in the IR.
1510/// b) This avoids reimplementing various kinds of lookups, e.g., to check
1511/// for existing IR attributes, in favor of a single lookups interface
1512/// provided by an abstract attribute subclass.
1513///
1514/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1515/// described in the file comment.
1517
1518 /// Constructor
1519 ///
1520 /// \param Functions The set of functions we are deriving attributes for.
1521 /// \param InfoCache Cache to hold various information accessible for
1522 /// the abstract attributes.
1523 /// \param Configuration The Attributor configuration which determines what
1524 /// generic features to use.
1525 Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
1526 AttributorConfig Configuration);
1527
1528 ~Attributor();
1529
1530 /// Run the analyses until a fixpoint is reached or enforced (timeout).
1531 ///
1532 /// The attributes registered with this Attributor can be used after as long
1533 /// as the Attributor is not destroyed (it owns the attributes now).
1534 ///
1535 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
1536 ChangeStatus run();
1537
1538 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
1539 /// no abstract attribute is found equivalent positions are checked, see
1540 /// SubsumingPositionIterator. Thus, the returned abstract attribute
1541 /// might be anchored at a different position, e.g., the callee if \p IRP is a
1542 /// call base.
1543 ///
1544 /// This method is the only (supported) way an abstract attribute can retrieve
1545 /// information from another abstract attribute. As an example, take an
1546 /// abstract attribute that determines the memory access behavior for a
1547 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
1548 /// most optimistic information for other abstract attributes in-flight, e.g.
1549 /// the one reasoning about the "captured" state for the argument or the one
1550 /// reasoning on the memory access behavior of the function as a whole.
1551 ///
1552 /// If the DepClass enum is set to `DepClassTy::None` the dependence from
1553 /// \p QueryingAA to the return abstract attribute is not automatically
1554 /// recorded. This should only be used if the caller will record the
1555 /// dependence explicitly if necessary, thus if it the returned abstract
1556 /// attribute is used for reasoning. To record the dependences explicitly use
1557 /// the `Attributor::recordDependence` method.
1558 template <typename AAType>
1559 const AAType *getAAFor(const AbstractAttribute &QueryingAA,
1560 const IRPosition &IRP, DepClassTy DepClass) {
1561 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1562 /* ForceUpdate */ false);
1563 }
1564
1565 /// The version of getAAFor that allows to omit a querying abstract
1566 /// attribute. Using this after Attributor started running is restricted to
1567 /// only the Attributor itself. Initial seeding of AAs can be done via this
1568 /// function.
1569 /// NOTE: ForceUpdate is ignored in any stage other than the update stage.
1570 template <typename AAType>
1571 const AAType *getOrCreateAAFor(IRPosition IRP,
1572 const AbstractAttribute *QueryingAA,
1573 DepClassTy DepClass, bool ForceUpdate = false,
1574 bool UpdateAfterInit = true) {
1575 if (!shouldPropagateCallBaseContext(IRP))
1576 IRP = IRP.stripCallBaseContext();
1577
1578 if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1579 /* AllowInvalidState */ true)) {
1580 if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1581 updateAA(*AAPtr);
1582 return AAPtr;
1583 }
1584
1585 bool ShouldUpdateAA;
1586 if (!shouldInitialize<AAType>(IRP, ShouldUpdateAA))
1587 return nullptr;
1588
1589 if (!DebugCounter::shouldExecute(NumAbstractAttributes))
1590 return nullptr;
1591
1592 // No matching attribute found, create one.
1593 // Use the static create method.
1594 auto &AA = AAType::createForPosition(IRP, *this);
1595
1596 // Always register a new attribute to make sure we clean up the allocated
1597 // memory properly.
1598 registerAA(AA);
1599
1600 // If we are currenty seeding attributes, enforce seeding rules.
1601 if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1602 AA.getState().indicatePessimisticFixpoint();
1603 return &AA;
1604 }
1605
1606 // Bootstrap the new attribute with an initial update to propagate
1607 // information, e.g., function -> call site.
1608 {
1609 TimeTraceScope TimeScope("initialize", [&]() {
1610 return AA.getName() +
1611 std::to_string(AA.getIRPosition().getPositionKind());
1612 });
1613 ++InitializationChainLength;
1614 AA.initialize(*this);
1615 --InitializationChainLength;
1616 }
1617
1618 if (!ShouldUpdateAA) {
1619 AA.getState().indicatePessimisticFixpoint();
1620 return &AA;
1621 }
1622
1623 // Allow seeded attributes to declare dependencies.
1624 // Remember the seeding state.
1625 if (UpdateAfterInit) {
1626 AttributorPhase OldPhase = Phase;
1627 Phase = AttributorPhase::UPDATE;
1628
1629 updateAA(AA);
1630
1631 Phase = OldPhase;
1632 }
1633
1634 if (QueryingAA && AA.getState().isValidState())
1635 recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
1636 DepClass);
1637 return &AA;
1638 }
1639
1640 template <typename AAType>
1641 const AAType *getOrCreateAAFor(const IRPosition &IRP) {
1642 return getOrCreateAAFor<AAType>(IRP, /* QueryingAA */ nullptr,
1644 }
1645
1646 /// Return the attribute of \p AAType for \p IRP if existing and valid. This
1647 /// also allows non-AA users lookup.
1648 template <typename AAType>
1649 AAType *lookupAAFor(const IRPosition &IRP,
1650 const AbstractAttribute *QueryingAA = nullptr,
1652 bool AllowInvalidState = false) {
1653 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1654 "Cannot query an attribute with a type not derived from "
1655 "'AbstractAttribute'!");
1656 // Lookup the abstract attribute of type AAType. If found, return it after
1657 // registering a dependence of QueryingAA on the one returned attribute.
1658 AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP});
1659 if (!AAPtr)
1660 return nullptr;
1661
1662 AAType *AA = static_cast<AAType *>(AAPtr);
1663
1664 // Do not register a dependence on an attribute with an invalid state.
1665 if (DepClass != DepClassTy::NONE && QueryingAA &&
1666 AA->getState().isValidState())
1667 recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
1668 DepClass);
1669
1670 // Return nullptr if this attribute has an invalid state.
1671 if (!AllowInvalidState && !AA->getState().isValidState())
1672 return nullptr;
1673 return AA;
1674 }
1675
1676 /// Allows a query AA to request an update if a new query was received.
1678
1679 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
1680 /// \p FromAA changes \p ToAA should be updated as well.
1681 ///
1682 /// This method should be used in conjunction with the `getAAFor` method and
1683 /// with the DepClass enum passed to the method set to None. This can
1684 /// be beneficial to avoid false dependences but it requires the users of
1685 /// `getAAFor` to explicitly record true dependences through this method.
1686 /// The \p DepClass flag indicates if the dependence is striclty necessary.
1687 /// That means for required dependences, if \p FromAA changes to an invalid
1688 /// state, \p ToAA can be moved to a pessimistic fixpoint because it required
1689 /// information from \p FromAA but none are available anymore.
1690 void recordDependence(const AbstractAttribute &FromAA,
1691 const AbstractAttribute &ToAA, DepClassTy DepClass);
1692
1693 /// Introduce a new abstract attribute into the fixpoint analysis.
1694 ///
1695 /// Note that ownership of the attribute is given to the Attributor. It will
1696 /// invoke delete for the Attributor on destruction of the Attributor.
1697 ///
1698 /// Attributes are identified by their IR position (AAType::getIRPosition())
1699 /// and the address of their static member (see AAType::ID).
1700 template <typename AAType> AAType &registerAA(AAType &AA) {
1701 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1702 "Cannot register an attribute with a type not derived from "
1703 "'AbstractAttribute'!");
1704 // Put the attribute in the lookup map structure and the container we use to
1705 // keep track of all attributes.
1706 const IRPosition &IRP = AA.getIRPosition();
1707 AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
1708
1709 assert(!AAPtr && "Attribute already in map!");
1710 AAPtr = &AA;
1711
1712 // Register AA with the synthetic root only before the manifest stage.
1713 if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1716
1717 return AA;
1718 }
1719
1720 /// Return the internal information cache.
1721 InformationCache &getInfoCache() { return InfoCache; }
1722
1723 /// Return true if this is a module pass, false otherwise.
1724 bool isModulePass() const { return Configuration.IsModulePass; }
1725
1726 /// Return true if we should specialize the call site \b CB for the potential
1727 /// callee \p Fn.
1729 CallBase &CB, Function &Callee,
1730 unsigned NumAssumedCallees) {
1731 return Configuration.IndirectCalleeSpecializationCallback
1733 *this, AA, CB, Callee, NumAssumedCallees)
1734 : true;
1735 }
1736
1737 /// Return true if the module contains the whole world, thus, no outside
1738 /// functions exist.
1739 bool isClosedWorldModule() const;
1740
1741 /// Return true if we derive attributes for \p Fn
1742 bool isRunOn(Function &Fn) const { return isRunOn(&Fn); }
1743 bool isRunOn(Function *Fn) const {
1744 return Functions.empty() || Functions.count(Fn);
1745 }
1746
1747 template <typename AAType> bool shouldUpdateAA(const IRPosition &IRP) {
1748 // If this is queried in the manifest stage, we force the AA to indicate
1749 // pessimistic fixpoint immediately.
1750 if (Phase == AttributorPhase::MANIFEST || Phase == AttributorPhase::CLEANUP)
1751 return false;
1752
1753 Function *AssociatedFn = IRP.getAssociatedFunction();
1754
1755 if (IRP.isAnyCallSitePosition()) {
1756 // Check if we require a callee but there is none.
1757 if (!AssociatedFn && AAType::requiresCalleeForCallBase())
1758 return false;
1759
1760 // Check if we require non-asm but it is inline asm.
1761 if (AAType::requiresNonAsmForCallBase() &&
1762 cast<CallBase>(IRP.getAnchorValue()).isInlineAsm())
1763 return false;
1764 }
1765
1766 // Check if we require a calles but we can't see all.
1767 if (AAType::requiresCallersForArgOrFunction())
1770 if (!AssociatedFn->hasLocalLinkage())
1771 return false;
1772
1773 if (!AAType::isValidIRPositionForUpdate(*this, IRP))
1774 return false;
1775
1776 // We update only AAs associated with functions in the Functions set or
1777 // call sites of them.
1778 return (!AssociatedFn || isModulePass() || isRunOn(AssociatedFn) ||
1779 isRunOn(IRP.getAnchorScope()));
1780 }
1781
1782 template <typename AAType>
1783 bool shouldInitialize(const IRPosition &IRP, bool &ShouldUpdateAA) {
1784 if (!AAType::isValidIRPositionForInit(*this, IRP))
1785 return false;
1786
1787 if (Configuration.Allowed && !Configuration.Allowed->count(&AAType::ID))
1788 return false;
1789
1790 // For now we skip anything in naked and optnone functions.
1791 const Function *AnchorFn = IRP.getAnchorScope();
1792 if (AnchorFn && (AnchorFn->hasFnAttribute(Attribute::Naked) ||
1793 AnchorFn->hasFnAttribute(Attribute::OptimizeNone)))
1794 return false;
1795
1796 // Avoid too many nested initializations to prevent a stack overflow.
1797 if (InitializationChainLength > MaxInitializationChainLength)
1798 return false;
1799
1800 ShouldUpdateAA = shouldUpdateAA<AAType>(IRP);
1801
1802 return !AAType::hasTrivialInitializer() || ShouldUpdateAA;
1803 }
1804
1805 /// Determine opportunities to derive 'default' attributes in \p F and create
1806 /// abstract attribute objects for them.
1807 ///
1808 /// \param F The function that is checked for attribute opportunities.
1809 ///
1810 /// Note that abstract attribute instances are generally created even if the
1811 /// IR already contains the information they would deduce. The most important
1812 /// reason for this is the single interface, the one of the abstract attribute
1813 /// instance, which can be queried without the need to look at the IR in
1814 /// various places.
1816
1817 /// Determine whether the function \p F is IPO amendable
1818 ///
1819 /// If a function is exactly defined or it has alwaysinline attribute
1820 /// and is viable to be inlined, we say it is IPO amendable
1822 return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F) ||
1823 (Configuration.IPOAmendableCB && Configuration.IPOAmendableCB(F));
1824 }
1825
1826 /// Mark the internal function \p F as live.
1827 ///
1828 /// This will trigger the identification and initialization of attributes for
1829 /// \p F.
1831 assert(F.hasLocalLinkage() &&
1832 "Only local linkage is assumed dead initially.");
1833
1834 if (Configuration.DefaultInitializeLiveInternals)
1836 if (Configuration.InitializationCallback)
1837 Configuration.InitializationCallback(*this, F);
1838 }
1839
1840 /// Record that \p U is to be replaces with \p NV after information was
1841 /// manifested. This also triggers deletion of trivially dead istructions.
1843 Value *&V = ToBeChangedUses[&U];
1844 if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
1845 isa_and_nonnull<UndefValue>(V)))
1846 return false;
1847 assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1848 "Use was registered twice for replacement with different values!");
1849 V = &NV;
1850 return true;
1851 }
1852
1853 /// Helper function to replace all uses associated with \p IRP with \p NV.
1854 /// Return true if there is any change. The flag \p ChangeDroppable indicates
1855 /// if dropppable uses should be changed too.
1857 bool ChangeDroppable = true) {
1859 auto *CB = cast<CallBase>(IRP.getCtxI());
1861 CB->getArgOperandUse(IRP.getCallSiteArgNo()), NV);
1862 }
1863 Value &V = IRP.getAssociatedValue();
1864 auto &Entry = ToBeChangedValues[&V];
1865 Value *CurNV = get<0>(Entry);
1866 if (CurNV && (CurNV->stripPointerCasts() == NV.stripPointerCasts() ||
1867 isa<UndefValue>(CurNV)))
1868 return false;
1869 assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) &&
1870 "Value replacement was registered twice with different values!");
1871 Entry = {&NV, ChangeDroppable};
1872 return true;
1873 }
1874
1875 /// Record that \p I is to be replaced with `unreachable` after information
1876 /// was manifested.
1878 ToBeChangedToUnreachableInsts.insert(I);
1879 }
1880
1881 /// Record that \p II has at least one dead successor block. This information
1882 /// is used, e.g., to replace \p II with a call, after information was
1883 /// manifested.
1885 InvokeWithDeadSuccessor.insert(&II);
1886 }
1887
1888 /// Record that \p I is deleted after information was manifested. This also
1889 /// triggers deletion of trivially dead istructions.
1890 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
1891
1892 /// Record that \p BB is deleted after information was manifested. This also
1893 /// triggers deletion of trivially dead istructions.
1894 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
1895
1896 // Record that \p BB is added during the manifest of an AA. Added basic blocks
1897 // are preserved in the IR.
1899 ManifestAddedBlocks.insert(&BB);
1900 }
1901
1902 /// Record that \p F is deleted after information was manifested.
1904 if (Configuration.DeleteFns)
1905 ToBeDeletedFunctions.insert(&F);
1906 }
1907
1908 /// Return the attributes of kind \p AK existing in the IR as operand bundles
1909 /// of an llvm.assume.
1912
1913 /// Return true if any kind in \p AKs existing in the IR at a position that
1914 /// will affect this one. See also getAttrs(...).
1915 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1916 /// e.g., the function position if this is an
1917 /// argument position, should be ignored.
1919 bool IgnoreSubsumingPositions = false,
1920 Attribute::AttrKind ImpliedAttributeKind = Attribute::None);
1921
1922 /// Return the attributes of any kind in \p AKs existing in the IR at a
1923 /// position that will affect this one. While each position can only have a
1924 /// single attribute of any kind in \p AKs, there are "subsuming" positions
1925 /// that could have an attribute as well. This method returns all attributes
1926 /// found in \p Attrs.
1927 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
1928 /// e.g., the function position if this is an
1929 /// argument position, should be ignored.
1932 bool IgnoreSubsumingPositions = false);
1933
1934 /// Remove all \p AttrKinds attached to \p IRP.
1938
1939 /// Attach \p DeducedAttrs to \p IRP, if \p ForceReplace is set we do this
1940 /// even if the same attribute kind was already present.
1942 ArrayRef<Attribute> DeducedAttrs,
1943 bool ForceReplace = false);
1944
1945private:
1946 /// Helper to check \p Attrs for \p AK, if not found, check if \p
1947 /// AAType::isImpliedByIR is true, and if not, create AAType for \p IRP.
1948 template <Attribute::AttrKind AK, typename AAType>
1949 void checkAndQueryIRAttr(const IRPosition &IRP, AttributeSet Attrs);
1950
1951 /// Helper to apply \p CB on all attributes of type \p AttrDescs of \p IRP.
1952 template <typename DescTy>
1953 ChangeStatus updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs,
1954 function_ref<bool(const DescTy &, AttributeSet,
1956 CB);
1957
1958 /// Mapping from functions/call sites to their attributes.
1960
1961public:
1962 /// If \p IRP is assumed to be a constant, return it, if it is unclear yet,
1963 /// return std::nullopt, otherwise return `nullptr`.
1964 std::optional<Constant *> getAssumedConstant(const IRPosition &IRP,
1965 const AbstractAttribute &AA,
1966 bool &UsedAssumedInformation);
1967 std::optional<Constant *> getAssumedConstant(const Value &V,
1968 const AbstractAttribute &AA,
1969 bool &UsedAssumedInformation) {
1970 return getAssumedConstant(IRPosition::value(V), AA, UsedAssumedInformation);
1971 }
1972
1973 /// If \p V is assumed simplified, return it, if it is unclear yet,
1974 /// return std::nullopt, otherwise return `nullptr`.
1975 std::optional<Value *> getAssumedSimplified(const IRPosition &IRP,
1976 const AbstractAttribute &AA,
1977 bool &UsedAssumedInformation,
1978 AA::ValueScope S) {
1979 return getAssumedSimplified(IRP, &AA, UsedAssumedInformation, S);
1980 }
1981 std::optional<Value *> getAssumedSimplified(const Value &V,
1982 const AbstractAttribute &AA,
1983 bool &UsedAssumedInformation,
1984 AA::ValueScope S) {
1986 UsedAssumedInformation, S);
1987 }
1988
1989 /// If \p V is assumed simplified, return it, if it is unclear yet,
1990 /// return std::nullopt, otherwise return `nullptr`. Same as the public
1991 /// version except that it can be used without recording dependences on any \p
1992 /// AA.
1993 std::optional<Value *> getAssumedSimplified(const IRPosition &V,
1994 const AbstractAttribute *AA,
1995 bool &UsedAssumedInformation,
1996 AA::ValueScope S);
1997
1998 /// Try to simplify \p IRP and in the scope \p S. If successful, true is
1999 /// returned and all potential values \p IRP can take are put into \p Values.
2000 /// If the result in \p Values contains select or PHI instructions it means
2001 /// those could not be simplified to a single value. Recursive calls with
2002 /// these instructions will yield their respective potential values. If false
2003 /// is returned no other information is valid.
2004 bool getAssumedSimplifiedValues(const IRPosition &IRP,
2005 const AbstractAttribute *AA,
2008 bool &UsedAssumedInformation,
2009 bool RecurseForSelectAndPHI = true);
2010
2011 /// Register \p CB as a simplification callback.
2012 /// `Attributor::getAssumedSimplified` will use these callbacks before
2013 /// we it will ask `AAValueSimplify`. It is important to ensure this
2014 /// is called before `identifyDefaultAbstractAttributes`, assuming the
2015 /// latter is called at all.
2016 using SimplifictionCallbackTy = std::function<std::optional<Value *>(
2017 const IRPosition &, const AbstractAttribute *, bool &)>;
2019 const SimplifictionCallbackTy &CB) {
2020 SimplificationCallbacks[IRP].emplace_back(CB);
2021 }
2022
2023 /// Return true if there is a simplification callback for \p IRP.
2025 return SimplificationCallbacks.count(IRP);
2026 }
2027
2028 /// Register \p CB as a simplification callback.
2029 /// Similar to \p registerSimplificationCallback, the call back will be called
2030 /// first when we simplify a global variable \p GV.
2032 std::function<std::optional<Constant *>(
2033 const GlobalVariable &, const AbstractAttribute *, bool &)>;
2035 const GlobalVariable &GV,
2037 GlobalVariableSimplificationCallbacks[&GV].emplace_back(CB);
2038 }
2039
2040 /// Return true if there is a simplification callback for \p GV.
2042 return GlobalVariableSimplificationCallbacks.count(&GV);
2043 }
2044
2045 /// Return \p std::nullopt if there is no call back registered for \p GV or
2046 /// the call back is still not sure if \p GV can be simplified. Return \p
2047 /// nullptr if \p GV can't be simplified.
2048 std::optional<Constant *>
2050 const AbstractAttribute *AA,
2051 bool &UsedAssumedInformation) {
2052 assert(GlobalVariableSimplificationCallbacks.contains(&GV));
2053 for (auto &CB : GlobalVariableSimplificationCallbacks.lookup(&GV)) {
2054 auto SimplifiedGV = CB(GV, AA, UsedAssumedInformation);
2055 // For now we assume the call back will not return a std::nullopt.
2056 assert(SimplifiedGV.has_value() && "SimplifiedGV has not value");
2057 return *SimplifiedGV;
2058 }
2059 llvm_unreachable("there must be a callback registered");
2060 }
2061
2063 std::function<bool(Attributor &, const AbstractAttribute *)>;
2065 const VirtualUseCallbackTy &CB) {
2066 VirtualUseCallbacks[&V].emplace_back(CB);
2067 }
2068
2069private:
2070 /// The vector with all simplification callbacks registered by outside AAs.
2072 SimplificationCallbacks;
2073
2074 /// The vector with all simplification callbacks for global variables
2075 /// registered by outside AAs.
2076 DenseMap<const GlobalVariable *,
2078 GlobalVariableSimplificationCallbacks;
2079
2081 VirtualUseCallbacks;
2082
2083public:
2084 /// Translate \p V from the callee context into the call site context.
2085 std::optional<Value *>
2086 translateArgumentToCallSiteContent(std::optional<Value *> V, CallBase &CB,
2087 const AbstractAttribute &AA,
2088 bool &UsedAssumedInformation);
2089
2090 /// Return true if \p AA (or its context instruction) is assumed dead.
2091 ///
2092 /// If \p LivenessAA is not provided it is queried.
2093 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA,
2094 bool &UsedAssumedInformation,
2095 bool CheckBBLivenessOnly = false,
2096 DepClassTy DepClass = DepClassTy::OPTIONAL);
2097
2098 /// Return true if \p I is assumed dead.
2099 ///
2100 /// If \p LivenessAA is not provided it is queried.
2101 bool isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA,
2102 const AAIsDead *LivenessAA, bool &UsedAssumedInformation,
2103 bool CheckBBLivenessOnly = false,
2105 bool CheckForDeadStore = false);
2106
2107 /// Return true if \p U is assumed dead.
2108 ///
2109 /// If \p FnLivenessAA is not provided it is queried.
2110 bool isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA,
2111 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2112 bool CheckBBLivenessOnly = false,
2113 DepClassTy DepClass = DepClassTy::OPTIONAL);
2114
2115 /// Return true if \p IRP is assumed dead.
2116 ///
2117 /// If \p FnLivenessAA is not provided it is queried.
2118 bool isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA,
2119 const AAIsDead *FnLivenessAA, bool &UsedAssumedInformation,
2120 bool CheckBBLivenessOnly = false,
2121 DepClassTy DepClass = DepClassTy::OPTIONAL);
2122
2123 /// Return true if \p BB is assumed dead.
2124 ///
2125 /// If \p LivenessAA is not provided it is queried.
2126 bool isAssumedDead(const BasicBlock &BB, const AbstractAttribute *QueryingAA,
2127 const AAIsDead *FnLivenessAA,
2128 DepClassTy DepClass = DepClassTy::OPTIONAL);
2129
2130 /// Check \p Pred on all potential Callees of \p CB.
2131 ///
2132 /// This method will evaluate \p Pred with all potential callees of \p CB as
2133 /// input and return true if \p Pred does. If some callees might be unknown
2134 /// this function will return false.
2135 bool checkForAllCallees(
2136 function_ref<bool(ArrayRef<const Function *> Callees)> Pred,
2137 const AbstractAttribute &QueryingAA, const CallBase &CB);
2138
2139 /// Check \p Pred on all (transitive) uses of \p V.
2140 ///
2141 /// This method will evaluate \p Pred on all (transitive) uses of the
2142 /// associated value and return true if \p Pred holds every time.
2143 /// If uses are skipped in favor of equivalent ones, e.g., if we look through
2144 /// memory, the \p EquivalentUseCB will be used to give the caller an idea
2145 /// what original used was replaced by a new one (or new ones). The visit is
2146 /// cut short if \p EquivalentUseCB returns false and the function will return
2147 /// false as well.
2148 bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
2149 const AbstractAttribute &QueryingAA, const Value &V,
2150 bool CheckBBLivenessOnly = false,
2151 DepClassTy LivenessDepClass = DepClassTy::OPTIONAL,
2152 bool IgnoreDroppableUses = true,
2153 function_ref<bool(const Use &OldU, const Use &NewU)>
2154 EquivalentUseCB = nullptr);
2155
2156 /// Emit a remark generically.
2157 ///
2158 /// This template function can be used to generically emit a remark. The
2159 /// RemarkKind should be one of the following:
2160 /// - OptimizationRemark to indicate a successful optimization attempt
2161 /// - OptimizationRemarkMissed to report a failed optimization attempt
2162 /// - OptimizationRemarkAnalysis to provide additional information about an
2163 /// optimization attempt
2164 ///
2165 /// The remark is built using a callback function \p RemarkCB that takes a
2166 /// RemarkKind as input and returns a RemarkKind.
2167 template <typename RemarkKind, typename RemarkCallBack>
2169 RemarkCallBack &&RemarkCB) const {
2170 if (!Configuration.OREGetter)
2171 return;
2172
2173 Function *F = I->getFunction();
2174 auto &ORE = Configuration.OREGetter(F);
2175
2176 if (RemarkName.starts_with("OMP"))
2177 ORE.emit([&]() {
2178 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I))
2179 << " [" << RemarkName << "]";
2180 });
2181 else
2182 ORE.emit([&]() {
2183 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, I));
2184 });
2185 }
2186
2187 /// Emit a remark on a function.
2188 template <typename RemarkKind, typename RemarkCallBack>
2189 void emitRemark(Function *F, StringRef RemarkName,
2190 RemarkCallBack &&RemarkCB) const {
2191 if (!Configuration.OREGetter)
2192 return;
2193
2194 auto &ORE = Configuration.OREGetter(F);
2195
2196 if (RemarkName.starts_with("OMP"))
2197 ORE.emit([&]() {
2198 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F))
2199 << " [" << RemarkName << "]";
2200 });
2201 else
2202 ORE.emit([&]() {
2203 return RemarkCB(RemarkKind(Configuration.PassName, RemarkName, F));
2204 });
2205 }
2206
2207 /// Helper struct used in the communication between an abstract attribute (AA)
2208 /// that wants to change the signature of a function and the Attributor which
2209 /// applies the changes. The struct is partially initialized with the
2210 /// information from the AA (see the constructor). All other members are
2211 /// provided by the Attributor prior to invoking any callbacks.
2213 /// Callee repair callback type
2214 ///
2215 /// The function repair callback is invoked once to rewire the replacement
2216 /// arguments in the body of the new function. The argument replacement info
2217 /// is passed, as build from the registerFunctionSignatureRewrite call, as
2218 /// well as the replacement function and an iteratore to the first
2219 /// replacement argument.
2220 using CalleeRepairCBTy = std::function<void(
2222
2223 /// Abstract call site (ACS) repair callback type
2224 ///
2225 /// The abstract call site repair callback is invoked once on every abstract
2226 /// call site of the replaced function (\see ReplacedFn). The callback needs
2227 /// to provide the operands for the call to the new replacement function.
2228 /// The number and type of the operands appended to the provided vector
2229 /// (second argument) is defined by the number and types determined through
2230 /// the replacement type vector (\see ReplacementTypes). The first argument
2231 /// is the ArgumentReplacementInfo object registered with the Attributor
2232 /// through the registerFunctionSignatureRewrite call.
2234 std::function<void(const ArgumentReplacementInfo &, AbstractCallSite,
2236
2237 /// Simple getters, see the corresponding members for details.
2238 ///{
2239
2240 Attributor &getAttributor() const { return A; }
2241 const Function &getReplacedFn() const { return ReplacedFn; }
2242 const Argument &getReplacedArg() const { return ReplacedArg; }
2243 unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); }
2245 return ReplacementTypes;
2246 }
2247
2248 ///}
2249
2250 private:
2251 /// Constructor that takes the argument to be replaced, the types of
2252 /// the replacement arguments, as well as callbacks to repair the call sites
2253 /// and new function after the replacement happened.
2255 ArrayRef<Type *> ReplacementTypes,
2256 CalleeRepairCBTy &&CalleeRepairCB,
2257 ACSRepairCBTy &&ACSRepairCB)
2258 : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg),
2259 ReplacementTypes(ReplacementTypes),
2260 CalleeRepairCB(std::move(CalleeRepairCB)),
2261 ACSRepairCB(std::move(ACSRepairCB)) {}
2262
2263 /// Reference to the attributor to allow access from the callbacks.
2264 Attributor &A;
2265
2266 /// The "old" function replaced by ReplacementFn.
2267 const Function &ReplacedFn;
2268
2269 /// The "old" argument replaced by new ones defined via ReplacementTypes.
2270 const Argument &ReplacedArg;
2271
2272 /// The types of the arguments replacing ReplacedArg.
2273 const SmallVector<Type *, 8> ReplacementTypes;
2274
2275 /// Callee repair callback, see CalleeRepairCBTy.
2276 const CalleeRepairCBTy CalleeRepairCB;
2277
2278 /// Abstract call site (ACS) repair callback, see ACSRepairCBTy.
2279 const ACSRepairCBTy ACSRepairCB;
2280
2281 /// Allow access to the private members from the Attributor.
2282 friend struct Attributor;
2283 };
2284
2285 /// Check if we can rewrite a function signature.
2286 ///
2287 /// The argument \p Arg is replaced with new ones defined by the number,
2288 /// order, and types in \p ReplacementTypes.
2289 ///
2290 /// \returns True, if the replacement can be registered, via
2291 /// registerFunctionSignatureRewrite, false otherwise.
2293 ArrayRef<Type *> ReplacementTypes);
2294
2295 /// Register a rewrite for a function signature.
2296 ///
2297 /// The argument \p Arg is replaced with new ones defined by the number,
2298 /// order, and types in \p ReplacementTypes. The rewiring at the call sites is
2299 /// done through \p ACSRepairCB and at the callee site through
2300 /// \p CalleeRepairCB.
2301 ///
2302 /// \returns True, if the replacement was registered, false otherwise.
2304 Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2307
2308 /// Check \p Pred on all function call sites.
2309 ///
2310 /// This method will evaluate \p Pred on call sites and return
2311 /// true if \p Pred holds in every call sites. However, this is only possible
2312 /// all call sites are known, hence the function has internal linkage.
2313 /// If true is returned, \p UsedAssumedInformation is set if assumed
2314 /// information was used to skip or simplify potential call sites.
2316 const AbstractAttribute &QueryingAA,
2317 bool RequireAllCallSites,
2318 bool &UsedAssumedInformation);
2319
2320 /// Check \p Pred on all call sites of \p Fn.
2321 ///
2322 /// This method will evaluate \p Pred on call sites and return
2323 /// true if \p Pred holds in every call sites. However, this is only possible
2324 /// all call sites are known, hence the function has internal linkage.
2325 /// If true is returned, \p UsedAssumedInformation is set if assumed
2326 /// information was used to skip or simplify potential call sites.
2328 const Function &Fn, bool RequireAllCallSites,
2329 const AbstractAttribute *QueryingAA,
2330 bool &UsedAssumedInformation,
2331 bool CheckPotentiallyDead = false);
2332
2333 /// Check \p Pred on all values potentially returned by the function
2334 /// associated with \p QueryingAA.
2335 ///
2336 /// This is the context insensitive version of the method above.
2337 bool
2339 const AbstractAttribute &QueryingAA,
2341 bool RecurseForSelectAndPHI = true);
2342
2343 /// Check \p Pred on all instructions in \p Fn with an opcode present in
2344 /// \p Opcodes.
2345 ///
2346 /// This method will evaluate \p Pred on all instructions with an opcode
2347 /// present in \p Opcode and return true if \p Pred holds on all of them.
2349 const Function *Fn,
2350 const AbstractAttribute *QueryingAA,
2351 ArrayRef<unsigned> Opcodes,
2352 bool &UsedAssumedInformation,
2353 bool CheckBBLivenessOnly = false,
2354 bool CheckPotentiallyDead = false);
2355
2356 /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
2357 ///
2358 /// This method will evaluate \p Pred on all instructions with an opcode
2359 /// present in \p Opcode and return true if \p Pred holds on all of them.
2361 const AbstractAttribute &QueryingAA,
2362 ArrayRef<unsigned> Opcodes,
2363 bool &UsedAssumedInformation,
2364 bool CheckBBLivenessOnly = false,
2365 bool CheckPotentiallyDead = false);
2366
2367 /// Check \p Pred on all call-like instructions (=CallBased derived).
2368 ///
2369 /// See checkForAllCallLikeInstructions(...) for more information.
2371 const AbstractAttribute &QueryingAA,
2372 bool &UsedAssumedInformation,
2373 bool CheckBBLivenessOnly = false,
2374 bool CheckPotentiallyDead = false) {
2376 Pred, QueryingAA,
2377 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2378 (unsigned)Instruction::Call},
2379 UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead);
2380 }
2381
2382 /// Check \p Pred on all Read/Write instructions.
2383 ///
2384 /// This method will evaluate \p Pred on all instructions that read or write
2385 /// to memory present in the information cache and return true if \p Pred
2386 /// holds on all of them.
2388 AbstractAttribute &QueryingAA,
2389 bool &UsedAssumedInformation);
2390
2391 /// Create a shallow wrapper for \p F such that \p F has internal linkage
2392 /// afterwards. It also sets the original \p F 's name to anonymous
2393 ///
2394 /// A wrapper is a function with the same type (and attributes) as \p F
2395 /// that will only call \p F and return the result, if any.
2396 ///
2397 /// Assuming the declaration of looks like:
2398 /// rty F(aty0 arg0, ..., atyN argN);
2399 ///
2400 /// The wrapper will then look as follows:
2401 /// rty wrapper(aty0 arg0, ..., atyN argN) {
2402 /// return F(arg0, ..., argN);
2403 /// }
2404 ///
2405 static void createShallowWrapper(Function &F);
2406
2407 /// Returns true if the function \p F can be internalized. i.e. it has a
2408 /// compatible linkage.
2409 static bool isInternalizable(Function &F);
2410
2411 /// Make another copy of the function \p F such that the copied version has
2412 /// internal linkage afterwards and can be analysed. Then we replace all uses
2413 /// of the original function to the copied one
2414 ///
2415 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2416 /// linkage can be internalized because these linkages guarantee that other
2417 /// definitions with the same name have the same semantics as this one.
2418 ///
2419 /// This will only be run if the `attributor-allow-deep-wrappers` option is
2420 /// set, or if the function is called with \p Force set to true.
2421 ///
2422 /// If the function \p F failed to be internalized the return value will be a
2423 /// null pointer.
2424 static Function *internalizeFunction(Function &F, bool Force = false);
2425
2426 /// Make copies of each function in the set \p FnSet such that the copied
2427 /// version has internal linkage afterwards and can be analysed. Then we
2428 /// replace all uses of the original function to the copied one. The map
2429 /// \p FnMap contains a mapping of functions to their internalized versions.
2430 ///
2431 /// Only non-locally linked functions that have `linkonce_odr` or `weak_odr`
2432 /// linkage can be internalized because these linkages guarantee that other
2433 /// definitions with the same name have the same semantics as this one.
2434 ///
2435 /// This version will internalize all the functions in the set \p FnSet at
2436 /// once and then replace the uses. This prevents internalized functions being
2437 /// called by external functions when there is an internalized version in the
2438 /// module.
2441
2442 /// Return the data layout associated with the anchor scope.
2443 const DataLayout &getDataLayout() const { return InfoCache.DL; }
2444
2445 /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
2447
2449 return CGModifiedFunctions;
2450 }
2451
2452private:
2453 /// This method will do fixpoint iteration until fixpoint or the
2454 /// maximum iteration count is reached.
2455 ///
2456 /// If the maximum iteration count is reached, This method will
2457 /// indicate pessimistic fixpoint on attributes that transitively depend
2458 /// on attributes that were scheduled for an update.
2459 void runTillFixpoint();
2460
2461 /// Gets called after scheduling, manifests attributes to the LLVM IR.
2462 ChangeStatus manifestAttributes();
2463
2464 /// Gets called after attributes have been manifested, cleans up the IR.
2465 /// Deletes dead functions, blocks and instructions.
2466 /// Rewrites function signitures and updates the call graph.
2467 ChangeStatus cleanupIR();
2468
2469 /// Identify internal functions that are effectively dead, thus not reachable
2470 /// from a live entry point. The functions are added to ToBeDeletedFunctions.
2471 void identifyDeadInternalFunctions();
2472
2473 /// Run `::update` on \p AA and track the dependences queried while doing so.
2474 /// Also adjust the state if we know further updates are not necessary.
2475 ChangeStatus updateAA(AbstractAttribute &AA);
2476
2477 /// Remember the dependences on the top of the dependence stack such that they
2478 /// may trigger further updates. (\see DependenceStack)
2479 void rememberDependences();
2480
2481 /// Determine if CallBase context in \p IRP should be propagated.
2482 bool shouldPropagateCallBaseContext(const IRPosition &IRP);
2483
2484 /// Apply all requested function signature rewrites
2485 /// (\see registerFunctionSignatureRewrite) and return Changed if the module
2486 /// was altered.
2488 rewriteFunctionSignatures(SmallSetVector<Function *, 8> &ModifiedFns);
2489
2490 /// Check if the Attribute \p AA should be seeded.
2491 /// See getOrCreateAAFor.
2492 bool shouldSeedAttribute(AbstractAttribute &AA);
2493
2494 /// A nested map to lookup abstract attributes based on the argument position
2495 /// on the outer level, and the addresses of the static member (AAType::ID) on
2496 /// the inner level.
2497 ///{
2498 using AAMapKeyTy = std::pair<const char *, IRPosition>;
2500 ///}
2501
2502 /// Map to remember all requested signature changes (= argument replacements).
2504 ArgumentReplacementMap;
2505
2506 /// The set of functions we are deriving attributes for.
2507 SetVector<Function *> &Functions;
2508
2509 /// The information cache that holds pre-processed (LLVM-IR) information.
2510 InformationCache &InfoCache;
2511
2512 /// Abstract Attribute dependency graph
2513 AADepGraph DG;
2514
2515 /// Set of functions for which we modified the content such that it might
2516 /// impact the call graph.
2517 SmallSetVector<Function *, 8> CGModifiedFunctions;
2518
2519 /// Information about a dependence. If FromAA is changed ToAA needs to be
2520 /// updated as well.
2521 struct DepInfo {
2522 const AbstractAttribute *FromAA;
2523 const AbstractAttribute *ToAA;
2524 DepClassTy DepClass;
2525 };
2526
2527 /// The dependence stack is used to track dependences during an
2528 /// `AbstractAttribute::update` call. As `AbstractAttribute::update` can be
2529 /// recursive we might have multiple vectors of dependences in here. The stack
2530 /// size, should be adjusted according to the expected recursion depth and the
2531 /// inner dependence vector size to the expected number of dependences per
2532 /// abstract attribute. Since the inner vectors are actually allocated on the
2533 /// stack we can be generous with their size.
2534 using DependenceVector = SmallVector<DepInfo, 8>;
2535 SmallVector<DependenceVector *, 16> DependenceStack;
2536
2537 /// A set to remember the functions we already assume to be live and visited.
2538 DenseSet<const Function *> VisitedFunctions;
2539
2540 /// Uses we replace with a new value after manifest is done. We will remove
2541 /// then trivially dead instructions as well.
2542 SmallMapVector<Use *, Value *, 32> ToBeChangedUses;
2543
2544 /// Values we replace with a new value after manifest is done. We will remove
2545 /// then trivially dead instructions as well.
2546 SmallMapVector<Value *, PointerIntPair<Value *, 1, bool>, 32>
2547 ToBeChangedValues;
2548
2549 /// Instructions we replace with `unreachable` insts after manifest is done.
2550 SmallSetVector<WeakVH, 16> ToBeChangedToUnreachableInsts;
2551
2552 /// Invoke instructions with at least a single dead successor block.
2553 SmallSetVector<WeakVH, 16> InvokeWithDeadSuccessor;
2554
2555 /// A flag that indicates which stage of the process we are in. Initially, the
2556 /// phase is SEEDING. Phase is changed in `Attributor::run()`
2557 enum class AttributorPhase {
2558 SEEDING,
2559 UPDATE,
2560 MANIFEST,
2561 CLEANUP,
2562 } Phase = AttributorPhase::SEEDING;
2563
2564 /// The current initialization chain length. Tracked to avoid stack overflows.
2565 unsigned InitializationChainLength = 0;
2566
2567 /// Functions, blocks, and instructions we delete after manifest is done.
2568 ///
2569 ///{
2570 SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks;
2571 SmallSetVector<Function *, 8> ToBeDeletedFunctions;
2572 SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks;
2573 SmallSetVector<WeakVH, 8> ToBeDeletedInsts;
2574 ///}
2575
2576 /// Container with all the query AAs that requested an update via
2577 /// registerForUpdate.
2578 SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate;
2579
2580 /// User provided configuration for this Attributor instance.
2581 const AttributorConfig Configuration;
2582
2583 friend AADepGraph;
2584 friend AttributorCallGraph;
2585};
2586
2587/// An interface to query the internal state of an abstract attribute.
2588///
2589/// The abstract state is a minimal interface that allows the Attributor to
2590/// communicate with the abstract attributes about their internal state without
2591/// enforcing or exposing implementation details, e.g., the (existence of an)
2592/// underlying lattice.
2593///
2594/// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
2595/// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
2596/// was reached or (4) a pessimistic fixpoint was enforced.
2597///
2598/// All methods need to be implemented by the subclass. For the common use case,
2599/// a single boolean state or a bit-encoded state, the BooleanState and
2600/// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract
2601/// attribute can inherit from them to get the abstract state interface and
2602/// additional methods to directly modify the state based if needed. See the
2603/// class comments for help.
2605 virtual ~AbstractState() = default;
2606
2607 /// Return if this abstract state is in a valid state. If false, no
2608 /// information provided should be used.
2609 virtual bool isValidState() const = 0;
2610
2611 /// Return if this abstract state is fixed, thus does not need to be updated
2612 /// if information changes as it cannot change itself.
2613 virtual bool isAtFixpoint() const = 0;
2614
2615 /// Indicate that the abstract state should converge to the optimistic state.
2616 ///
2617 /// This will usually make the optimistically assumed state the known to be
2618 /// true state.
2619 ///
2620 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
2622
2623 /// Indicate that the abstract state should converge to the pessimistic state.
2624 ///
2625 /// This will usually revert the optimistically assumed state to the known to
2626 /// be true state.
2627 ///
2628 /// \returns ChangeStatus::CHANGED as the assumed value may change.
2630};
2631
2632/// Simple state with integers encoding.
2633///
2634/// The interface ensures that the assumed bits are always a subset of the known
2635/// bits. Users can only add known bits and, except through adding known bits,
2636/// they can only remove assumed bits. This should guarantee monotonicity and
2637/// thereby the existence of a fixpoint (if used correctly). The fixpoint is
2638/// reached when the assumed and known state/bits are equal. Users can
2639/// force/inidicate a fixpoint. If an optimistic one is indicated, the known
2640/// state will catch up with the assumed one, for a pessimistic fixpoint it is
2641/// the other way around.
2642template <typename base_ty, base_ty BestState, base_ty WorstState>
2644 using base_t = base_ty;
2645
2646 IntegerStateBase() = default;
2648
2649 /// Return the best possible representable state.
2650 static constexpr base_t getBestState() { return BestState; }
2651 static constexpr base_t getBestState(const IntegerStateBase &) {
2652 return getBestState();
2653 }
2654
2655 /// Return the worst possible representable state.
2656 static constexpr base_t getWorstState() { return WorstState; }
2657 static constexpr base_t getWorstState(const IntegerStateBase &) {
2658 return getWorstState();
2659 }
2660
2661 /// See AbstractState::isValidState()
2662 /// NOTE: For now we simply pretend that the worst possible state is invalid.
2663 bool isValidState() const override { return Assumed != getWorstState(); }
2664
2665 /// See AbstractState::isAtFixpoint()
2666 bool isAtFixpoint() const override { return Assumed == Known; }
2667
2668 /// See AbstractState::indicateOptimisticFixpoint(...)
2670 Known = Assumed;
2672 }
2673
2674 /// See AbstractState::indicatePessimisticFixpoint(...)
2676 Assumed = Known;
2677 return ChangeStatus::CHANGED;
2678 }
2679
2680 /// Return the known state encoding
2681 base_t getKnown() const { return Known; }
2682
2683 /// Return the assumed state encoding.
2684 base_t getAssumed() const { return Assumed; }
2685
2686 /// Equality for IntegerStateBase.
2687 bool
2689 return this->getAssumed() == R.getAssumed() &&
2690 this->getKnown() == R.getKnown();
2691 }
2692
2693 /// Inequality for IntegerStateBase.
2694 bool
2696 return !(*this == R);
2697 }
2698
2699 /// "Clamp" this state with \p R. The result is subtype dependent but it is
2700 /// intended that only information assumed in both states will be assumed in
2701 /// this one afterwards.
2703 handleNewAssumedValue(R.getAssumed());
2704 }
2705
2706 /// "Clamp" this state with \p R. The result is subtype dependent but it is
2707 /// intended that information known in either state will be known in
2708 /// this one afterwards.
2710 handleNewKnownValue(R.getKnown());
2711 }
2712
2714 joinOR(R.getAssumed(), R.getKnown());
2715 }
2716
2718 joinAND(R.getAssumed(), R.getKnown());
2719 }
2720
2721protected:
2722 /// Handle a new assumed value \p Value. Subtype dependent.
2724
2725 /// Handle a new known value \p Value. Subtype dependent.
2727
2728 /// Handle a value \p Value. Subtype dependent.
2729 virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0;
2730
2731 /// Handle a new assumed value \p Value. Subtype dependent.
2732 virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0;
2733
2734 /// The known state encoding in an integer of type base_t.
2736
2737 /// The assumed state encoding in an integer of type base_t.
2739};
2740
2741/// Specialization of the integer state for a bit-wise encoding.
2742template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2743 base_ty WorstState = 0>
2745 : public IntegerStateBase<base_ty, BestState, WorstState> {
2747 using base_t = base_ty;
2748 BitIntegerState() = default;
2750
2751 /// Return true if the bits set in \p BitsEncoding are "known bits".
2752 bool isKnown(base_t BitsEncoding = BestState) const {
2753 return (this->Known & BitsEncoding) == BitsEncoding;
2754 }
2755
2756 /// Return true if the bits set in \p BitsEncoding are "assumed bits".
2757 bool isAssumed(base_t BitsEncoding = BestState) const {
2758 return (this->Assumed & BitsEncoding) == BitsEncoding;
2759 }
2760
2761 /// Add the bits in \p BitsEncoding to the "known bits".
2763 // Make sure we never miss any "known bits".
2764 this->Assumed |= Bits;
2765 this->Known |= Bits;
2766 return *this;
2767 }
2768
2769 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
2771 return intersectAssumedBits(~BitsEncoding);
2772 }
2773
2774 /// Remove the bits in \p BitsEncoding from the "known bits".
2776 this->Known = (this->Known & ~BitsEncoding);
2777 return *this;
2778 }
2779
2780 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
2782 // Make sure we never lose any "known bits".
2783 this->Assumed = (this->Assumed & BitsEncoding) | this->Known;
2784 return *this;
2785 }
2786
2787private:
2788 void handleNewAssumedValue(base_t Value) override {
2790 }
2791 void handleNewKnownValue(base_t Value) override { addKnownBits(Value); }
2792 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2793 this->Known |= KnownValue;
2794 this->Assumed |= AssumedValue;
2795 }
2796 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2797 this->Known &= KnownValue;
2798 this->Assumed &= AssumedValue;
2799 }
2800};
2801
2802/// Specialization of the integer state for an increasing value, hence ~0u is
2803/// the best state and 0 the worst.
2804template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0),
2805 base_ty WorstState = 0>
2807 : public IntegerStateBase<base_ty, BestState, WorstState> {
2809 using base_t = base_ty;
2810
2813
2814 /// Return the best possible representable state.
2815 static constexpr base_t getBestState() { return BestState; }
2816 static constexpr base_t
2818 return getBestState();
2819 }
2820
2821 /// Take minimum of assumed and \p Value.
2823 // Make sure we never lose "known value".
2824 this->Assumed = std::max(std::min(this->Assumed, Value), this->Known);
2825 return *this;
2826 }
2827
2828 /// Take maximum of known and \p Value.
2830 // Make sure we never lose "known value".
2831 this->Assumed = std::max(Value, this->Assumed);
2832 this->Known = std::max(Value, this->Known);
2833 return *this;
2834 }
2835
2836private:
2837 void handleNewAssumedValue(base_t Value) override {
2839 }
2840 void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); }
2841 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2842 this->Known = std::max(this->Known, KnownValue);
2843 this->Assumed = std::max(this->Assumed, AssumedValue);
2844 }
2845 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2846 this->Known = std::min(this->Known, KnownValue);
2847 this->Assumed = std::min(this->Assumed, AssumedValue);
2848 }
2849};
2850
2851/// Specialization of the integer state for a decreasing value, hence 0 is the
2852/// best state and ~0u the worst.
2853template <typename base_ty = uint32_t>
2854struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> {
2855 using base_t = base_ty;
2856
2857 /// Take maximum of assumed and \p Value.
2859 // Make sure we never lose "known value".
2860 this->Assumed = std::min(std::max(this->Assumed, Value), this->Known);
2861 return *this;
2862 }
2863
2864 /// Take minimum of known and \p Value.
2866 // Make sure we never lose "known value".
2867 this->Assumed = std::min(Value, this->Assumed);
2868 this->Known = std::min(Value, this->Known);
2869 return *this;
2870 }
2871
2872private:
2873 void handleNewAssumedValue(base_t Value) override {
2875 }
2876 void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); }
2877 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2878 this->Assumed = std::min(this->Assumed, KnownValue);
2879 this->Assumed = std::min(this->Assumed, AssumedValue);
2880 }
2881 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2882 this->Assumed = std::max(this->Assumed, KnownValue);
2883 this->Assumed = std::max(this->Assumed, AssumedValue);
2884 }
2885};
2886
2887/// Simple wrapper for a single bit (boolean) state.
2888struct BooleanState : public IntegerStateBase<bool, true, false> {
2891
2892 BooleanState() = default;
2894
2895 /// Set the assumed value to \p Value but never below the known one.
2896 void setAssumed(bool Value) { Assumed &= (Known | Value); }
2897
2898 /// Set the known and asssumed value to \p Value.
2899 void setKnown(bool Value) {
2900 Known |= Value;
2901 Assumed |= Value;
2902 }
2903
2904 /// Return true if the state is assumed to hold.
2905 bool isAssumed() const { return getAssumed(); }
2906
2907 /// Return true if the state is known to hold.
2908 bool isKnown() const { return getKnown(); }
2909
2910private:
2911 void handleNewAssumedValue(base_t Value) override {
2912 if (!Value)
2913 Assumed = Known;
2914 }
2915 void handleNewKnownValue(base_t Value) override {
2916 if (Value)
2917 Known = (Assumed = Value);
2918 }
2919 void joinOR(base_t AssumedValue, base_t KnownValue) override {
2920 Known |= KnownValue;
2921 Assumed |= AssumedValue;
2922 }
2923 void joinAND(base_t AssumedValue, base_t KnownValue) override {
2924 Known &= KnownValue;
2925 Assumed &= AssumedValue;
2926 }
2927};
2928
2929/// State for an integer range.
2931
2932 /// Bitwidth of the associated value.
2934
2935 /// State representing assumed range, initially set to empty.
2937
2938 /// State representing known range, initially set to [-inf, inf].
2940
2943 Known(ConstantRange::getFull(BitWidth)) {}
2944
2946 : BitWidth(CR.getBitWidth()), Assumed(CR),
2948
2949 /// Return the worst possible representable state.
2951 return ConstantRange::getFull(BitWidth);
2952 }
2953
2954 /// Return the best possible representable state.
2956 return ConstantRange::getEmpty(BitWidth);
2957 }
2959 return getBestState(IRS.getBitWidth());
2960 }
2961
2962 /// Return associated values' bit width.
2963 uint32_t getBitWidth() const { return BitWidth; }
2964
2965 /// See AbstractState::isValidState()
2966 bool isValidState() const override {
2967 return BitWidth > 0 && !Assumed.isFullSet();
2968 }
2969
2970 /// See AbstractState::isAtFixpoint()
2971 bool isAtFixpoint() const override { return Assumed == Known; }
2972
2973 /// See AbstractState::indicateOptimisticFixpoint(...)
2975 Known = Assumed;
2976 return ChangeStatus::CHANGED;
2977 }
2978
2979 /// See AbstractState::indicatePessimisticFixpoint(...)
2981 Assumed = Known;
2982 return ChangeStatus::CHANGED;
2983 }
2984
2985 /// Return the known state encoding
2986 ConstantRange getKnown() const { return Known; }
2987
2988 /// Return the assumed state encoding.
2990
2991 /// Unite assumed range with the passed state.
2993 // Don't lose a known range.
2995 }
2996
2997 /// See IntegerRangeState::unionAssumed(..).
2999 unionAssumed(R.getAssumed());
3000 }
3001
3002 /// Intersect known range with the passed state.
3006 }
3007
3008 /// See IntegerRangeState::intersectKnown(..).
3010 intersectKnown(R.getKnown());
3011 }
3012
3013 /// Equality for IntegerRangeState.
3014 bool operator==(const IntegerRangeState &R) const {
3015 return getAssumed() == R.getAssumed() && getKnown() == R.getKnown();
3016 }
3017
3018 /// "Clamp" this state with \p R. The result is subtype dependent but it is
3019 /// intended that only information assumed in both states will be assumed in
3020 /// this one afterwards.
3022 // NOTE: `^=` operator seems like `intersect` but in this case, we need to
3023 // take `union`.
3024 unionAssumed(R);
3025 return *this;
3026 }
3027
3029 // NOTE: `&=` operator seems like `intersect` but in this case, we need to
3030 // take `union`.
3031 Known = Known.unionWith(R.getKnown());
3032 Assumed = Assumed.unionWith(R.getAssumed());
3033 return *this;
3034 }
3035};
3036
3037/// Simple state for a set.
3038///
3039/// This represents a state containing a set of values. The interface supports
3040/// modelling sets that contain all possible elements. The state's internal
3041/// value is modified using union or intersection operations.
3042template <typename BaseTy> struct SetState : public AbstractState {
3043 /// A wrapper around a set that has semantics for handling unions and
3044 /// intersections with a "universal" set that contains all elements.
3046 /// Creates a universal set with no concrete elements or an empty set.
3047 SetContents(bool Universal) : Universal(Universal) {}
3048
3049 /// Creates a non-universal set with concrete values.
3050 SetContents(const DenseSet<BaseTy> &Assumptions)
3051 : Universal(false), Set(Assumptions) {}
3052
3053 SetContents(bool Universal, const DenseSet<BaseTy> &Assumptions)
3054 : Universal(Universal), Set(Assumptions) {}
3055
3056 const DenseSet<BaseTy> &getSet() const { return Set; }
3057
3058 bool isUniversal() const { return Universal; }
3059
3060 bool empty() const { return Set.empty() && !Universal; }
3061
3062 /// Finds A := A ^ B where A or B could be the "Universal" set which
3063 /// contains every possible attribute. Returns true if changes were made.
3065 bool IsUniversal = Universal;
3066 unsigned Size = Set.size();
3067
3068 // A := A ^ U = A
3069 if (RHS.isUniversal())
3070 return false;
3071
3072 // A := U ^ B = B
3073 if (Universal)
3074 Set = RHS.getSet();
3075 else
3076 set_intersect(Set, RHS.getSet());
3077
3078 Universal &= RHS.isUniversal();
3079 return IsUniversal != Universal || Size != Set.size();
3080 }
3081
3082 /// Finds A := A u B where A or B could be the "Universal" set which
3083 /// contains every possible attribute. returns true if changes were made.
3084 bool getUnion(const SetContents &RHS) {
3085 bool IsUniversal = Universal;
3086 unsigned Size = Set.size();
3087
3088 // A := A u U = U = U u B
3089 if (!RHS.isUniversal() && !Universal)
3090 set_union(Set, RHS.getSet());
3091
3092 Universal |= RHS.isUniversal();
3093 return IsUniversal != Universal || Size != Set.size();
3094 }
3095
3096 private:
3097 /// Indicates if this set is "universal", containing every possible element.
3098 bool Universal;
3099
3100 /// The set of currently active assumptions.
3101 DenseSet<BaseTy> Set;
3102 };
3103
3104 SetState() : Known(false), Assumed(true), IsAtFixedpoint(false) {}
3105
3106 /// Initializes the known state with an initial set and initializes the
3107 /// assumed state as universal.
3109 : Known(Known), Assumed(true), IsAtFixedpoint(false) {}
3110
3111 /// See AbstractState::isValidState()
3112 bool isValidState() const override { return !Assumed.empty(); }
3113
3114 /// See AbstractState::isAtFixpoint()
3115 bool isAtFixpoint() const override { return IsAtFixedpoint; }
3116
3117 /// See AbstractState::indicateOptimisticFixpoint(...)
3119 IsAtFixedpoint = true;
3120 Known = Assumed;
3122 }
3123
3124 /// See AbstractState::indicatePessimisticFixpoint(...)
3126 IsAtFixedpoint = true;
3127 Assumed = Known;
3128 return ChangeStatus::CHANGED;
3129 }
3130
3131 /// Return the known state encoding.
3132 const SetContents &getKnown() const { return Known; }
3133
3134 /// Return the assumed state encoding.
3135 const SetContents &getAssumed() const { return Assumed; }
3136
3137 /// Returns if the set state contains the element.
3138 bool setContains(const BaseTy &Elem) const {
3139 return Assumed.getSet().contains(Elem) || Known.getSet().contains(Elem);
3140 }
3141
3142 /// Performs the set intersection between this set and \p RHS. Returns true if
3143 /// changes were made.
3145 bool IsUniversal = Assumed.isUniversal();
3146 unsigned SizeBefore = Assumed.getSet().size();
3147
3148 // Get intersection and make sure that the known set is still a proper
3149 // subset of the assumed set. A := K u (A ^ R).
3150 Assumed.getIntersection(RHS);
3151 Assumed.getUnion(Known);
3152
3153 return SizeBefore != Assumed.getSet().size() ||
3154 IsUniversal != Assumed.isUniversal();
3155 }
3156
3157 /// Performs the set union between this set and \p RHS. Returns true if
3158 /// changes were made.
3159 bool getUnion(const SetContents &RHS) { return Assumed.getUnion(RHS); }
3160
3161private:
3162 /// The set of values known for this state.
3163 SetContents Known;
3164
3165 /// The set of assumed values for this state.
3166 SetContents Assumed;
3167
3168 bool IsAtFixedpoint;
3169};
3170
3171/// Helper to tie a abstract state implementation to an abstract attribute.
3172template <typename StateTy, typename BaseType, class... Ts>
3173struct StateWrapper : public BaseType, public StateTy {
3174 /// Provide static access to the type of the state.
3176
3177 StateWrapper(const IRPosition &IRP, Ts... Args)
3178 : BaseType(IRP), StateTy(Args...) {}
3179
3180 /// See AbstractAttribute::getState(...).
3181 StateType &getState() override { return *this; }
3182
3183 /// See AbstractAttribute::getState(...).
3184 const StateType &getState() const override { return *this; }
3185};
3186
3187/// Helper class that provides common functionality to manifest IR attributes.
3188template <Attribute::AttrKind AK, typename BaseType, typename AAType>
3189struct IRAttribute : public BaseType {
3190 IRAttribute(const IRPosition &IRP) : BaseType(IRP) {}
3191
3192 /// Most boolean IRAttribute AAs don't do anything non-trivial
3193 /// in their initializers while non-boolean ones often do. Subclasses can
3194 /// change this.
3196
3197 /// Compile time access to the IR attribute kind.
3199
3200 /// Return true if the IR attribute(s) associated with this AA are implied for
3201 /// an undef value.
3202 static bool isImpliedByUndef() { return true; }
3203
3204 /// Return true if the IR attribute(s) associated with this AA are implied for
3205 /// an poison value.
3206 static bool isImpliedByPoison() { return true; }
3207
3208 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3209 Attribute::AttrKind ImpliedAttributeKind = AK,
3210 bool IgnoreSubsumingPositions = false) {
3211 if (AAType::isImpliedByUndef() && isa<UndefValue>(IRP.getAssociatedValue()))
3212 return true;
3213 if (AAType::isImpliedByPoison() &&
3214 isa<PoisonValue>(IRP.getAssociatedValue()))
3215 return true;
3216 return A.hasAttr(IRP, {ImpliedAttributeKind}, IgnoreSubsumingPositions,
3217 ImpliedAttributeKind);
3218 }
3219
3220 /// See AbstractAttribute::manifest(...).
3222 if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
3224 SmallVector<Attribute, 4> DeducedAttrs;
3225 getDeducedAttributes(A, this->getAnchorValue().getContext(), DeducedAttrs);
3226 if (DeducedAttrs.empty())
3228 return A.manifestAttrs(this->getIRPosition(), DeducedAttrs);
3229 }
3230
3231 /// Return the kind that identifies the abstract attribute implementation.
3232 Attribute::AttrKind getAttrKind() const { return AK; }
3233
3234 /// Return the deduced attributes in \p Attrs.
3236 SmallVectorImpl<Attribute> &Attrs) const {
3237 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
3238 }
3239};
3240
3241/// Base struct for all "concrete attribute" deductions.
3242///
3243/// The abstract attribute is a minimal interface that allows the Attributor to
3244/// orchestrate the abstract/fixpoint analysis. The design allows to hide away
3245/// implementation choices made for the subclasses but also to structure their
3246/// implementation and simplify the use of other abstract attributes in-flight.
3247///
3248/// To allow easy creation of new attributes, most methods have default
3249/// implementations. The ones that do not are generally straight forward, except
3250/// `AbstractAttribute::updateImpl` which is the location of most reasoning
3251/// associated with the abstract attribute. The update is invoked by the
3252/// Attributor in case the situation used to justify the current optimistic
3253/// state might have changed. The Attributor determines this automatically
3254/// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
3255///
3256/// The `updateImpl` method should inspect the IR and other abstract attributes
3257/// in-flight to justify the best possible (=optimistic) state. The actual
3258/// implementation is, similar to the underlying abstract state encoding, not
3259/// exposed. In the most common case, the `updateImpl` will go through a list of
3260/// reasons why its optimistic state is valid given the current information. If
3261/// any combination of them holds and is sufficient to justify the current
3262/// optimistic state, the method shall return UNCHAGED. If not, the optimistic
3263/// state is adjusted to the situation and the method shall return CHANGED.
3264///
3265/// If the manifestation of the "concrete attribute" deduced by the subclass
3266/// differs from the "default" behavior, which is a (set of) LLVM-IR
3267/// attribute(s) for an argument, call site argument, function return value, or
3268/// function, the `AbstractAttribute::manifest` method should be overloaded.
3269///
3270/// NOTE: If the state obtained via getState() is INVALID, thus if
3271/// AbstractAttribute::getState().isValidState() returns false, no
3272/// information provided by the methods of this class should be used.
3273/// NOTE: The Attributor currently has certain limitations to what we can do.
3274/// As a general rule of thumb, "concrete" abstract attributes should *for
3275/// now* only perform "backward" information propagation. That means
3276/// optimistic information obtained through abstract attributes should
3277/// only be used at positions that precede the origin of the information
3278/// with regards to the program flow. More practically, information can
3279/// *now* be propagated from instructions to their enclosing function, but
3280/// *not* from call sites to the called function. The mechanisms to allow
3281/// both directions will be added in the future.
3282/// NOTE: The mechanics of adding a new "concrete" abstract attribute are
3283/// described in the file comment.
3286
3288
3289 /// Virtual destructor.
3290 virtual ~AbstractAttribute() = default;
3291
3292 /// Compile time access to the IR attribute kind.
3294
3295 /// This function is used to identify if an \p DGN is of type
3296 /// AbstractAttribute so that the dyn_cast and cast can use such information
3297 /// to cast an AADepGraphNode to an AbstractAttribute.
3298 ///
3299 /// We eagerly return true here because all AADepGraphNodes except for the
3300 /// Synthethis Node are of type AbstractAttribute
3301 static bool classof(const AADepGraphNode *DGN) { return true; }
3302
3303 /// Return false if this AA does anything non-trivial (hence not done by
3304 /// default) in its initializer.
3305 static bool hasTrivialInitializer() { return false; }
3306
3307 /// Return true if this AA requires a "callee" (or an associted function) for
3308 /// a call site positon. Default is optimistic to minimize AAs.
3309 static bool requiresCalleeForCallBase() { return false; }
3310
3311 /// Return true if this AA requires non-asm "callee" for a call site positon.
3312 static bool requiresNonAsmForCallBase() { return true; }
3313
3314 /// Return true if this AA requires all callees for an argument or function
3315 /// positon.
3316 static bool requiresCallersForArgOrFunction() { return false; }
3317
3318 /// Return false if an AA should not be created for \p IRP.
3320 return true;
3321 }
3322
3323 /// Return false if an AA should not be updated for \p IRP.
3325 Function *AssociatedFn = IRP.getAssociatedFunction();
3326 bool IsFnInterface = IRP.isFnInterfaceKind();
3327 assert((!IsFnInterface || AssociatedFn) &&
3328 "Function interface without a function?");
3329
3330 // TODO: Not all attributes require an exact definition. Find a way to
3331 // enable deduction for some but not all attributes in case the
3332 // definition might be changed at runtime, see also
3333 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
3334 // TODO: We could always determine abstract attributes and if sufficient
3335 // information was found we could duplicate the functions that do not
3336 // have an exact definition.
3337 return !IsFnInterface || A.isFunctionIPOAmendable(*AssociatedFn);
3338 }
3339
3340 /// Initialize the state with the information in the Attributor \p A.
3341 ///
3342 /// This function is called by the Attributor once all abstract attributes
3343 /// have been identified. It can and shall be used for task like:
3344 /// - identify existing knowledge in the IR and use it for the "known state"
3345 /// - perform any work that is not going to change over time, e.g., determine
3346 /// a subset of the IR, or attributes in-flight, that have to be looked at
3347 /// in the `updateImpl` method.
3348 virtual void initialize(Attributor &A) {}
3349
3350 /// A query AA is always scheduled as long as we do updates because it does
3351 /// lazy computation that cannot be determined to be done from the outside.
3352 /// However, while query AAs will not be fixed if they do not have outstanding
3353 /// dependences, we will only schedule them like other AAs. If a query AA that
3354 /// received a new query it needs to request an update via
3355 /// `Attributor::requestUpdateForAA`.
3356 virtual bool isQueryAA() const { return false; }
3357
3358 /// Return the internal abstract state for inspection.
3359 virtual StateType &getState() = 0;
3360 virtual const StateType &getState() const = 0;
3361
3362 /// Return an IR position, see struct IRPosition.
3363 const IRPosition &getIRPosition() const { return *this; };
3364 IRPosition &getIRPosition() { return *this; };
3365
3366 /// Helper functions, for debug purposes only.
3367 ///{
3368 void print(raw_ostream &OS) const { print(nullptr, OS); }
3369 void print(Attributor *, raw_ostream &OS) const override;
3370 virtual void printWithDeps(raw_ostream &OS) const;
3371 void dump() const { this->print(dbgs()); }
3372
3373 /// This function should return the "summarized" assumed state as string.
3374 virtual const std::string getAsStr(Attributor *A) const = 0;
3375
3376 /// This function should return the name of the AbstractAttribute
3377 virtual const std::string getName() const = 0;
3378
3379 /// This function should return the address of the ID of the AbstractAttribute
3380 virtual const char *getIdAddr() const = 0;
3381 ///}
3382
3383 /// Allow the Attributor access to the protected methods.
3384 friend struct Attributor;
3385
3386protected:
3387 /// Hook for the Attributor to trigger an update of the internal state.
3388 ///
3389 /// If this attribute is already fixed, this method will return UNCHANGED,
3390 /// otherwise it delegates to `AbstractAttribute::updateImpl`.
3391 ///
3392 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3394
3395 /// Hook for the Attributor to trigger the manifestation of the information
3396 /// represented by the abstract attribute in the LLVM-IR.
3397 ///
3398 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
3401 }
3402
3403 /// Hook to enable custom statistic tracking, called after manifest that
3404 /// resulted in a change if statistics are enabled.
3405 ///
3406 /// We require subclasses to provide an implementation so we remember to
3407 /// add statistics for them.
3408 virtual void trackStatistics() const = 0;
3409
3410 /// The actual update/transfer function which has to be implemented by the
3411 /// derived classes.
3412 ///
3413 /// If it is called, the environment has changed and we have to determine if
3414 /// the current information is still valid or adjust it otherwise.
3415 ///
3416 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
3418};
3419
3420/// Forward declarations of output streams for debug purposes.
3421///
3422///{
3428template <typename base_ty, base_ty BestState, base_ty WorstState>
3432 return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
3433 << static_cast<const AbstractState &>(S);
3434}
3435raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State);
3436///}
3437
3438struct AttributorPass : public PassInfoMixin<AttributorPass> {
3440};
3441struct AttributorCGSCCPass : public PassInfoMixin<AttributorCGSCCPass> {
3444};
3445
3446/// A more lightweight version of the Attributor which only runs attribute
3447/// inference but no simplifications.
3448struct AttributorLightPass : public PassInfoMixin<AttributorLightPass> {
3450};
3451
3452/// A more lightweight version of the Attributor which only runs attribute
3453/// inference but no simplifications.
3455 : public PassInfoMixin<AttributorLightCGSCCPass> {
3458};
3459
3460/// Helper function to clamp a state \p S of type \p StateType with the
3461/// information in \p R and indicate/return if \p S did change (as-in update is
3462/// required to be run again).
3463template <typename StateType>
3464ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) {
3465 auto Assumed = S.getAssumed();
3466 S ^= R;
3467 return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
3469}
3470
3471/// ----------------------------------------------------------------------------
3472/// Abstract Attribute Classes
3473/// ----------------------------------------------------------------------------
3474
3476 : public IRAttribute<Attribute::NoUnwind,
3477 StateWrapper<BooleanState, AbstractAttribute>,
3478 AANoUnwind> {
3480
3481 /// Returns true if nounwind is assumed.
3482 bool isAssumedNoUnwind() const { return getAssumed(); }
3483
3484 /// Returns true if nounwind is known.
3485 bool isKnownNoUnwind() const { return getKnown(); }
3486
3487 /// Create an abstract attribute view for the position \p IRP.
3489
3490 /// See AbstractAttribute::getName()
3491 const std::string getName() const override { return "AANoUnwind"; }
3492
3493 /// See AbstractAttribute::getIdAddr()
3494 const char *getIdAddr() const override { return &ID; }
3495
3496 /// This function should return true if the type of the \p AA is AANoUnwind
3497 static bool classof(const AbstractAttribute *AA) {
3498 return (AA->getIdAddr() == &ID);
3499 }
3500
3501 /// Unique ID (due to the unique address)
3502 static const char ID;
3503};
3504
3506 : public IRAttribute<Attribute::NoSync,
3507 StateWrapper<BooleanState, AbstractAttribute>,
3508 AANoSync> {
3510
3511 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3512 Attribute::AttrKind ImpliedAttributeKind,
3513 bool IgnoreSubsumingPositions = false) {
3514 // Note: This is also run for non-IPO amendable functions.
3515 assert(ImpliedAttributeKind == Attribute::NoSync);
3516 if (A.hasAttr(IRP, {Attribute::NoSync}, IgnoreSubsumingPositions,
3517 Attribute::NoSync))
3518 return true;
3519
3520 // Check for readonly + non-convergent.
3521 // TODO: We should be able to use hasAttr for Attributes, not only
3522 // AttrKinds.
3524 if (!F || F->isConvergent())
3525 return false;
3526
3528 A.getAttrs(IRP, {Attribute::Memory}, Attrs, IgnoreSubsumingPositions);
3529
3531 for (const Attribute &Attr : Attrs)
3532 ME &= Attr.getMemoryEffects();
3533
3534 if (!ME.onlyReadsMemory())
3535 return false;
3536
3537 A.manifestAttrs(IRP, Attribute::get(F->getContext(), Attribute::NoSync));
3538 return true;
3539 }
3540
3541 /// See AbstractAttribute::isValidIRPositionForInit
3543 if (!IRP.isFunctionScope() &&
3545 return false;
3546 return IRAttribute::isValidIRPositionForInit(A, IRP);
3547 }
3548
3549 /// Returns true if "nosync" is assumed.
3550 bool isAssumedNoSync() const { return getAssumed(); }
3551
3552 /// Returns true if "nosync" is known.
3553 bool isKnownNoSync() const { return getKnown(); }
3554
3555 /// Helper function used to determine whether an instruction is non-relaxed
3556 /// atomic. In other words, if an atomic instruction does not have unordered
3557 /// or monotonic ordering
3558 static bool isNonRelaxedAtomic(const Instruction *I);
3559
3560 /// Helper function specific for intrinsics which are potentially volatile.
3561 static bool isNoSyncIntrinsic(const Instruction *I);
3562
3563 /// Helper function to determine if \p CB is an aligned (GPU) barrier. Aligned
3564 /// barriers have to be executed by all threads. The flag \p ExecutedAligned
3565 /// indicates if the call is executed by all threads in a (thread) block in an
3566 /// aligned way. If that is the case, non-aligned barriers are effectively
3567 /// aligned barriers.
3568 static bool isAlignedBarrier(const CallBase &CB, bool ExecutedAligned);
3569
3570 /// Create an abstract attribute view for the position \p IRP.
3572
3573 /// See AbstractAttribute::getName()
3574 const std::string getName() const override { return "AANoSync"; }
3575
3576 /// See AbstractAttribute::getIdAddr()
3577 const char *getIdAddr() const override { return &ID; }
3578
3579 /// This function should return true if the type of the \p AA is AANoSync
3580 static bool classof(const AbstractAttribute *AA) {
3581 return (AA->getIdAddr() == &ID);
3582 }
3583
3584 /// Unique ID (due to the unique address)
3585 static const char ID;
3586};
3587
3588/// An abstract interface for all nonnull attributes.
3590 : public IRAttribute<Attribute::MustProgress,
3591 StateWrapper<BooleanState, AbstractAttribute>,
3592 AAMustProgress> {
3594
3595 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3596 Attribute::AttrKind ImpliedAttributeKind,
3597 bool IgnoreSubsumingPositions = false) {
3598 // Note: This is also run for non-IPO amendable functions.
3599 assert(ImpliedAttributeKind == Attribute::MustProgress);
3600 return A.hasAttr(IRP, {Attribute::MustProgress, Attribute::WillReturn},
3601 IgnoreSubsumingPositions, Attribute::MustProgress);
3602 }
3603
3604 /// Return true if we assume that the underlying value is nonnull.
3605 bool isAssumedMustProgress() const { return getAssumed(); }
3606
3607 /// Return true if we know that underlying value is nonnull.
3608 bool isKnownMustProgress() const { return getKnown(); }
3609
3610 /// Create an abstract attribute view for the position \p IRP.
3612 Attributor &A);
3613
3614 /// See AbstractAttribute::getName()
3615 const std::string getName() const override { return "AAMustProgress"; }
3616
3617 /// See AbstractAttribute::getIdAddr()
3618 const char *getIdAddr() const override { return &ID; }
3619
3620 /// This function should return true if the type of the \p AA is
3621 /// AAMustProgress
3622 static bool classof(const AbstractAttribute *AA) {
3623 return (AA->getIdAddr() == &ID);
3624 }
3625
3626 /// Unique ID (due to the unique address)
3627 static const char ID;
3628};
3629
3630/// An abstract interface for all nonnull attributes.
3632 : public IRAttribute<Attribute::NonNull,
3633 StateWrapper<BooleanState, AbstractAttribute>,
3634 AANonNull> {
3636
3637 /// See AbstractAttribute::hasTrivialInitializer.
3638 static bool hasTrivialInitializer() { return false; }
3639
3640 /// See IRAttribute::isImpliedByUndef.
3641 /// Undef is not necessarily nonnull as nonnull + noundef would cause poison.
3642 /// Poison implies nonnull though.
3643 static bool isImpliedByUndef() { return false; }
3644
3645 /// See AbstractAttribute::isValidIRPositionForInit
3648 return false;
3649 return IRAttribute::isValidIRPositionForInit(A, IRP);
3650 }
3651
3652 /// See AbstractAttribute::isImpliedByIR(...).
3653 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3654 Attribute::AttrKind ImpliedAttributeKind,
3655 bool IgnoreSubsumingPositions = false);
3656
3657 /// Return true if we assume that the underlying value is nonnull.
3658 bool isAssumedNonNull() const { return getAssumed(); }
3659
3660 /// Return true if we know that underlying value is nonnull.
3661 bool isKnownNonNull() const { return getKnown(); }
3662
3663 /// Create an abstract attribute view for the position \p IRP.
3665
3666 /// See AbstractAttribute::getName()
3667 const std::string getName() const override { return "AANonNull"; }
3668
3669 /// See AbstractAttribute::getIdAddr()
3670 const char *getIdAddr() const override { return &ID; }
3671
3672 /// This function should return true if the type of the \p AA is AANonNull
3673 static bool classof(const AbstractAttribute *AA) {
3674 return (AA->getIdAddr() == &ID);
3675 }
3676
3677 /// Unique ID (due to the unique address)
3678 static const char ID;
3679};
3680
3681/// An abstract attribute for norecurse.
3683 : public IRAttribute<Attribute::NoRecurse,
3684 StateWrapper<BooleanState, AbstractAttribute>,
3685 AANoRecurse> {
3687
3688 /// Return true if "norecurse" is assumed.
3689 bool isAssumedNoRecurse() const { return getAssumed(); }
3690
3691 /// Return true if "norecurse" is known.
3692 bool isKnownNoRecurse() const { return getKnown(); }
3693
3694 /// Create an abstract attribute view for the position \p IRP.
3696
3697 /// See AbstractAttribute::getName()
3698 const std::string getName() const override { return "AANoRecurse"; }
3699
3700 /// See AbstractAttribute::getIdAddr()
3701 const char *getIdAddr() const override { return &ID; }
3702
3703 /// This function should return true if the type of the \p AA is AANoRecurse
3704 static bool classof(const AbstractAttribute *AA) {
3705 return (AA->getIdAddr() == &ID);
3706 }
3707
3708 /// Unique ID (due to the unique address)
3709 static const char ID;
3710};
3711
3712/// An abstract attribute for willreturn.
3714 : public IRAttribute<Attribute::WillReturn,
3715 StateWrapper<BooleanState, AbstractAttribute>,
3716 AAWillReturn> {
3718
3719 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3720 Attribute::AttrKind ImpliedAttributeKind,
3721 bool IgnoreSubsumingPositions = false) {
3722 // Note: This is also run for non-IPO amendable functions.
3723 assert(ImpliedAttributeKind == Attribute::WillReturn);
3724 if (IRAttribute::isImpliedByIR(A, IRP, ImpliedAttributeKind,
3725 IgnoreSubsumingPositions))
3726 return true;
3728 return false;
3729 A.manifestAttrs(IRP, Attribute::get(IRP.getAnchorValue().getContext(),
3730 Attribute::WillReturn));
3731 return true;
3732 }
3733
3734 /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
3736 const IRPosition &IRP) {
3737 // Check for `mustprogress` in the scope and the associated function which
3738 // might be different if this is a call site.
3739 if (!A.hasAttr(IRP, {Attribute::MustProgress}))
3740 return false;
3741
3743 A.getAttrs(IRP, {Attribute::Memory}, Attrs,
3744 /* IgnoreSubsumingPositions */ false);
3745
3747 for (const Attribute &Attr : Attrs)
3748 ME &= Attr.getMemoryEffects();
3749 return ME.onlyReadsMemory();
3750 }
3751
3752 /// Return true if "willreturn" is assumed.
3753 bool isAssumedWillReturn() const { return getAssumed(); }
3754
3755 /// Return true if "willreturn" is known.
3756 bool isKnownWillReturn() const { return getKnown(); }
3757
3758 /// Create an abstract attribute view for the position \p IRP.
3760
3761 /// See AbstractAttribute::getName()
3762 const std::string getName() const override { return "AAWillReturn"; }
3763
3764 /// See AbstractAttribute::getIdAddr()
3765 const char *getIdAddr() const override { return &ID; }
3766
3767 /// This function should return true if the type of the \p AA is AAWillReturn
3768 static bool classof(const AbstractAttribute *AA) {
3769 return (AA->getIdAddr() == &ID);
3770 }
3771
3772 /// Unique ID (due to the unique address)
3773 static const char ID;
3774};
3775
3776/// An abstract attribute for undefined behavior.
3778 : public StateWrapper<BooleanState, AbstractAttribute> {
3781
3782 /// Return true if "undefined behavior" is assumed.
3783 bool isAssumedToCauseUB() const { return getAssumed(); }
3784
3785 /// Return true if "undefined behavior" is assumed for a specific instruction.
3786 virtual bool isAssumedToCauseUB(Instruction *I) const = 0;
3787
3788 /// Return true if "undefined behavior" is known.
3789 bool isKnownToCauseUB() const { return getKnown(); }
3790
3791 /// Return true if "undefined behavior" is known for a specific instruction.
3792 virtual bool isKnownToCauseUB(Instruction *I) const = 0;
3793
3794 /// Create an abstract attribute view for the position \p IRP.
3796 Attributor &A);
3797
3798 /// See AbstractAttribute::getName()
3799 const std::string getName() const override { return "AAUndefinedBehavior"; }
3800
3801 /// See AbstractAttribute::getIdAddr()
3802 const char *getIdAddr() const override { return &ID; }
3803
3804 /// This function should return true if the type of the \p AA is
3805 /// AAUndefineBehavior
3806 static bool classof(const AbstractAttribute *AA) {
3807 return (AA->getIdAddr() == &ID);
3808 }
3809
3810 /// Unique ID (due to the unique address)
3811 static const char ID;
3812};
3813
3814/// An abstract interface to determine reachability of point A to B.
3816 : public StateWrapper<BooleanState, AbstractAttribute> {
3819
3820 /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
3821 /// Users should provide two positions they are interested in, and the class
3822 /// determines (and caches) reachability.
3824 Attributor &A, const Instruction &From, const Instruction &To,
3825 const AA::InstExclusionSetTy *ExclusionSet = nullptr) const = 0;
3826
3827 /// Create an abstract attribute view for the position \p IRP.
3829 Attributor &A);
3830
3831 /// See AbstractAttribute::getName()
3832 const std::string getName() const override { return "AAIntraFnReachability"; }
3833
3834 /// See AbstractAttribute::getIdAddr()
3835 const char *getIdAddr() const override { return &ID; }
3836
3837 /// This function should return true if the type of the \p AA is
3838 /// AAIntraFnReachability
3839 static bool classof(const AbstractAttribute *AA) {
3840 return (AA->getIdAddr() == &ID);
3841 }
3842
3843 /// Unique ID (due to the unique address)
3844 static const char ID;
3845};
3846
3847/// An abstract interface for all noalias attributes.
3849 : public IRAttribute<Attribute::NoAlias,
3850 StateWrapper<BooleanState, AbstractAttribute>,
3851 AANoAlias> {
3853
3854 /// See AbstractAttribute::isValidIRPositionForInit
3856 if (!IRP.getAssociatedType()->isPointerTy())
3857 return false;
3858 return IRAttribute::isValidIRPositionForInit(A, IRP);
3859 }
3860
3861 /// See IRAttribute::isImpliedByIR
3862 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3863 Attribute::AttrKind ImpliedAttributeKind,
3864 bool IgnoreSubsumingPositions = false);
3865
3866 /// See AbstractAttribute::requiresCallersForArgOrFunction
3867 static bool requiresCallersForArgOrFunction() { return true; }
3868
3869 /// Return true if we assume that the underlying value is alias.
3870 bool isAssumedNoAlias() const { return getAssumed(); }
3871
3872 /// Return true if we know that underlying value is noalias.
3873 bool isKnownNoAlias() const { return getKnown(); }
3874
3875 /// Create an abstract attribute view for the position \p IRP.
3877
3878 /// See AbstractAttribute::getName()
3879 const std::string getName() const override { return "AANoAlias"; }
3880
3881 /// See AbstractAttribute::getIdAddr()
3882 const char *getIdAddr() const override { return &ID; }
3883
3884 /// This function should return true if the type of the \p AA is AANoAlias
3885 static bool classof(const AbstractAttribute *AA) {
3886 return (AA->getIdAddr() == &ID);
3887 }
3888
3889 /// Unique ID (due to the unique address)
3890 static const char ID;
3891};
3892
3893/// An AbstractAttribute for nofree.
3895 : public IRAttribute<Attribute::NoFree,
3896 StateWrapper<BooleanState, AbstractAttribute>,
3897 AANoFree> {
3899
3900 /// See IRAttribute::isImpliedByIR
3901 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
3902 Attribute::AttrKind ImpliedAttributeKind,
3903 bool IgnoreSubsumingPositions = false) {
3904 // Note: This is also run for non-IPO amendable functions.
3905 assert(ImpliedAttributeKind == Attribute::NoFree);
3906 return A.hasAttr(
3907 IRP, {Attribute::ReadNone, Attribute::ReadOnly, Attribute::NoFree},
3908 IgnoreSubsumingPositions, Attribute::NoFree);
3909 }
3910
3911 /// See AbstractAttribute::isValidIRPositionForInit
3913 if (!IRP.isFunctionScope() &&
3915 return false;
3916 return IRAttribute::isValidIRPositionForInit(A, IRP);
3917 }
3918
3919 /// Return true if "nofree" is assumed.
3920 bool isAssumedNoFree() const { return getAssumed(); }
3921
3922 /// Return true if "nofree" is known.
3923 bool isKnownNoFree() const { return getKnown(); }
3924
3925 /// Create an abstract attribute view for the position \p IRP.
3927
3928 /// See AbstractAttribute::getName()
3929 const std::string getName() const override { return "AANoFree"; }
3930
3931 /// See AbstractAttribute::getIdAddr()
3932 const char *getIdAddr() const override { return &ID; }
3933
3934 /// This function should return true if the type of the \p AA is AANoFree
3935 static bool classof(const AbstractAttribute *AA) {
3936 return (AA->getIdAddr() == &ID);
3937 }
3938
3939 /// Unique ID (due to the unique address)
3940 static const char ID;
3941};
3942
3943/// An AbstractAttribute for noreturn.
3945 : public IRAttribute<Attribute::NoReturn,
3946 StateWrapper<BooleanState, AbstractAttribute>,
3947 AANoReturn> {
3949
3950 /// Return true if the underlying object is assumed to never return.
3951 bool isAssumedNoReturn() const { return getAssumed(); }
3952
3953 /// Return true if the underlying object is known to never return.
3954 bool isKnownNoReturn() const { return getKnown(); }
3955
3956 /// Create an abstract attribute view for the position \p IRP.
3958
3959 /// See AbstractAttribute::getName()
3960 const std::string getName() const override { return "AANoReturn"; }
3961
3962 /// See AbstractAttribute::getIdAddr()
3963 const char *getIdAddr() const override { return &ID; }
3964
3965 /// This function should return true if the type of the \p AA is AANoReturn
3966 static bool classof(const AbstractAttribute *AA) {
3967 return (AA->getIdAddr() == &ID);
3968 }
3969
3970 /// Unique ID (due to the unique address)
3971 static const char ID;
3972};
3973
3974/// An abstract interface for liveness abstract attribute.
3976 : public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> {
3978 AAIsDead(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3979
3980 /// See AbstractAttribute::isValidIRPositionForInit
3983 return isa<Function>(IRP.getAnchorValue()) &&
3984 !cast<Function>(IRP.getAnchorValue()).isDeclaration();
3985 return true;
3986 }
3987
3988 /// State encoding bits. A set bit in the state means the property holds.
3989 enum {
3992
3994 };
3995 static_assert(IS_DEAD == getBestState(), "Unexpected BEST_STATE value");
3996
3997protected:
3998 /// The query functions are protected such that other attributes need to go
3999 /// through the Attributor interfaces: `Attributor::isAssumedDead(...)`
4000
4001 /// Returns true if the underlying value is assumed dead.
4002 virtual bool isAssumedDead() const = 0;
4003
4004 /// Returns true if the underlying value is known dead.
4005 virtual bool isKnownDead() const = 0;
4006
4007 /// Returns true if \p BB is known dead.
4008 virtual bool isKnownDead(const BasicBlock *BB) const = 0;
4009
4010 /// Returns true if \p I is assumed dead.
4011 virtual bool isAssumedDead(const Instruction *I) const = 0;
4012
4013 /// Returns true if \p I is known dead.
4014 virtual bool isKnownDead(const Instruction *I) const = 0;
4015
4016 /// Return true if the underlying value is a store that is known to be
4017 /// removable. This is different from dead stores as the removable store
4018 /// can have an effect on live values, especially loads, but that effect
4019 /// is propagated which allows us to remove the store in turn.
4020 virtual bool isRemovableStore() const { return false; }
4021
4022 /// This method is used to check if at least one instruction in a collection
4023 /// of instructions is live.
4024 template <typename T> bool isLiveInstSet(T begin, T end) const {
4025 for (const auto &I : llvm::make_range(begin, end)) {
4026 assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
4027 "Instruction must be in the same anchor scope function.");
4028
4029 if (!isAssumedDead(I))
4030 return true;
4031 }
4032
4033 return false;
4034 }
4035
4036public:
4037 /// Create an abstract attribute view for the position \p IRP.
4039
4040 /// Determine if \p F might catch asynchronous exceptions.
4042 return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
4043 }
4044
4045 /// Returns true if \p BB is assumed dead.
4046 virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
4047
4048 /// Return if the edge from \p From BB to \p To BB is assumed dead.
4049 /// This is specifically useful in AAReachability.
4050 virtual bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const {
4051 return false;
4052 }
4053
4054 /// See AbstractAttribute::getName()
4055 const std::string getName() const override { return "AAIsDead"; }
4056
4057 /// See AbstractAttribute::getIdAddr()
4058 const char *getIdAddr() const override { return &ID; }
4059
4060 /// This function should return true if the type of the \p AA is AAIsDead
4061 static bool classof(const AbstractAttribute *AA) {
4062 return (AA->getIdAddr() == &ID);
4063 }
4064
4065 /// Unique ID (due to the unique address)
4066 static const char ID;
4067
4068 friend struct Attributor;
4069};
4070
4071/// State for dereferenceable attribute
4073
4074 static DerefState getBestState() { return DerefState(); }
4075 static DerefState getBestState(const DerefState &) { return getBestState(); }
4076
4077 /// Return the worst possible representable state.
4079 DerefState DS;
4080 DS.indicatePessimisticFixpoint();
4081 return DS;
4082 }
4084 return getWorstState();
4085 }
4086
4087 /// State representing for dereferenceable bytes.
4089
4090 /// Map representing for accessed memory offsets and sizes.
4091 /// A key is Offset and a value is size.
4092 /// If there is a load/store instruction something like,
4093 /// p[offset] = v;
4094 /// (offset, sizeof(v)) will be inserted to this map.
4095 /// std::map is used because we want to iterate keys in ascending order.
4096 std::map<int64_t, uint64_t> AccessedBytesMap;
4097
4098 /// Helper function to calculate dereferenceable bytes from current known
4099 /// bytes and accessed bytes.
4100 ///
4101 /// int f(int *A){
4102 /// *A = 0;
4103 /// *(A+2) = 2;
4104 /// *(A+1) = 1;
4105 /// *(A+10) = 10;
4106 /// }
4107 /// ```
4108 /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`.
4109 /// AccessedBytesMap is std::map so it is iterated in accending order on
4110 /// key(Offset). So KnownBytes will be updated like this:
4111 ///
4112 /// |Access | KnownBytes
4113 /// |(0, 4)| 0 -> 4
4114 /// |(4, 4)| 4 -> 8
4115 /// |(8, 4)| 8 -> 12
4116 /// |(40, 4) | 12 (break)
4117 void computeKnownDerefBytesFromAccessedMap() {
4118 int64_t KnownBytes = DerefBytesState.getKnown();
4119 for (auto &Access : AccessedBytesMap) {
4120 if (KnownBytes < Access.first)
4121 break;
4122 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
4123 }
4124
4126 }
4127
4128 /// State representing that whether the value is globaly dereferenceable.
4129 BooleanState GlobalState;
4130
4131 /// See AbstractState::isValidState()
4132 bool isValidState() const override { return DerefBytesState.isValidState(); }
4133
4134 /// See AbstractState::isAtFixpoint()
4135 bool isAtFixpoint() const override {
4136 return !isValidState() ||
4137 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
4138 }
4139
4140 /// See AbstractState::indicateOptimisticFixpoint(...)
4143 GlobalState.indicateOptimisticFixpoint();
4145 }
4146
4147 /// See AbstractState::indicatePessimisticFixpoint(...)
4150 GlobalState.indicatePessimisticFixpoint();
4151 return ChangeStatus::CHANGED;
4152 }
4153
4154 /// Update known dereferenceable bytes.
4155 void takeKnownDerefBytesMaximum(uint64_t Bytes) {
4157
4158 // Known bytes might increase.
4159 computeKnownDerefBytesFromAccessedMap();
4160 }
4161
4162 /// Update assumed dereferenceable bytes.
4163 void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
4165 }
4166
4167 /// Add accessed bytes to the map.
4168 void addAccessedBytes(int64_t Offset, uint64_t Size) {
4169 uint64_t &AccessedBytes = AccessedBytesMap[Offset];
4170 AccessedBytes = std::max(AccessedBytes, Size);
4171
4172 // Known bytes might increase.
4173 computeKnownDerefBytesFromAccessedMap();
4174 }
4175
4176 /// Equality for DerefState.
4177 bool operator==(const DerefState &R) const {
4178 return this->DerefBytesState == R.DerefBytesState &&
4179 this->GlobalState == R.GlobalState;
4180 }
4181
4182 /// Inequality for DerefState.
4183 bool operator!=(const DerefState &R) const { return !(*this == R); }
4184
4185 /// See IntegerStateBase::operator^=
4186 DerefState operator^=(const DerefState &R) {
4187 DerefBytesState ^= R.DerefBytesState;
4188 GlobalState ^= R.GlobalState;
4189 return *this;
4190 }
4191
4192 /// See IntegerStateBase::operator+=
4193 DerefState operator+=(const DerefState &R) {
4194 DerefBytesState += R.DerefBytesState;
4195 GlobalState += R.GlobalState;
4196 return *this;
4197 }
4198
4199 /// See IntegerStateBase::operator&=
4200 DerefState operator&=(const DerefState &R) {
4201 DerefBytesState &= R.DerefBytesState;
4202 GlobalState &= R.GlobalState;
4203 return *this;
4204 }
4205
4206 /// See IntegerStateBase::operator|=
4207 DerefState operator|=(const DerefState &R) {
4208 DerefBytesState |= R.DerefBytesState;
4209 GlobalState |= R.GlobalState;
4210 return *this;
4211 }
4212};
4213
4214/// An abstract interface for all dereferenceable attribute.
4216 : public IRAttribute<Attribute::Dereferenceable,
4217 StateWrapper<DerefState, AbstractAttribute>,
4218 AADereferenceable> {
4220
4221 /// See AbstractAttribute::isValidIRPositionForInit
4223 if (!IRP.getAssociatedType()->isPointerTy())
4224 return false;
4225 return IRAttribute::isValidIRPositionForInit(A, IRP);
4226 }
4227
4228 /// Return true if we assume that underlying value is
4229 /// dereferenceable(_or_null) globally.
4230 bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
4231
4232 /// Return true if we know that underlying value is
4233 /// dereferenceable(_or_null) globally.
4234 bool isKnownGlobal() const { return GlobalState.getKnown(); }
4235
4236 /// Return assumed dereferenceable bytes.
4238 return DerefBytesState.getAssumed();
4239 }
4240
4241 /// Return known dereferenceable bytes.
4243 return DerefBytesState.getKnown();
4244 }
4245
4246 /// Create an abstract attribute view for the position \p IRP.
4248 Attributor &A);
4249
4250 /// See AbstractAttribute::getName()
4251 const std::string getName() const override { return "AADereferenceable"; }
4252
4253 /// See AbstractAttribute::getIdAddr()
4254 const char *getIdAddr() const override { return &ID; }
4255
4256 /// This function should return true if the type of the \p AA is
4257 /// AADereferenceable
4258 static bool classof(const AbstractAttribute *AA) {
4259 return (AA->getIdAddr() == &ID);
4260 }
4261
4262 /// Unique ID (due to the unique address)
4263 static const char ID;
4264};
4265
4268/// An abstract interface for all align attributes.
4270 : public IRAttribute<Attribute::Alignment,
4271 StateWrapper<AAAlignmentStateType, AbstractAttribute>,
4272 AAAlign> {
4274
4275 /// See AbstractAttribute::isValidIRPositionForInit
4278 return false;
4279 return IRAttribute::isValidIRPositionForInit(A, IRP);
4280 }
4281
4282 /// Return assumed alignment.
4283 Align getAssumedAlign() const { return Align(getAssumed()); }
4284
4285 /// Return known alignment.
4286 Align getKnownAlign() const { return Align(getKnown()); }
4287
4288 /// See AbstractAttribute::getName()
4289 const std::string getName() const override { return "AAAlign"; }
4290
4291 /// See AbstractAttribute::getIdAddr()
4292 const char *getIdAddr() const override { return &ID; }
4293
4294 /// This function should return true if the type of the \p AA is AAAlign
4295 static bool classof(const AbstractAttribute *AA) {
4296 return (AA->getIdAddr() == &ID);
4297 }
4298
4299 /// Create an abstract attribute view for the position \p IRP.
4301
4302 /// Unique ID (due to the unique address)
4303 static const char ID;
4304};
4305
4306/// An abstract interface to track if a value leaves it's defining function
4307/// instance.
4308/// TODO: We should make it a ternary AA tracking uniqueness, and uniqueness
4309/// wrt. the Attributor analysis separately.
4310struct AAInstanceInfo : public StateWrapper<BooleanState, AbstractAttribute> {
4313
4314 /// Return true if we know that the underlying value is unique in its scope
4315 /// wrt. the Attributor analysis. That means it might not be unique but we can
4316 /// still use pointer equality without risking to represent two instances with
4317 /// one `llvm::Value`.
4318 bool isKnownUniqueForAnalysis() const { return isKnown(); }
4319
4320 /// Return true if we assume that the underlying value is unique in its scope
4321 /// wrt. the Attributor analysis. That means it might not be unique but we can
4322 /// still use pointer equality without risking to represent two instances with
4323 /// one `llvm::Value`.
4324 bool isAssumedUniqueForAnalysis() const { return isAssumed(); }
4325
4326 /// Create an abstract attribute view for the position \p IRP.
4328 Attributor &A);
4329
4330 /// See AbstractAttribute::getName()
4331 const std::string getName() const override { return "AAInstanceInfo"; }
4332
4333 /// See AbstractAttribute::getIdAddr()
4334 const char *getIdAddr() const override { return &ID; }
4335
4336 /// This function should return true if the type of the \p AA is
4337 /// AAInstanceInfo
4338 static bool classof(const AbstractAttribute *AA) {
4339 return (AA->getIdAddr() == &ID);
4340 }
4341
4342 /// Unique ID (due to the unique address)
4343 static const char ID;
4344};
4345
4346/// An abstract interface for all nocapture attributes.
4348 : public IRAttribute<
4349 Attribute::NoCapture,
4350 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>,
4351 AANoCapture> {
4353
4354 /// See IRAttribute::isImpliedByIR
4355 static bool isImpliedByIR(Attributor &A, const IRPosition &IRP,
4356 Attribute::AttrKind ImpliedAttributeKind,
4357 bool IgnoreSubsumingPositions = false);
4358
4359 /// Update \p State according to the capture capabilities of \p F for position
4360 /// \p IRP.
4361 static void determineFunctionCaptureCapabilities(const IRPosition &IRP,
4362 const Function &F,
4363 BitIntegerState &State);
4364
4365 /// See AbstractAttribute::isValidIRPositionForInit
4367 if (!IRP.getAssociatedType()->isPointerTy())
4368 return false;
4369 return IRAttribute::isValidIRPositionForInit(A, IRP);
4370 }
4371
4372 /// State encoding bits. A set bit in the state means the property holds.
4373 /// NO_CAPTURE is the best possible state, 0 the worst possible state.
4374 enum {
4378
4379 /// If we do not capture the value in memory or through integers we can only
4380 /// communicate it back as a derived pointer.
4382
4383 /// If we do not capture the value in memory, through integers, or as a
4384 /// derived pointer we know it is not captured.
4385 NO_CAPTURE =
4387 };
4388
4389 /// Return true if we know that the underlying value is not captured in its
4390 /// respective scope.
4391 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
4392
4393 /// Return true if we assume that the underlying value is not captured in its
4394 /// respective scope.
4395 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
4396
4397 /// Return true if we know that the underlying value is not captured in its
4398 /// respective scope but we allow it to escape through a "return".
4401 }
4402
4403 /// Return true if we assume that the underlying value is not captured in its
4404 /// respective scope but we allow it to escape through a "return".
4407 }
4408
4409 /// Create an abstract attribute view for the position \p IRP.
4411
4412 /// See AbstractAttribute::getName()
4413 const std::string getName() const override { return "AANoCapture"; }
4414
4415 /// See AbstractAttribute::getIdAddr()
4416 const char *getIdAddr() const override { return &ID; }
4417
4418 /// This function should return true if the type of the \p AA is AANoCapture
4419 static bool classof(const AbstractAttribute *AA) {
4420 return (AA->