[Alignment][NFC] Support compile time constants
[llvm-core.git] / include / llvm / Transforms / IPO / Attributor.h
blob3dbe0fcd76eac8dc38116ce6d046969c2555c8cb
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.
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.
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.
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.
32 // The Attributor will only reevaluated 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.
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.
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.
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.
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 // IntegerState if they fit your needs, e.g., you require only a bit-encoding.
76 // - Implement all pure methods. Also use overloading if the attribute is not
77 // conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for
78 // an argument, call site argument, function return value, or function. See
79 // the class and method descriptions for more information on the two
80 // "Abstract" classes and their respective methods.
81 // - Register opportunities for the new abstract attribute in the
82 // `Attributor::identifyDefaultAbstractAttributes` method if it should be
83 // counted as a 'default' attribute.
84 // - Add sufficient tests.
85 // - Add a Statistics object for bookkeeping. If it is a simple (set of)
86 // attribute(s) manifested through the Attributor manifestation framework, see
87 // the bookkeeping function in Attributor.cpp.
88 // - If instructions with a certain opcode are interesting to the attribute, add
89 // that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
90 // will make it possible to query all those instructions through the
91 // `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
92 // need to traverse the IR repeatedly.
94 //===----------------------------------------------------------------------===//
96 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
97 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
99 #include "llvm/ADT/MapVector.h"
100 #include "llvm/ADT/SCCIterator.h"
101 #include "llvm/ADT/SetVector.h"
102 #include "llvm/Analysis/AliasAnalysis.h"
103 #include "llvm/Analysis/CallGraph.h"
104 #include "llvm/Analysis/MustExecute.h"
105 #include "llvm/Analysis/TargetLibraryInfo.h"
106 #include "llvm/IR/CallSite.h"
107 #include "llvm/IR/PassManager.h"
109 namespace llvm {
111 struct AbstractAttribute;
112 struct InformationCache;
113 struct AAIsDead;
115 class Function;
117 /// Simple enum class that forces the status to be spelled out explicitly.
119 ///{
120 enum class ChangeStatus {
121 CHANGED,
122 UNCHANGED,
125 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
126 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
127 ///}
129 /// Helper to describe and deal with positions in the LLVM-IR.
131 /// A position in the IR is described by an anchor value and an "offset" that
132 /// could be the argument number, for call sites and arguments, or an indicator
133 /// of the "position kind". The kinds, specified in the Kind enum below, include
134 /// the locations in the attribute list, i.a., function scope and return value,
135 /// as well as a distinction between call sites and functions. Finally, there
136 /// are floating values that do not have a corresponding attribute list
137 /// position.
138 struct IRPosition {
139 virtual ~IRPosition() {}
141 /// The positions we distinguish in the IR.
143 /// The values are chosen such that the KindOrArgNo member has a value >= 1
144 /// if it is an argument or call site argument while a value < 1 indicates the
145 /// respective kind of that value.
146 enum Kind : int {
147 IRP_INVALID = -6, ///< An invalid position.
148 IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable
149 ///< for attributes. This could be any value or instruction.
150 IRP_RETURNED = -4, ///< An attribute for the function return value.
151 IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value.
152 IRP_FUNCTION = -2, ///< An attribute for a function (scope).
153 IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope).
154 IRP_ARGUMENT = 0, ///< An attribute for a function argument.
155 IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument.
158 /// Default constructor available to create invalid positions implicitly. All
159 /// other positions need to be created explicitly through the appropriate
160 /// static member function.
161 IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); }
163 /// Create a position describing the value of \p V.
164 static const IRPosition value(const Value &V) {
165 if (auto *Arg = dyn_cast<Argument>(&V))
166 return IRPosition::argument(*Arg);
167 if (auto *CB = dyn_cast<CallBase>(&V))
168 return IRPosition::callsite_returned(*CB);
169 return IRPosition(const_cast<Value &>(V), IRP_FLOAT);
172 /// Create a position describing the function scope of \p F.
173 static const IRPosition function(const Function &F) {
174 return IRPosition(const_cast<Function &>(F), IRP_FUNCTION);
177 /// Create a position describing the returned value of \p F.
178 static const IRPosition returned(const Function &F) {
179 return IRPosition(const_cast<Function &>(F), IRP_RETURNED);
182 /// Create a position describing the argument \p Arg.
183 static const IRPosition argument(const Argument &Arg) {
184 return IRPosition(const_cast<Argument &>(Arg), Kind(Arg.getArgNo()));
187 /// Create a position describing the function scope of \p CB.
188 static const IRPosition callsite_function(const CallBase &CB) {
189 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE);
192 /// Create a position describing the returned value of \p CB.
193 static const IRPosition callsite_returned(const CallBase &CB) {
194 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED);
197 /// Create a position describing the argument of \p CB at position \p ArgNo.
198 static const IRPosition callsite_argument(const CallBase &CB,
199 unsigned ArgNo) {
200 return IRPosition(const_cast<CallBase &>(CB), Kind(ArgNo));
203 /// Create a position describing the function scope of \p ICS.
204 static const IRPosition callsite_function(ImmutableCallSite ICS) {
205 return IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction()));
208 /// Create a position describing the returned value of \p ICS.
209 static const IRPosition callsite_returned(ImmutableCallSite ICS) {
210 return IRPosition::callsite_returned(cast<CallBase>(*ICS.getInstruction()));
213 /// Create a position describing the argument of \p ICS at position \p ArgNo.
214 static const IRPosition callsite_argument(ImmutableCallSite ICS,
215 unsigned ArgNo) {
216 return IRPosition::callsite_argument(cast<CallBase>(*ICS.getInstruction()),
217 ArgNo);
220 /// Create a position describing the argument of \p ACS at position \p ArgNo.
221 static const IRPosition callsite_argument(AbstractCallSite ACS,
222 unsigned ArgNo) {
223 int CSArgNo = ACS.getCallArgOperandNo(ArgNo);
224 if (CSArgNo >= 0)
225 return IRPosition::callsite_argument(
226 cast<CallBase>(*ACS.getInstruction()), CSArgNo);
227 return IRPosition();
230 /// Create a position with function scope matching the "context" of \p IRP.
231 /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result
232 /// will be a call site position, otherwise the function position of the
233 /// associated function.
234 static const IRPosition function_scope(const IRPosition &IRP) {
235 if (IRP.isAnyCallSitePosition()) {
236 return IRPosition::callsite_function(
237 cast<CallBase>(IRP.getAnchorValue()));
239 assert(IRP.getAssociatedFunction());
240 return IRPosition::function(*IRP.getAssociatedFunction());
243 bool operator==(const IRPosition &RHS) const {
244 return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo);
246 bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); }
248 /// Return the value this abstract attribute is anchored with.
250 /// The anchor value might not be the associated value if the latter is not
251 /// sufficient to determine where arguments will be manifested. This is, so
252 /// far, only the case for call site arguments as the value is not sufficient
253 /// to pinpoint them. Instead, we can use the call site as an anchor.
255 ///{
256 Value &getAnchorValue() {
257 assert(KindOrArgNo != IRP_INVALID &&
258 "Invalid position does not have an anchor value!");
259 return *AnchorVal;
261 const Value &getAnchorValue() const {
262 return const_cast<IRPosition *>(this)->getAnchorValue();
264 ///}
266 /// Return the associated function, if any.
268 ///{
269 Function *getAssociatedFunction() {
270 if (auto *CB = dyn_cast<CallBase>(AnchorVal))
271 return CB->getCalledFunction();
272 assert(KindOrArgNo != IRP_INVALID &&
273 "Invalid position does not have an anchor scope!");
274 Value &V = getAnchorValue();
275 if (isa<Function>(V))
276 return &cast<Function>(V);
277 if (isa<Argument>(V))
278 return cast<Argument>(V).getParent();
279 if (isa<Instruction>(V))
280 return cast<Instruction>(V).getFunction();
281 return nullptr;
283 const Function *getAssociatedFunction() const {
284 return const_cast<IRPosition *>(this)->getAssociatedFunction();
286 ///}
288 /// Return the associated argument, if any.
290 ///{
291 Argument *getAssociatedArgument() {
292 if (auto *Arg = dyn_cast<Argument>(&getAnchorValue()))
293 return Arg;
294 int ArgNo = getArgNo();
295 if (ArgNo < 0)
296 return nullptr;
297 Function *AssociatedFn = getAssociatedFunction();
298 if (!AssociatedFn || AssociatedFn->arg_size() <= unsigned(ArgNo))
299 return nullptr;
300 return AssociatedFn->arg_begin() + ArgNo;
302 const Argument *getAssociatedArgument() const {
303 return const_cast<IRPosition *>(this)->getAssociatedArgument();
305 ///}
307 /// Return true if the position refers to a function interface, that is the
308 /// function scope, the function return, or an argumnt.
309 bool isFnInterfaceKind() const {
310 switch (getPositionKind()) {
311 case IRPosition::IRP_FUNCTION:
312 case IRPosition::IRP_RETURNED:
313 case IRPosition::IRP_ARGUMENT:
314 return true;
315 default:
316 return false;
320 /// Return the Function surrounding the anchor value.
322 ///{
323 Function *getAnchorScope() {
324 Value &V = getAnchorValue();
325 if (isa<Function>(V))
326 return &cast<Function>(V);
327 if (isa<Argument>(V))
328 return cast<Argument>(V).getParent();
329 if (isa<Instruction>(V))
330 return cast<Instruction>(V).getFunction();
331 return nullptr;
333 const Function *getAnchorScope() const {
334 return const_cast<IRPosition *>(this)->getAnchorScope();
336 ///}
338 /// Return the context instruction, if any.
340 ///{
341 Instruction *getCtxI() {
342 Value &V = getAnchorValue();
343 if (auto *I = dyn_cast<Instruction>(&V))
344 return I;
345 if (auto *Arg = dyn_cast<Argument>(&V))
346 if (!Arg->getParent()->isDeclaration())
347 return &Arg->getParent()->getEntryBlock().front();
348 if (auto *F = dyn_cast<Function>(&V))
349 if (!F->isDeclaration())
350 return &(F->getEntryBlock().front());
351 return nullptr;
353 const Instruction *getCtxI() const {
354 return const_cast<IRPosition *>(this)->getCtxI();
356 ///}
358 /// Return the value this abstract attribute is associated with.
360 ///{
361 Value &getAssociatedValue() {
362 assert(KindOrArgNo != IRP_INVALID &&
363 "Invalid position does not have an associated value!");
364 if (getArgNo() < 0 || isa<Argument>(AnchorVal))
365 return *AnchorVal;
366 assert(isa<CallBase>(AnchorVal) && "Expected a call base!");
367 return *cast<CallBase>(AnchorVal)->getArgOperand(getArgNo());
369 const Value &getAssociatedValue() const {
370 return const_cast<IRPosition *>(this)->getAssociatedValue();
372 ///}
374 /// Return the argument number of the associated value if it is an argument or
375 /// call site argument, otherwise a negative value.
376 int getArgNo() const { return KindOrArgNo; }
378 /// Return the index in the attribute list for this position.
379 unsigned getAttrIdx() const {
380 switch (getPositionKind()) {
381 case IRPosition::IRP_INVALID:
382 case IRPosition::IRP_FLOAT:
383 break;
384 case IRPosition::IRP_FUNCTION:
385 case IRPosition::IRP_CALL_SITE:
386 return AttributeList::FunctionIndex;
387 case IRPosition::IRP_RETURNED:
388 case IRPosition::IRP_CALL_SITE_RETURNED:
389 return AttributeList::ReturnIndex;
390 case IRPosition::IRP_ARGUMENT:
391 case IRPosition::IRP_CALL_SITE_ARGUMENT:
392 return KindOrArgNo + AttributeList::FirstArgIndex;
394 llvm_unreachable(
395 "There is no attribute index for a floating or invalid position!");
398 /// Return the associated position kind.
399 Kind getPositionKind() const {
400 if (getArgNo() >= 0) {
401 assert(((isa<Argument>(getAnchorValue()) &&
402 isa<Argument>(getAssociatedValue())) ||
403 isa<CallBase>(getAnchorValue())) &&
404 "Expected argument or call base due to argument number!");
405 if (isa<CallBase>(getAnchorValue()))
406 return IRP_CALL_SITE_ARGUMENT;
407 return IRP_ARGUMENT;
410 assert(KindOrArgNo < 0 &&
411 "Expected (call site) arguments to never reach this point!");
412 return Kind(KindOrArgNo);
415 /// TODO: Figure out if the attribute related helper functions should live
416 /// here or somewhere else.
418 /// Return true if any kind in \p AKs existing in the IR at a position that
419 /// will affect this one. See also getAttrs(...).
420 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions,
421 /// e.g., the function position if this is an
422 /// argument position, should be ignored.
423 bool hasAttr(ArrayRef<Attribute::AttrKind> AKs,
424 bool IgnoreSubsumingPositions = false) const;
426 /// Return the attributes of any kind in \p AKs existing in the IR at a
427 /// position that will affect this one. While each position can only have a
428 /// single attribute of any kind in \p AKs, there are "subsuming" positions
429 /// that could have an attribute as well. This method returns all attributes
430 /// found in \p Attrs.
431 void getAttrs(ArrayRef<Attribute::AttrKind> AKs,
432 SmallVectorImpl<Attribute> &Attrs) const;
434 /// Return the attribute of kind \p AK existing in the IR at this position.
435 Attribute getAttr(Attribute::AttrKind AK) const {
436 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
437 return Attribute();
439 AttributeList AttrList;
440 if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue()))
441 AttrList = ICS.getAttributes();
442 else
443 AttrList = getAssociatedFunction()->getAttributes();
445 if (AttrList.hasAttribute(getAttrIdx(), AK))
446 return AttrList.getAttribute(getAttrIdx(), AK);
447 return Attribute();
450 /// Remove the attribute of kind \p AKs existing in the IR at this position.
451 void removeAttrs(ArrayRef<Attribute::AttrKind> AKs) {
452 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
453 return;
455 AttributeList AttrList;
456 CallSite CS = CallSite(&getAnchorValue());
457 if (CS)
458 AttrList = CS.getAttributes();
459 else
460 AttrList = getAssociatedFunction()->getAttributes();
462 LLVMContext &Ctx = getAnchorValue().getContext();
463 for (Attribute::AttrKind AK : AKs)
464 AttrList = AttrList.removeAttribute(Ctx, getAttrIdx(), AK);
466 if (CS)
467 CS.setAttributes(AttrList);
468 else
469 getAssociatedFunction()->setAttributes(AttrList);
472 bool isAnyCallSitePosition() const {
473 switch (getPositionKind()) {
474 case IRPosition::IRP_CALL_SITE:
475 case IRPosition::IRP_CALL_SITE_RETURNED:
476 case IRPosition::IRP_CALL_SITE_ARGUMENT:
477 return true;
478 default:
479 return false;
483 /// Special DenseMap key values.
485 ///{
486 static const IRPosition EmptyKey;
487 static const IRPosition TombstoneKey;
488 ///}
490 private:
491 /// Private constructor for special values only!
492 explicit IRPosition(int KindOrArgNo)
493 : AnchorVal(0), KindOrArgNo(KindOrArgNo) {}
495 /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK.
496 explicit IRPosition(Value &AnchorVal, Kind PK)
497 : AnchorVal(&AnchorVal), KindOrArgNo(PK) {
498 verify();
501 /// Verify internal invariants.
502 void verify();
504 /// The value this position is anchored at.
505 Value *AnchorVal;
507 /// The argument number, if non-negative, or the position "kind".
508 int KindOrArgNo;
511 /// Helper that allows IRPosition as a key in a DenseMap.
512 template <> struct DenseMapInfo<IRPosition> {
513 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; }
514 static inline IRPosition getTombstoneKey() {
515 return IRPosition::TombstoneKey;
517 static unsigned getHashValue(const IRPosition &IRP) {
518 return (DenseMapInfo<Value *>::getHashValue(&IRP.getAnchorValue()) << 4) ^
519 (unsigned(IRP.getArgNo()));
521 static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) {
522 return LHS == RHS;
526 /// A visitor class for IR positions.
528 /// Given a position P, the SubsumingPositionIterator allows to visit "subsuming
529 /// positions" wrt. attributes/information. Thus, if a piece of information
530 /// holds for a subsuming position, it also holds for the position P.
532 /// The subsuming positions always include the initial position and then,
533 /// depending on the position kind, additionally the following ones:
534 /// - for IRP_RETURNED:
535 /// - the function (IRP_FUNCTION)
536 /// - for IRP_ARGUMENT:
537 /// - the function (IRP_FUNCTION)
538 /// - for IRP_CALL_SITE:
539 /// - the callee (IRP_FUNCTION), if known
540 /// - for IRP_CALL_SITE_RETURNED:
541 /// - the callee (IRP_RETURNED), if known
542 /// - the call site (IRP_FUNCTION)
543 /// - the callee (IRP_FUNCTION), if known
544 /// - for IRP_CALL_SITE_ARGUMENT:
545 /// - the argument of the callee (IRP_ARGUMENT), if known
546 /// - the callee (IRP_FUNCTION), if known
547 /// - the position the call site argument is associated with if it is not
548 /// anchored to the call site, e.g., if it is an arugment then the argument
549 /// (IRP_ARGUMENT)
550 class SubsumingPositionIterator {
551 SmallVector<IRPosition, 4> IRPositions;
552 using iterator = decltype(IRPositions)::iterator;
554 public:
555 SubsumingPositionIterator(const IRPosition &IRP);
556 iterator begin() { return IRPositions.begin(); }
557 iterator end() { return IRPositions.end(); }
560 /// Wrapper for FunctoinAnalysisManager.
561 struct AnalysisGetter {
562 template <typename Analysis>
563 typename Analysis::Result *getAnalysis(const Function &F) {
564 if (!MAM || !F.getParent())
565 return nullptr;
566 auto &FAM = MAM->getResult<FunctionAnalysisManagerModuleProxy>(
567 const_cast<Module &>(*F.getParent()))
568 .getManager();
569 return &FAM.getResult<Analysis>(const_cast<Function &>(F));
572 template <typename Analysis>
573 typename Analysis::Result *getAnalysis(const Module &M) {
574 if (!MAM)
575 return nullptr;
576 return &MAM->getResult<Analysis>(const_cast<Module &>(M));
578 AnalysisGetter(ModuleAnalysisManager &MAM) : MAM(&MAM) {}
579 AnalysisGetter() {}
581 private:
582 ModuleAnalysisManager *MAM = nullptr;
585 /// Data structure to hold cached (LLVM-IR) information.
587 /// All attributes are given an InformationCache object at creation time to
588 /// avoid inspection of the IR by all of them individually. This default
589 /// InformationCache will hold information required by 'default' attributes,
590 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
591 /// is called.
593 /// If custom abstract attributes, registered manually through
594 /// Attributor::registerAA(...), need more information, especially if it is not
595 /// reusable, it is advised to inherit from the InformationCache and cast the
596 /// instance down in the abstract attributes.
597 struct InformationCache {
598 InformationCache(const Module &M, AnalysisGetter &AG)
599 : DL(M.getDataLayout()), Explorer(/* ExploreInterBlock */ true), AG(AG) {
601 CallGraph *CG = AG.getAnalysis<CallGraphAnalysis>(M);
602 if (!CG)
603 return;
605 DenseMap<const Function *, unsigned> SccSize;
606 for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) {
607 for (CallGraphNode *Node : *I)
608 SccSize[Node->getFunction()] = I->size();
610 SccSizeOpt = std::move(SccSize);
613 /// A map type from opcodes to instructions with this opcode.
614 using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>;
616 /// Return the map that relates "interesting" opcodes with all instructions
617 /// with that opcode in \p F.
618 OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) {
619 return FuncInstOpcodeMap[&F];
622 /// A vector type to hold instructions.
623 using InstructionVectorTy = std::vector<Instruction *>;
625 /// Return the instructions in \p F that may read or write memory.
626 InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) {
627 return FuncRWInstsMap[&F];
630 /// Return MustBeExecutedContextExplorer
631 MustBeExecutedContextExplorer &getMustBeExecutedContextExplorer() {
632 return Explorer;
635 /// Return TargetLibraryInfo for function \p F.
636 TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) {
637 return AG.getAnalysis<TargetLibraryAnalysis>(F);
640 /// Return AliasAnalysis Result for function \p F.
641 AAResults *getAAResultsForFunction(const Function &F) {
642 return AG.getAnalysis<AAManager>(F);
645 /// Return SCC size on call graph for function \p F.
646 unsigned getSccSize(const Function &F) {
647 if (!SccSizeOpt.hasValue())
648 return 0;
649 return (SccSizeOpt.getValue())[&F];
652 /// Return datalayout used in the module.
653 const DataLayout &getDL() { return DL; }
655 private:
656 /// A map type from functions to opcode to instruction maps.
657 using FuncInstOpcodeMapTy = DenseMap<const Function *, OpcodeInstMapTy>;
659 /// A map type from functions to their read or write instructions.
660 using FuncRWInstsMapTy = DenseMap<const Function *, InstructionVectorTy>;
662 /// A nested map that remembers all instructions in a function with a certain
663 /// instruction opcode (Instruction::getOpcode()).
664 FuncInstOpcodeMapTy FuncInstOpcodeMap;
666 /// A map from functions to their instructions that may read or write memory.
667 FuncRWInstsMapTy FuncRWInstsMap;
669 /// The datalayout used in the module.
670 const DataLayout &DL;
672 /// MustBeExecutedContextExplorer
673 MustBeExecutedContextExplorer Explorer;
675 /// Getters for analysis.
676 AnalysisGetter &AG;
678 /// Cache result for scc size in the call graph
679 Optional<DenseMap<const Function *, unsigned>> SccSizeOpt;
681 /// Give the Attributor access to the members so
682 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
683 friend struct Attributor;
686 /// The fixpoint analysis framework that orchestrates the attribute deduction.
688 /// The Attributor provides a general abstract analysis framework (guided
689 /// fixpoint iteration) as well as helper functions for the deduction of
690 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
691 /// propagated, and ultimately manifested through the Attributor framework. This
692 /// is particularly useful if these properties interact with attributes and a
693 /// co-scheduled deduction allows to improve the solution. Even if not, thus if
694 /// attributes/properties are completely isolated, they should use the
695 /// Attributor framework to reduce the number of fixpoint iteration frameworks
696 /// in the code base. Note that the Attributor design makes sure that isolated
697 /// attributes are not impacted, in any way, by others derived at the same time
698 /// if there is no cross-reasoning performed.
700 /// The public facing interface of the Attributor is kept simple and basically
701 /// allows abstract attributes to one thing, query abstract attributes
702 /// in-flight. There are two reasons to do this:
703 /// a) The optimistic state of one abstract attribute can justify an
704 /// optimistic state of another, allowing to framework to end up with an
705 /// optimistic (=best possible) fixpoint instead of one based solely on
706 /// information in the IR.
707 /// b) This avoids reimplementing various kinds of lookups, e.g., to check
708 /// for existing IR attributes, in favor of a single lookups interface
709 /// provided by an abstract attribute subclass.
711 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
712 /// described in the file comment.
713 struct Attributor {
714 /// Constructor
716 /// \param InfoCache Cache to hold various information accessible for
717 /// the abstract attributes.
718 /// \param DepRecomputeInterval Number of iterations until the dependences
719 /// between abstract attributes are recomputed.
720 /// \param Whitelist If not null, a set limiting the attribute opportunities.
721 Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval,
722 DenseSet<const char *> *Whitelist = nullptr)
723 : InfoCache(InfoCache), DepRecomputeInterval(DepRecomputeInterval),
724 Whitelist(Whitelist) {}
726 ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
728 /// Run the analyses until a fixpoint is reached or enforced (timeout).
730 /// The attributes registered with this Attributor can be used after as long
731 /// as the Attributor is not destroyed (it owns the attributes now).
733 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
734 ChangeStatus run(Module &M);
736 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
737 /// no abstract attribute is found equivalent positions are checked, see
738 /// SubsumingPositionIterator. Thus, the returned abstract attribute
739 /// might be anchored at a different position, e.g., the callee if \p IRP is a
740 /// call base.
742 /// This method is the only (supported) way an abstract attribute can retrieve
743 /// information from another abstract attribute. As an example, take an
744 /// abstract attribute that determines the memory access behavior for a
745 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the
746 /// most optimistic information for other abstract attributes in-flight, e.g.
747 /// the one reasoning about the "captured" state for the argument or the one
748 /// reasoning on the memory access behavior of the function as a whole.
750 /// If the flag \p TrackDependence is set to false the dependence from
751 /// \p QueryingAA to the return abstract attribute is not automatically
752 /// recorded. This should only be used if the caller will record the
753 /// dependence explicitly if necessary, thus if it the returned abstract
754 /// attribute is used for reasoning. To record the dependences explicitly use
755 /// the `Attributor::recordDependence` method.
756 template <typename AAType>
757 const AAType &getAAFor(const AbstractAttribute &QueryingAA,
758 const IRPosition &IRP, bool TrackDependence = true) {
759 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence);
762 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if
763 /// \p FromAA changes \p ToAA should be updated as well.
765 /// This method should be used in conjunction with the `getAAFor` method and
766 /// with the TrackDependence flag passed to the method set to false. This can
767 /// be beneficial to avoid false dependences but it requires the users of
768 /// `getAAFor` to explicitly record true dependences through this method.
769 void recordDependence(const AbstractAttribute &FromAA,
770 const AbstractAttribute &ToAA) {
771 QueryMap[&FromAA].insert(const_cast<AbstractAttribute *>(&ToAA));
774 /// Introduce a new abstract attribute into the fixpoint analysis.
776 /// Note that ownership of the attribute is given to the Attributor. It will
777 /// invoke delete for the Attributor on destruction of the Attributor.
779 /// Attributes are identified by their IR position (AAType::getIRPosition())
780 /// and the address of their static member (see AAType::ID).
781 template <typename AAType> AAType &registerAA(AAType &AA) {
782 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
783 "Cannot register an attribute with a type not derived from "
784 "'AbstractAttribute'!");
785 // Put the attribute in the lookup map structure and the container we use to
786 // keep track of all attributes.
787 IRPosition &IRP = AA.getIRPosition();
788 auto &KindToAbstractAttributeMap = AAMap[IRP];
789 assert(!KindToAbstractAttributeMap.count(&AAType::ID) &&
790 "Attribute already in map!");
791 KindToAbstractAttributeMap[&AAType::ID] = &AA;
792 AllAbstractAttributes.push_back(&AA);
793 return AA;
796 /// Return the internal information cache.
797 InformationCache &getInfoCache() { return InfoCache; }
799 /// Determine opportunities to derive 'default' attributes in \p F and create
800 /// abstract attribute objects for them.
802 /// \param F The function that is checked for attribute opportunities.
804 /// Note that abstract attribute instances are generally created even if the
805 /// IR already contains the information they would deduce. The most important
806 /// reason for this is the single interface, the one of the abstract attribute
807 /// instance, which can be queried without the need to look at the IR in
808 /// various places.
809 void identifyDefaultAbstractAttributes(Function &F);
811 /// Initialize the information cache for queries regarding function \p F.
813 /// This method needs to be called for all function that might be looked at
814 /// through the information cache interface *prior* to looking at them.
815 void initializeInformationCache(Function &F);
817 /// Mark the internal function \p F as live.
819 /// This will trigger the identification and initialization of attributes for
820 /// \p F.
821 void markLiveInternalFunction(const Function &F) {
822 assert(F.hasLocalLinkage() &&
823 "Only local linkage is assumed dead initially.");
825 identifyDefaultAbstractAttributes(const_cast<Function &>(F));
828 /// Record that \p I is deleted after information was manifested.
829 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
831 /// Record that \p BB is deleted after information was manifested.
832 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
834 /// Record that \p F is deleted after information was manifested.
835 void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
837 /// Return true if \p AA (or its context instruction) is assumed dead.
839 /// If \p LivenessAA is not provided it is queried.
840 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA);
842 /// Check \p Pred on all function call sites.
844 /// This method will evaluate \p Pred on call sites and return
845 /// true if \p Pred holds in every call sites. However, this is only possible
846 /// all call sites are known, hence the function has internal linkage.
847 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
848 const AbstractAttribute &QueryingAA,
849 bool RequireAllCallSites);
851 /// Check \p Pred on all values potentially returned by \p F.
853 /// This method will evaluate \p Pred on all values potentially returned by
854 /// the function associated with \p QueryingAA. The returned values are
855 /// matched with their respective return instructions. Returns true if \p Pred
856 /// holds on all of them.
857 bool checkForAllReturnedValuesAndReturnInsts(
858 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
859 &Pred,
860 const AbstractAttribute &QueryingAA);
862 /// Check \p Pred on all values potentially returned by the function
863 /// associated with \p QueryingAA.
865 /// This is the context insensitive version of the method above.
866 bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred,
867 const AbstractAttribute &QueryingAA);
869 /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
871 /// This method will evaluate \p Pred on all instructions with an opcode
872 /// present in \p Opcode and return true if \p Pred holds on all of them.
873 bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred,
874 const AbstractAttribute &QueryingAA,
875 const ArrayRef<unsigned> &Opcodes);
877 /// Check \p Pred on all call-like instructions (=CallBased derived).
879 /// See checkForAllCallLikeInstructions(...) for more information.
880 bool
881 checkForAllCallLikeInstructions(const function_ref<bool(Instruction &)> &Pred,
882 const AbstractAttribute &QueryingAA) {
883 return checkForAllInstructions(Pred, QueryingAA,
884 {(unsigned)Instruction::Invoke,
885 (unsigned)Instruction::CallBr,
886 (unsigned)Instruction::Call});
889 /// Check \p Pred on all Read/Write instructions.
891 /// This method will evaluate \p Pred on all instructions that read or write
892 /// to memory present in the information cache and return true if \p Pred
893 /// holds on all of them.
894 bool checkForAllReadWriteInstructions(
895 const llvm::function_ref<bool(Instruction &)> &Pred,
896 AbstractAttribute &QueryingAA);
898 /// Return the data layout associated with the anchor scope.
899 const DataLayout &getDataLayout() const { return InfoCache.DL; }
901 private:
902 /// Check \p Pred on all call sites of \p Fn.
904 /// This method will evaluate \p Pred on call sites and return
905 /// true if \p Pred holds in every call sites. However, this is only possible
906 /// all call sites are known, hence the function has internal linkage.
907 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
908 const Function &Fn, bool RequireAllCallSites,
909 const AbstractAttribute *QueryingAA);
911 /// The private version of getAAFor that allows to omit a querying abstract
912 /// attribute. See also the public getAAFor method.
913 template <typename AAType>
914 const AAType &getOrCreateAAFor(const IRPosition &IRP,
915 const AbstractAttribute *QueryingAA = nullptr,
916 bool TrackDependence = false) {
917 if (const AAType *AAPtr =
918 lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence))
919 return *AAPtr;
921 // No matching attribute found, create one.
922 // Use the static create method.
923 auto &AA = AAType::createForPosition(IRP, *this);
924 registerAA(AA);
926 // For now we ignore naked and optnone functions.
927 bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID);
928 if (const Function *Fn = IRP.getAnchorScope())
929 Invalidate |= Fn->hasFnAttribute(Attribute::Naked) ||
930 Fn->hasFnAttribute(Attribute::OptimizeNone);
932 // Bootstrap the new attribute with an initial update to propagate
933 // information, e.g., function -> call site. If it is not on a given
934 // whitelist we will not perform updates at all.
935 if (Invalidate) {
936 AA.getState().indicatePessimisticFixpoint();
937 return AA;
940 AA.initialize(*this);
941 AA.update(*this);
943 if (TrackDependence && AA.getState().isValidState())
944 QueryMap[&AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
945 return AA;
948 /// Return the attribute of \p AAType for \p IRP if existing.
949 template <typename AAType>
950 const AAType *lookupAAFor(const IRPosition &IRP,
951 const AbstractAttribute *QueryingAA = nullptr,
952 bool TrackDependence = false) {
953 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
954 "Cannot query an attribute with a type not derived from "
955 "'AbstractAttribute'!");
956 assert((QueryingAA || !TrackDependence) &&
957 "Cannot track dependences without a QueryingAA!");
959 // Lookup the abstract attribute of type AAType. If found, return it after
960 // registering a dependence of QueryingAA on the one returned attribute.
961 const auto &KindToAbstractAttributeMap = AAMap.lookup(IRP);
962 if (AAType *AA = static_cast<AAType *>(
963 KindToAbstractAttributeMap.lookup(&AAType::ID))) {
964 // Do not register a dependence on an attribute with an invalid state.
965 if (TrackDependence && AA->getState().isValidState())
966 QueryMap[AA].insert(const_cast<AbstractAttribute *>(QueryingAA));
967 return AA;
969 return nullptr;
972 /// The set of all abstract attributes.
973 ///{
974 using AAVector = SmallVector<AbstractAttribute *, 64>;
975 AAVector AllAbstractAttributes;
976 ///}
978 /// A nested map to lookup abstract attributes based on the argument position
979 /// on the outer level, and the addresses of the static member (AAType::ID) on
980 /// the inner level.
981 ///{
982 using KindToAbstractAttributeMap =
983 DenseMap<const char *, AbstractAttribute *>;
984 DenseMap<IRPosition, KindToAbstractAttributeMap> AAMap;
985 ///}
987 /// A map from abstract attributes to the ones that queried them through calls
988 /// to the getAAFor<...>(...) method.
989 ///{
990 using QueryMapTy =
991 MapVector<const AbstractAttribute *, SetVector<AbstractAttribute *>>;
992 QueryMapTy QueryMap;
993 ///}
995 /// The information cache that holds pre-processed (LLVM-IR) information.
996 InformationCache &InfoCache;
998 /// Number of iterations until the dependences between abstract attributes are
999 /// recomputed.
1000 const unsigned DepRecomputeInterval;
1002 /// If not null, a set limiting the attribute opportunities.
1003 const DenseSet<const char *> *Whitelist;
1005 /// A set to remember the functions we already assume to be live and visited.
1006 DenseSet<const Function *> VisitedFunctions;
1008 /// Functions, blocks, and instructions we delete after manifest is done.
1010 ///{
1011 SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
1012 SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
1013 SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
1014 ///}
1017 /// An interface to query the internal state of an abstract attribute.
1019 /// The abstract state is a minimal interface that allows the Attributor to
1020 /// communicate with the abstract attributes about their internal state without
1021 /// enforcing or exposing implementation details, e.g., the (existence of an)
1022 /// underlying lattice.
1024 /// It is sufficient to be able to query if a state is (1) valid or invalid, (2)
1025 /// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint
1026 /// was reached or (4) a pessimistic fixpoint was enforced.
1028 /// All methods need to be implemented by the subclass. For the common use case,
1029 /// a single boolean state or a bit-encoded state, the BooleanState and
1030 /// IntegerState classes are already provided. An abstract attribute can inherit
1031 /// from them to get the abstract state interface and additional methods to
1032 /// directly modify the state based if needed. See the class comments for help.
1033 struct AbstractState {
1034 virtual ~AbstractState() {}
1036 /// Return if this abstract state is in a valid state. If false, no
1037 /// information provided should be used.
1038 virtual bool isValidState() const = 0;
1040 /// Return if this abstract state is fixed, thus does not need to be updated
1041 /// if information changes as it cannot change itself.
1042 virtual bool isAtFixpoint() const = 0;
1044 /// Indicate that the abstract state should converge to the optimistic state.
1046 /// This will usually make the optimistically assumed state the known to be
1047 /// true state.
1049 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change.
1050 virtual ChangeStatus indicateOptimisticFixpoint() = 0;
1052 /// Indicate that the abstract state should converge to the pessimistic state.
1054 /// This will usually revert the optimistically assumed state to the known to
1055 /// be true state.
1057 /// \returns ChangeStatus::CHANGED as the assumed value may change.
1058 virtual ChangeStatus indicatePessimisticFixpoint() = 0;
1061 /// Simple state with integers encoding.
1063 /// The interface ensures that the assumed bits are always a subset of the known
1064 /// bits. Users can only add known bits and, except through adding known bits,
1065 /// they can only remove assumed bits. This should guarantee monotoniticy and
1066 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
1067 /// reached when the assumed and known state/bits are equal. Users can
1068 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
1069 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
1070 /// the other way around.
1071 struct IntegerState : public AbstractState {
1072 /// Underlying integer type, we assume 32 bits to be enough.
1073 using base_t = uint32_t;
1075 /// Initialize the (best) state.
1076 IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
1078 /// Return the worst possible representable state.
1079 static constexpr base_t getWorstState() { return 0; }
1081 /// See AbstractState::isValidState()
1082 /// NOTE: For now we simply pretend that the worst possible state is invalid.
1083 bool isValidState() const override { return Assumed != getWorstState(); }
1085 /// See AbstractState::isAtFixpoint()
1086 bool isAtFixpoint() const override { return Assumed == Known; }
1088 /// See AbstractState::indicateOptimisticFixpoint(...)
1089 ChangeStatus indicateOptimisticFixpoint() override {
1090 Known = Assumed;
1091 return ChangeStatus::UNCHANGED;
1094 /// See AbstractState::indicatePessimisticFixpoint(...)
1095 ChangeStatus indicatePessimisticFixpoint() override {
1096 Assumed = Known;
1097 return ChangeStatus::CHANGED;
1100 /// Return the known state encoding
1101 base_t getKnown() const { return Known; }
1103 /// Return the assumed state encoding.
1104 base_t getAssumed() const { return Assumed; }
1106 /// Return true if the bits set in \p BitsEncoding are "known bits".
1107 bool isKnown(base_t BitsEncoding) const {
1108 return (Known & BitsEncoding) == BitsEncoding;
1111 /// Return true if the bits set in \p BitsEncoding are "assumed bits".
1112 bool isAssumed(base_t BitsEncoding) const {
1113 return (Assumed & BitsEncoding) == BitsEncoding;
1116 /// Add the bits in \p BitsEncoding to the "known bits".
1117 IntegerState &addKnownBits(base_t Bits) {
1118 // Make sure we never miss any "known bits".
1119 Assumed |= Bits;
1120 Known |= Bits;
1121 return *this;
1124 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known.
1125 IntegerState &removeAssumedBits(base_t BitsEncoding) {
1126 // Make sure we never loose any "known bits".
1127 Assumed = (Assumed & ~BitsEncoding) | Known;
1128 return *this;
1131 /// Remove the bits in \p BitsEncoding from the "known bits".
1132 IntegerState &removeKnownBits(base_t BitsEncoding) {
1133 Known = (Known & ~BitsEncoding);
1134 return *this;
1137 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
1138 IntegerState &intersectAssumedBits(base_t BitsEncoding) {
1139 // Make sure we never loose any "known bits".
1140 Assumed = (Assumed & BitsEncoding) | Known;
1141 return *this;
1144 /// Take minimum of assumed and \p Value.
1145 IntegerState &takeAssumedMinimum(base_t Value) {
1146 // Make sure we never loose "known value".
1147 Assumed = std::max(std::min(Assumed, Value), Known);
1148 return *this;
1151 /// Take maximum of known and \p Value.
1152 IntegerState &takeKnownMaximum(base_t Value) {
1153 // Make sure we never loose "known value".
1154 Assumed = std::max(Value, Assumed);
1155 Known = std::max(Value, Known);
1156 return *this;
1159 /// Equality for IntegerState.
1160 bool operator==(const IntegerState &R) const {
1161 return this->getAssumed() == R.getAssumed() &&
1162 this->getKnown() == R.getKnown();
1165 /// Inequality for IntegerState.
1166 bool operator!=(const IntegerState &R) const { return !(*this == R); }
1168 /// "Clamp" this state with \p R. The result is the minimum of the assumed
1169 /// information but not less than what was known before.
1171 /// TODO: Consider replacing the operator with a call or using it only when
1172 /// we can also take the maximum of the known information, thus when
1173 /// \p R is not dependent on additional assumed state.
1174 IntegerState operator^=(const IntegerState &R) {
1175 takeAssumedMinimum(R.Assumed);
1176 return *this;
1179 /// "Clamp" this state with \p R. The result is the maximum of the known
1180 /// information but not more than what was assumed before.
1181 IntegerState operator+=(const IntegerState &R) {
1182 takeKnownMaximum(R.Known);
1183 return *this;
1186 /// Make this the minimum, known and assumed, of this state and \p R.
1187 IntegerState operator&=(const IntegerState &R) {
1188 Known = std::min(Known, R.Known);
1189 Assumed = std::min(Assumed, R.Assumed);
1190 return *this;
1193 /// Make this the maximum, known and assumed, of this state and \p R.
1194 IntegerState operator|=(const IntegerState &R) {
1195 Known = std::max(Known, R.Known);
1196 Assumed = std::max(Assumed, R.Assumed);
1197 return *this;
1200 private:
1201 /// The known state encoding in an integer of type base_t.
1202 base_t Known = getWorstState();
1204 /// The assumed state encoding in an integer of type base_t.
1205 base_t Assumed;
1208 /// Simple wrapper for a single bit (boolean) state.
1209 struct BooleanState : public IntegerState {
1210 BooleanState() : IntegerState(1){};
1213 /// Helper struct necessary as the modular build fails if the virtual method
1214 /// IRAttribute::manifest is defined in the Attributor.cpp.
1215 struct IRAttributeManifest {
1216 static ChangeStatus manifestAttrs(Attributor &A, IRPosition &IRP,
1217 const ArrayRef<Attribute> &DeducedAttrs);
1220 /// Helper to tie a abstract state implementation to an abstract attribute.
1221 template <typename StateTy, typename Base>
1222 struct StateWrapper : public StateTy, public Base {
1223 /// Provide static access to the type of the state.
1224 using StateType = StateTy;
1226 /// See AbstractAttribute::getState(...).
1227 StateType &getState() override { return *this; }
1229 /// See AbstractAttribute::getState(...).
1230 const AbstractState &getState() const override { return *this; }
1233 /// Helper class that provides common functionality to manifest IR attributes.
1234 template <Attribute::AttrKind AK, typename Base>
1235 struct IRAttribute : public IRPosition, public Base {
1236 IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
1237 ~IRAttribute() {}
1239 /// See AbstractAttribute::initialize(...).
1240 virtual void initialize(Attributor &A) override {
1241 if (hasAttr(getAttrKind())) {
1242 this->getState().indicateOptimisticFixpoint();
1243 return;
1246 const IRPosition &IRP = this->getIRPosition();
1247 bool IsFnInterface = IRP.isFnInterfaceKind();
1248 const Function *FnScope = IRP.getAnchorScope();
1249 // TODO: Not all attributes require an exact definition. Find a way to
1250 // enable deduction for some but not all attributes in case the
1251 // definition might be changed at runtime, see also
1252 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1253 // TODO: We could always determine abstract attributes and if sufficient
1254 // information was found we could duplicate the functions that do not
1255 // have an exact definition.
1256 if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
1257 this->getState().indicatePessimisticFixpoint();
1260 /// See AbstractAttribute::manifest(...).
1261 ChangeStatus manifest(Attributor &A) override {
1262 SmallVector<Attribute, 4> DeducedAttrs;
1263 getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs);
1264 return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs);
1267 /// Return the kind that identifies the abstract attribute implementation.
1268 Attribute::AttrKind getAttrKind() const { return AK; }
1270 /// Return the deduced attributes in \p Attrs.
1271 virtual void getDeducedAttributes(LLVMContext &Ctx,
1272 SmallVectorImpl<Attribute> &Attrs) const {
1273 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind()));
1276 /// Return an IR position, see struct IRPosition.
1278 ///{
1279 IRPosition &getIRPosition() override { return *this; }
1280 const IRPosition &getIRPosition() const override { return *this; }
1281 ///}
1284 /// Base struct for all "concrete attribute" deductions.
1286 /// The abstract attribute is a minimal interface that allows the Attributor to
1287 /// orchestrate the abstract/fixpoint analysis. The design allows to hide away
1288 /// implementation choices made for the subclasses but also to structure their
1289 /// implementation and simplify the use of other abstract attributes in-flight.
1291 /// To allow easy creation of new attributes, most methods have default
1292 /// implementations. The ones that do not are generally straight forward, except
1293 /// `AbstractAttribute::updateImpl` which is the location of most reasoning
1294 /// associated with the abstract attribute. The update is invoked by the
1295 /// Attributor in case the situation used to justify the current optimistic
1296 /// state might have changed. The Attributor determines this automatically
1297 /// by monitoring the `Attributor::getAAFor` calls made by abstract attributes.
1299 /// The `updateImpl` method should inspect the IR and other abstract attributes
1300 /// in-flight to justify the best possible (=optimistic) state. The actual
1301 /// implementation is, similar to the underlying abstract state encoding, not
1302 /// exposed. In the most common case, the `updateImpl` will go through a list of
1303 /// reasons why its optimistic state is valid given the current information. If
1304 /// any combination of them holds and is sufficient to justify the current
1305 /// optimistic state, the method shall return UNCHAGED. If not, the optimistic
1306 /// state is adjusted to the situation and the method shall return CHANGED.
1308 /// If the manifestation of the "concrete attribute" deduced by the subclass
1309 /// differs from the "default" behavior, which is a (set of) LLVM-IR
1310 /// attribute(s) for an argument, call site argument, function return value, or
1311 /// function, the `AbstractAttribute::manifest` method should be overloaded.
1313 /// NOTE: If the state obtained via getState() is INVALID, thus if
1314 /// AbstractAttribute::getState().isValidState() returns false, no
1315 /// information provided by the methods of this class should be used.
1316 /// NOTE: The Attributor currently has certain limitations to what we can do.
1317 /// As a general rule of thumb, "concrete" abstract attributes should *for
1318 /// now* only perform "backward" information propagation. That means
1319 /// optimistic information obtained through abstract attributes should
1320 /// only be used at positions that precede the origin of the information
1321 /// with regards to the program flow. More practically, information can
1322 /// *now* be propagated from instructions to their enclosing function, but
1323 /// *not* from call sites to the called function. The mechanisms to allow
1324 /// both directions will be added in the future.
1325 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
1326 /// described in the file comment.
1327 struct AbstractAttribute {
1328 using StateType = AbstractState;
1330 /// Virtual destructor.
1331 virtual ~AbstractAttribute() {}
1333 /// Initialize the state with the information in the Attributor \p A.
1335 /// This function is called by the Attributor once all abstract attributes
1336 /// have been identified. It can and shall be used for task like:
1337 /// - identify existing knowledge in the IR and use it for the "known state"
1338 /// - perform any work that is not going to change over time, e.g., determine
1339 /// a subset of the IR, or attributes in-flight, that have to be looked at
1340 /// in the `updateImpl` method.
1341 virtual void initialize(Attributor &A) {}
1343 /// Return the internal abstract state for inspection.
1344 virtual StateType &getState() = 0;
1345 virtual const StateType &getState() const = 0;
1347 /// Return an IR position, see struct IRPosition.
1348 virtual const IRPosition &getIRPosition() const = 0;
1350 /// Helper functions, for debug purposes only.
1351 ///{
1352 virtual void print(raw_ostream &OS) const;
1353 void dump() const { print(dbgs()); }
1355 /// This function should return the "summarized" assumed state as string.
1356 virtual const std::string getAsStr() const = 0;
1357 ///}
1359 /// Allow the Attributor access to the protected methods.
1360 friend struct Attributor;
1362 protected:
1363 /// Hook for the Attributor to trigger an update of the internal state.
1365 /// If this attribute is already fixed, this method will return UNCHANGED,
1366 /// otherwise it delegates to `AbstractAttribute::updateImpl`.
1368 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1369 ChangeStatus update(Attributor &A);
1371 /// Hook for the Attributor to trigger the manifestation of the information
1372 /// represented by the abstract attribute in the LLVM-IR.
1374 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED.
1375 virtual ChangeStatus manifest(Attributor &A) {
1376 return ChangeStatus::UNCHANGED;
1379 /// Hook to enable custom statistic tracking, called after manifest that
1380 /// resulted in a change if statistics are enabled.
1382 /// We require subclasses to provide an implementation so we remember to
1383 /// add statistics for them.
1384 virtual void trackStatistics() const = 0;
1386 /// Return an IR position, see struct IRPosition.
1387 virtual IRPosition &getIRPosition() = 0;
1389 /// The actual update/transfer function which has to be implemented by the
1390 /// derived classes.
1392 /// If it is called, the environment has changed and we have to determine if
1393 /// the current information is still valid or adjust it otherwise.
1395 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
1396 virtual ChangeStatus updateImpl(Attributor &A) = 0;
1399 /// Forward declarations of output streams for debug purposes.
1401 ///{
1402 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
1403 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
1404 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
1405 raw_ostream &operator<<(raw_ostream &OS, const IRPosition &);
1406 raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
1407 raw_ostream &operator<<(raw_ostream &OS, const IntegerState &S);
1408 ///}
1410 struct AttributorPass : public PassInfoMixin<AttributorPass> {
1411 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
1414 Pass *createAttributorLegacyPass();
1416 /// ----------------------------------------------------------------------------
1417 /// Abstract Attribute Classes
1418 /// ----------------------------------------------------------------------------
1420 /// An abstract attribute for the returned values of a function.
1421 struct AAReturnedValues
1422 : public IRAttribute<Attribute::Returned, AbstractAttribute> {
1423 AAReturnedValues(const IRPosition &IRP) : IRAttribute(IRP) {}
1425 /// Return an assumed unique return value if a single candidate is found. If
1426 /// there cannot be one, return a nullptr. If it is not clear yet, return the
1427 /// Optional::NoneType.
1428 Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
1430 /// Check \p Pred on all returned values.
1432 /// This method will evaluate \p Pred on returned values and return
1433 /// true if (1) all returned values are known, and (2) \p Pred returned true
1434 /// for all returned values.
1436 /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts
1437 /// method, this one will not filter dead return instructions.
1438 virtual bool checkForAllReturnedValuesAndReturnInsts(
1439 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)>
1440 &Pred) const = 0;
1442 using iterator =
1443 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::iterator;
1444 using const_iterator =
1445 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::const_iterator;
1446 virtual llvm::iterator_range<iterator> returned_values() = 0;
1447 virtual llvm::iterator_range<const_iterator> returned_values() const = 0;
1449 virtual size_t getNumReturnValues() const = 0;
1450 virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0;
1452 /// Create an abstract attribute view for the position \p IRP.
1453 static AAReturnedValues &createForPosition(const IRPosition &IRP,
1454 Attributor &A);
1456 /// Unique ID (due to the unique address)
1457 static const char ID;
1460 struct AANoUnwind
1461 : public IRAttribute<Attribute::NoUnwind,
1462 StateWrapper<BooleanState, AbstractAttribute>> {
1463 AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {}
1465 /// Returns true if nounwind is assumed.
1466 bool isAssumedNoUnwind() const { return getAssumed(); }
1468 /// Returns true if nounwind is known.
1469 bool isKnownNoUnwind() const { return getKnown(); }
1471 /// Create an abstract attribute view for the position \p IRP.
1472 static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A);
1474 /// Unique ID (due to the unique address)
1475 static const char ID;
1478 struct AANoSync
1479 : public IRAttribute<Attribute::NoSync,
1480 StateWrapper<BooleanState, AbstractAttribute>> {
1481 AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {}
1483 /// Returns true if "nosync" is assumed.
1484 bool isAssumedNoSync() const { return getAssumed(); }
1486 /// Returns true if "nosync" is known.
1487 bool isKnownNoSync() const { return getKnown(); }
1489 /// Create an abstract attribute view for the position \p IRP.
1490 static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A);
1492 /// Unique ID (due to the unique address)
1493 static const char ID;
1496 /// An abstract interface for all nonnull attributes.
1497 struct AANonNull
1498 : public IRAttribute<Attribute::NonNull,
1499 StateWrapper<BooleanState, AbstractAttribute>> {
1500 AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {}
1502 /// Return true if we assume that the underlying value is nonnull.
1503 bool isAssumedNonNull() const { return getAssumed(); }
1505 /// Return true if we know that underlying value is nonnull.
1506 bool isKnownNonNull() const { return getKnown(); }
1508 /// Create an abstract attribute view for the position \p IRP.
1509 static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A);
1511 /// Unique ID (due to the unique address)
1512 static const char ID;
1515 /// An abstract attribute for norecurse.
1516 struct AANoRecurse
1517 : public IRAttribute<Attribute::NoRecurse,
1518 StateWrapper<BooleanState, AbstractAttribute>> {
1519 AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {}
1521 /// Return true if "norecurse" is assumed.
1522 bool isAssumedNoRecurse() const { return getAssumed(); }
1524 /// Return true if "norecurse" is known.
1525 bool isKnownNoRecurse() const { return getKnown(); }
1527 /// Create an abstract attribute view for the position \p IRP.
1528 static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A);
1530 /// Unique ID (due to the unique address)
1531 static const char ID;
1534 /// An abstract attribute for willreturn.
1535 struct AAWillReturn
1536 : public IRAttribute<Attribute::WillReturn,
1537 StateWrapper<BooleanState, AbstractAttribute>> {
1538 AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1540 /// Return true if "willreturn" is assumed.
1541 bool isAssumedWillReturn() const { return getAssumed(); }
1543 /// Return true if "willreturn" is known.
1544 bool isKnownWillReturn() const { return getKnown(); }
1546 /// Create an abstract attribute view for the position \p IRP.
1547 static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1549 /// Unique ID (due to the unique address)
1550 static const char ID;
1553 /// An abstract interface for all noalias attributes.
1554 struct AANoAlias
1555 : public IRAttribute<Attribute::NoAlias,
1556 StateWrapper<BooleanState, AbstractAttribute>> {
1557 AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {}
1559 /// Return true if we assume that the underlying value is alias.
1560 bool isAssumedNoAlias() const { return getAssumed(); }
1562 /// Return true if we know that underlying value is noalias.
1563 bool isKnownNoAlias() const { return getKnown(); }
1565 /// Create an abstract attribute view for the position \p IRP.
1566 static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A);
1568 /// Unique ID (due to the unique address)
1569 static const char ID;
1572 /// An AbstractAttribute for nofree.
1573 struct AANoFree
1574 : public IRAttribute<Attribute::NoFree,
1575 StateWrapper<BooleanState, AbstractAttribute>> {
1576 AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {}
1578 /// Return true if "nofree" is assumed.
1579 bool isAssumedNoFree() const { return getAssumed(); }
1581 /// Return true if "nofree" is known.
1582 bool isKnownNoFree() const { return getKnown(); }
1584 /// Create an abstract attribute view for the position \p IRP.
1585 static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A);
1587 /// Unique ID (due to the unique address)
1588 static const char ID;
1591 /// An AbstractAttribute for noreturn.
1592 struct AANoReturn
1593 : public IRAttribute<Attribute::NoReturn,
1594 StateWrapper<BooleanState, AbstractAttribute>> {
1595 AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {}
1597 /// Return true if the underlying object is assumed to never return.
1598 bool isAssumedNoReturn() const { return getAssumed(); }
1600 /// Return true if the underlying object is known to never return.
1601 bool isKnownNoReturn() const { return getKnown(); }
1603 /// Create an abstract attribute view for the position \p IRP.
1604 static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A);
1606 /// Unique ID (due to the unique address)
1607 static const char ID;
1610 /// An abstract interface for liveness abstract attribute.
1611 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>,
1612 public IRPosition {
1613 AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {}
1615 /// Returns true if \p BB is assumed dead.
1616 virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
1618 /// Returns true if \p BB is known dead.
1619 virtual bool isKnownDead(const BasicBlock *BB) const = 0;
1621 /// Returns true if \p I is assumed dead.
1622 virtual bool isAssumedDead(const Instruction *I) const = 0;
1624 /// Returns true if \p I is known dead.
1625 virtual bool isKnownDead(const Instruction *I) const = 0;
1627 /// This method is used to check if at least one instruction in a collection
1628 /// of instructions is live.
1629 template <typename T> bool isLiveInstSet(T begin, T end) const {
1630 for (const auto &I : llvm::make_range(begin, end)) {
1631 assert(I->getFunction() == getIRPosition().getAssociatedFunction() &&
1632 "Instruction must be in the same anchor scope function.");
1634 if (!isAssumedDead(I))
1635 return true;
1638 return false;
1641 /// Return an IR position, see struct IRPosition.
1643 ///{
1644 IRPosition &getIRPosition() override { return *this; }
1645 const IRPosition &getIRPosition() const override { return *this; }
1646 ///}
1648 /// Create an abstract attribute view for the position \p IRP.
1649 static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A);
1651 /// Unique ID (due to the unique address)
1652 static const char ID;
1655 /// State for dereferenceable attribute
1656 struct DerefState : AbstractState {
1658 /// State representing for dereferenceable bytes.
1659 IntegerState DerefBytesState;
1661 /// State representing that whether the value is globaly dereferenceable.
1662 BooleanState GlobalState;
1664 /// See AbstractState::isValidState()
1665 bool isValidState() const override { return DerefBytesState.isValidState(); }
1667 /// See AbstractState::isAtFixpoint()
1668 bool isAtFixpoint() const override {
1669 return !isValidState() ||
1670 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
1673 /// See AbstractState::indicateOptimisticFixpoint(...)
1674 ChangeStatus indicateOptimisticFixpoint() override {
1675 DerefBytesState.indicateOptimisticFixpoint();
1676 GlobalState.indicateOptimisticFixpoint();
1677 return ChangeStatus::UNCHANGED;
1680 /// See AbstractState::indicatePessimisticFixpoint(...)
1681 ChangeStatus indicatePessimisticFixpoint() override {
1682 DerefBytesState.indicatePessimisticFixpoint();
1683 GlobalState.indicatePessimisticFixpoint();
1684 return ChangeStatus::CHANGED;
1687 /// Update known dereferenceable bytes.
1688 void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1689 DerefBytesState.takeKnownMaximum(Bytes);
1692 /// Update assumed dereferenceable bytes.
1693 void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1694 DerefBytesState.takeAssumedMinimum(Bytes);
1697 /// Equality for DerefState.
1698 bool operator==(const DerefState &R) {
1699 return this->DerefBytesState == R.DerefBytesState &&
1700 this->GlobalState == R.GlobalState;
1703 /// Inequality for IntegerState.
1704 bool operator!=(const DerefState &R) { return !(*this == R); }
1706 /// See IntegerState::operator^=
1707 DerefState operator^=(const DerefState &R) {
1708 DerefBytesState ^= R.DerefBytesState;
1709 GlobalState ^= R.GlobalState;
1710 return *this;
1713 /// See IntegerState::operator+=
1714 DerefState operator+=(const DerefState &R) {
1715 DerefBytesState += R.DerefBytesState;
1716 GlobalState += R.GlobalState;
1717 return *this;
1720 /// See IntegerState::operator&=
1721 DerefState operator&=(const DerefState &R) {
1722 DerefBytesState &= R.DerefBytesState;
1723 GlobalState &= R.GlobalState;
1724 return *this;
1727 /// See IntegerState::operator|=
1728 DerefState operator|=(const DerefState &R) {
1729 DerefBytesState |= R.DerefBytesState;
1730 GlobalState |= R.GlobalState;
1731 return *this;
1734 protected:
1735 const AANonNull *NonNullAA = nullptr;
1738 /// An abstract interface for all dereferenceable attribute.
1739 struct AADereferenceable
1740 : public IRAttribute<Attribute::Dereferenceable,
1741 StateWrapper<DerefState, AbstractAttribute>> {
1742 AADereferenceable(const IRPosition &IRP) : IRAttribute(IRP) {}
1744 /// Return true if we assume that the underlying value is nonnull.
1745 bool isAssumedNonNull() const {
1746 return NonNullAA && NonNullAA->isAssumedNonNull();
1749 /// Return true if we know that the underlying value is nonnull.
1750 bool isKnownNonNull() const {
1751 return NonNullAA && NonNullAA->isKnownNonNull();
1754 /// Return true if we assume that underlying value is
1755 /// dereferenceable(_or_null) globally.
1756 bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
1758 /// Return true if we know that underlying value is
1759 /// dereferenceable(_or_null) globally.
1760 bool isKnownGlobal() const { return GlobalState.getKnown(); }
1762 /// Return assumed dereferenceable bytes.
1763 uint32_t getAssumedDereferenceableBytes() const {
1764 return DerefBytesState.getAssumed();
1767 /// Return known dereferenceable bytes.
1768 uint32_t getKnownDereferenceableBytes() const {
1769 return DerefBytesState.getKnown();
1772 /// Create an abstract attribute view for the position \p IRP.
1773 static AADereferenceable &createForPosition(const IRPosition &IRP,
1774 Attributor &A);
1776 /// Unique ID (due to the unique address)
1777 static const char ID;
1780 /// An abstract interface for all align attributes.
1781 struct AAAlign
1782 : public IRAttribute<Attribute::Alignment,
1783 StateWrapper<IntegerState, AbstractAttribute>> {
1784 AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {}
1786 /// Return assumed alignment.
1787 unsigned getAssumedAlign() const { return getAssumed(); }
1789 /// Return known alignemnt.
1790 unsigned getKnownAlign() const { return getKnown(); }
1792 /// Create an abstract attribute view for the position \p IRP.
1793 static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A);
1795 /// Unique ID (due to the unique address)
1796 static const char ID;
1799 /// An abstract interface for all nocapture attributes.
1800 struct AANoCapture
1801 : public IRAttribute<Attribute::NoCapture,
1802 StateWrapper<IntegerState, AbstractAttribute>> {
1803 AANoCapture(const IRPosition &IRP) : IRAttribute(IRP) {}
1805 /// State encoding bits. A set bit in the state means the property holds.
1806 /// NO_CAPTURE is the best possible state, 0 the worst possible state.
1807 enum {
1808 NOT_CAPTURED_IN_MEM = 1 << 0,
1809 NOT_CAPTURED_IN_INT = 1 << 1,
1810 NOT_CAPTURED_IN_RET = 1 << 2,
1812 /// If we do not capture the value in memory or through integers we can only
1813 /// communicate it back as a derived pointer.
1814 NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT,
1816 /// If we do not capture the value in memory, through integers, or as a
1817 /// derived pointer we know it is not captured.
1818 NO_CAPTURE =
1819 NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET,
1822 /// Return true if we know that the underlying value is not captured in its
1823 /// respective scope.
1824 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); }
1826 /// Return true if we assume that the underlying value is not captured in its
1827 /// respective scope.
1828 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); }
1830 /// Return true if we know that the underlying value is not captured in its
1831 /// respective scope but we allow it to escape through a "return".
1832 bool isKnownNoCaptureMaybeReturned() const {
1833 return isKnown(NO_CAPTURE_MAYBE_RETURNED);
1836 /// Return true if we assume that the underlying value is not captured in its
1837 /// respective scope but we allow it to escape through a "return".
1838 bool isAssumedNoCaptureMaybeReturned() const {
1839 return isAssumed(NO_CAPTURE_MAYBE_RETURNED);
1842 /// Create an abstract attribute view for the position \p IRP.
1843 static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A);
1845 /// Unique ID (due to the unique address)
1846 static const char ID;
1849 /// An abstract interface for value simplify abstract attribute.
1850 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
1851 public IRPosition {
1852 AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {}
1854 /// Return an IR position, see struct IRPosition.
1856 ///{
1857 IRPosition &getIRPosition() { return *this; }
1858 const IRPosition &getIRPosition() const { return *this; }
1859 ///}
1861 /// Return an assumed simplified value if a single candidate is found. If
1862 /// there cannot be one, return original value. If it is not clear yet, return
1863 /// the Optional::NoneType.
1864 virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
1866 /// Create an abstract attribute view for the position \p IRP.
1867 static AAValueSimplify &createForPosition(const IRPosition &IRP,
1868 Attributor &A);
1870 /// Unique ID (due to the unique address)
1871 static const char ID;
1874 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>,
1875 public IRPosition {
1876 AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {}
1878 /// Returns true if HeapToStack conversion is assumed to be possible.
1879 bool isAssumedHeapToStack() const { return getAssumed(); }
1881 /// Returns true if HeapToStack conversion is known to be possible.
1882 bool isKnownHeapToStack() const { return getKnown(); }
1884 /// Return an IR position, see struct IRPosition.
1886 ///{
1887 IRPosition &getIRPosition() { return *this; }
1888 const IRPosition &getIRPosition() const { return *this; }
1889 ///}
1891 /// Create an abstract attribute view for the position \p IRP.
1892 static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
1894 /// Unique ID (due to the unique address)
1895 static const char ID;
1898 /// An abstract interface for all memory related attributes.
1899 struct AAMemoryBehavior
1900 : public IRAttribute<Attribute::ReadNone,
1901 StateWrapper<IntegerState, AbstractAttribute>> {
1902 AAMemoryBehavior(const IRPosition &IRP) : IRAttribute(IRP) {}
1904 /// State encoding bits. A set bit in the state means the property holds.
1905 /// BEST_STATE is the best possible state, 0 the worst possible state.
1906 enum {
1907 NO_READS = 1 << 0,
1908 NO_WRITES = 1 << 1,
1909 NO_ACCESSES = NO_READS | NO_WRITES,
1911 BEST_STATE = NO_ACCESSES,
1914 /// Return true if we know that the underlying value is not read or accessed
1915 /// in its respective scope.
1916 bool isKnownReadNone() const { return isKnown(NO_ACCESSES); }
1918 /// Return true if we assume that the underlying value is not read or accessed
1919 /// in its respective scope.
1920 bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); }
1922 /// Return true if we know that the underlying value is not accessed
1923 /// (=written) in its respective scope.
1924 bool isKnownReadOnly() const { return isKnown(NO_WRITES); }
1926 /// Return true if we assume that the underlying value is not accessed
1927 /// (=written) in its respective scope.
1928 bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); }
1930 /// Return true if we know that the underlying value is not read in its
1931 /// respective scope.
1932 bool isKnownWriteOnly() const { return isKnown(NO_READS); }
1934 /// Return true if we assume that the underlying value is not read in its
1935 /// respective scope.
1936 bool isAssumedWriteOnly() const { return isAssumed(NO_READS); }
1938 /// Create an abstract attribute view for the position \p IRP.
1939 static AAMemoryBehavior &createForPosition(const IRPosition &IRP,
1940 Attributor &A);
1942 /// Unique ID (due to the unique address)
1943 static const char ID;
1946 } // end namespace llvm
1948 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H