1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements an inter procedural pass that deduces and/or propagating
10 // attributes. This is done in an abstract interpretation style fixpoint
11 // iteration. See the Attributor.h file comment and the class descriptions in
12 // that file for more information.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Transforms/IPO/Attributor.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/GlobalsModRef.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/IR/Argument.h"
26 #include "llvm/IR/Attributes.h"
27 #include "llvm/IR/CFG.h"
28 #include "llvm/IR/InstIterator.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
37 #define DEBUG_TYPE "attributor"
39 STATISTIC(NumFnWithExactDefinition,
40 "Number of function with exact definitions");
41 STATISTIC(NumFnWithoutExactDefinition,
42 "Number of function without exact definitions");
43 STATISTIC(NumAttributesTimedOut,
44 "Number of abstract attributes timed out before fixpoint");
45 STATISTIC(NumAttributesValidFixpoint,
46 "Number of abstract attributes in a valid fixpoint state");
47 STATISTIC(NumAttributesManifested,
48 "Number of abstract attributes manifested in IR");
49 STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind");
51 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
52 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
53 STATISTIC(NumFnArgumentReturned,
54 "Number of function arguments marked returned");
55 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
56 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
57 STATISTIC(NumFnReturnedNonNull,
58 "Number of function return values marked nonnull");
59 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
60 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
61 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
63 // TODO: Determine a good default value.
65 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
66 // (when run with the first 5 abstract attributes). The results also indicate
67 // that we never reach 32 iterations but always find a fixpoint sooner.
69 // This will become more evolved once we perform two interleaved fixpoint
70 // iterations: bottom-up and top-down.
71 static cl::opt<unsigned>
72 MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
73 cl::desc("Maximal number of fixpoint iterations."),
76 static cl::opt<bool> DisableAttributor(
77 "attributor-disable", cl::Hidden,
78 cl::desc("Disable the attributor inter-procedural deduction pass."),
81 static cl::opt<bool> VerifyAttributor(
82 "attributor-verify", cl::Hidden,
83 cl::desc("Verify the Attributor deduction and "
84 "manifestation of attributes -- may issue false-positive errors"),
87 /// Logic operators for the change status enum class.
90 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
91 return l == ChangeStatus::CHANGED ? l : r;
93 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
94 return l == ChangeStatus::UNCHANGED ? l : r;
98 /// Helper to adjust the statistics.
99 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
100 const Attribute &Attr) {
101 if (!AreStatisticsEnabled())
104 if (!Attr.isEnumAttribute())
106 switch (Attr.getKindAsEnum()) {
107 case Attribute::NoUnwind:
110 case Attribute::Returned:
111 NumFnArgumentReturned++;
113 case Attribute::NoSync:
116 case Attribute::NoFree:
119 case Attribute::NonNull:
121 case AbstractAttribute::MP_RETURNED:
122 NumFnReturnedNonNull++;
124 case AbstractAttribute::MP_ARGUMENT:
125 NumFnArgumentNonNull++;
127 case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
128 NumCSArgumentNonNull++;
134 case Attribute::WillReturn:
142 template <typename StateTy>
143 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
144 template <typename StateTy>
145 using visitValueCB_t = std::function<void(Value *, StateTy &State)>;
147 /// Recursively visit all values that might become \p InitV at some point. This
148 /// will be done by looking through cast instructions, selects, phis, and calls
149 /// with the "returned" attribute. The callback \p FollowValueCB is asked before
150 /// a potential origin value is looked at. If no \p FollowValueCB is passed, a
151 /// default one is used that will make sure we visit every value only once. Once
152 /// we cannot look through the value any further, the callback \p VisitValueCB
153 /// is invoked and passed the current value and the \p State. To limit how much
154 /// effort is invested, we will never visit more than \p MaxValues values.
155 template <typename StateTy>
156 static bool genericValueTraversal(
157 Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
158 followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
160 SmallPtrSet<Value *, 16> Visited;
161 followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
162 return Visited.insert(Val).second;
166 FollowValueCB = &DefaultFollowValueCB;
168 SmallVector<Value *, 16> Worklist;
169 Worklist.push_back(InitV);
173 Value *V = Worklist.pop_back_val();
175 // Check if we should process the current value. To prevent endless
176 // recursion keep a record of the values we followed!
177 if (!(*FollowValueCB)(V, State))
180 // Make sure we limit the compile time for complex expressions.
181 if (Iteration++ >= MaxValues)
184 // Explicitly look through calls with a "returned" attribute if we do
185 // not have a pointer as stripPointerCasts only works on them.
186 if (V->getType()->isPointerTy()) {
187 V = V->stripPointerCasts();
190 if (CS && CS.getCalledFunction()) {
191 Value *NewV = nullptr;
192 for (Argument &Arg : CS.getCalledFunction()->args())
193 if (Arg.hasReturnedAttr()) {
194 NewV = CS.getArgOperand(Arg.getArgNo());
198 Worklist.push_back(NewV);
204 // Look through select instructions, visit both potential values.
205 if (auto *SI = dyn_cast<SelectInst>(V)) {
206 Worklist.push_back(SI->getTrueValue());
207 Worklist.push_back(SI->getFalseValue());
211 // Look through phi nodes, visit all operands.
212 if (auto *PHI = dyn_cast<PHINode>(V)) {
213 Worklist.append(PHI->op_begin(), PHI->op_end());
217 // Once a leaf is reached we inform the user through the callback.
218 VisitValueCB(V, State);
219 } while (!Worklist.empty());
221 // All values have been visited.
225 /// Helper to identify the correct offset into an attribute list.
226 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
227 unsigned ArgNo = 0) {
229 case AbstractAttribute::MP_ARGUMENT:
230 case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
231 return ArgNo + AttributeList::FirstArgIndex;
232 case AbstractAttribute::MP_FUNCTION:
233 return AttributeList::FunctionIndex;
234 case AbstractAttribute::MP_RETURNED:
235 return AttributeList::ReturnIndex;
237 llvm_unreachable("Unknown manifest position!");
240 /// Return true if \p New is equal or worse than \p Old.
241 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
242 if (!Old.isIntAttribute())
245 return Old.getValueAsInt() >= New.getValueAsInt();
248 /// Return true if the information provided by \p Attr was added to the
249 /// attribute list \p Attrs. This is only the case if it was not already present
250 /// in \p Attrs at the position describe by \p MP and \p ArgNo.
251 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
252 AttributeList &Attrs,
253 AbstractAttribute::ManifestPosition MP,
254 unsigned ArgNo = 0) {
255 unsigned AttrIdx = getAttrIndex(MP, ArgNo);
257 if (Attr.isEnumAttribute()) {
258 Attribute::AttrKind Kind = Attr.getKindAsEnum();
259 if (Attrs.hasAttribute(AttrIdx, Kind))
260 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
262 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
265 if (Attr.isStringAttribute()) {
266 StringRef Kind = Attr.getKindAsString();
267 if (Attrs.hasAttribute(AttrIdx, Kind))
268 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
270 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
274 llvm_unreachable("Expected enum or string attribute!");
277 ChangeStatus AbstractAttribute::update(Attributor &A) {
278 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
279 if (getState().isAtFixpoint())
282 LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
284 HasChanged = updateImpl(A);
286 LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
292 ChangeStatus AbstractAttribute::manifest(Attributor &A) {
293 assert(getState().isValidState() &&
294 "Attempted to manifest an invalid state!");
295 assert(getAssociatedValue() &&
296 "Attempted to manifest an attribute without associated value!");
298 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
299 SmallVector<Attribute, 4> DeducedAttrs;
300 getDeducedAttributes(DeducedAttrs);
302 Function &ScopeFn = getAnchorScope();
303 LLVMContext &Ctx = ScopeFn.getContext();
304 ManifestPosition MP = getManifestPosition();
307 SmallVector<unsigned, 4> ArgNos;
309 // In the following some generic code that will manifest attributes in
310 // DeducedAttrs if they improve the current IR. Due to the different
311 // annotation positions we use the underlying AttributeList interface.
312 // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
316 ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
317 Attrs = ScopeFn.getAttributes();
322 Attrs = ScopeFn.getAttributes();
324 case MP_CALL_SITE_ARGUMENT: {
325 CallSite CS(&getAnchoredValue());
326 for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
327 if (CS.getArgOperand(u) == getAssociatedValue())
329 Attrs = CS.getAttributes();
333 for (const Attribute &Attr : DeducedAttrs) {
334 for (unsigned ArgNo : ArgNos) {
335 if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
338 HasChanged = ChangeStatus::CHANGED;
339 bookkeeping(MP, Attr);
343 if (HasChanged == ChangeStatus::UNCHANGED)
350 ScopeFn.setAttributes(Attrs);
352 case MP_CALL_SITE_ARGUMENT:
353 CallSite(&getAnchoredValue()).setAttributes(Attrs);
359 Function &AbstractAttribute::getAnchorScope() {
360 Value &V = getAnchoredValue();
361 if (isa<Function>(V))
362 return cast<Function>(V);
363 if (isa<Argument>(V))
364 return *cast<Argument>(V).getParent();
365 if (isa<Instruction>(V))
366 return *cast<Instruction>(V).getFunction();
367 llvm_unreachable("No scope for anchored value found!");
370 const Function &AbstractAttribute::getAnchorScope() const {
371 return const_cast<AbstractAttribute *>(this)->getAnchorScope();
374 /// -----------------------NoUnwind Function Attribute--------------------------
376 struct AANoUnwindFunction : AANoUnwind, BooleanState {
378 AANoUnwindFunction(Function &F, InformationCache &InfoCache)
379 : AANoUnwind(F, InfoCache) {}
381 /// See AbstractAttribute::getState()
383 AbstractState &getState() override { return *this; }
384 const AbstractState &getState() const override { return *this; }
387 /// See AbstractAttribute::getManifestPosition().
388 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
390 const std::string getAsStr() const override {
391 return getAssumed() ? "nounwind" : "may-unwind";
394 /// See AbstractAttribute::updateImpl(...).
395 ChangeStatus updateImpl(Attributor &A) override;
397 /// See AANoUnwind::isAssumedNoUnwind().
398 bool isAssumedNoUnwind() const override { return getAssumed(); }
400 /// See AANoUnwind::isKnownNoUnwind().
401 bool isKnownNoUnwind() const override { return getKnown(); }
404 ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
405 Function &F = getAnchorScope();
407 // The map from instruction opcodes to those instructions in the function.
408 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
410 (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
411 (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
412 (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
414 for (unsigned Opcode : Opcodes) {
415 for (Instruction *I : OpcodeInstMap[Opcode]) {
419 auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
421 if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
422 indicatePessimisticFixpoint();
423 return ChangeStatus::CHANGED;
427 return ChangeStatus::UNCHANGED;
430 /// --------------------- Function Return Values -------------------------------
432 /// "Attribute" that collects all potential returned values and the return
433 /// instructions that they arise from.
435 /// If there is a unique returned value R, the manifest method will:
436 /// - mark R with the "returned" attribute, if R is an argument.
437 class AAReturnedValuesImpl final : public AAReturnedValues, AbstractState {
439 /// Mapping of values potentially returned by the associated function to the
440 /// return instructions that might return them.
441 DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> ReturnedValues;
448 bool HasOverdefinedReturnedCalls;
451 /// Collect values that could become \p V in the set \p Values, each mapped to
453 void collectValuesRecursively(
454 Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
455 DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> &Values) {
457 visitValueCB_t<bool> VisitValueCB = [&](Value *Val, bool &) {
458 assert(!isa<Instruction>(Val) ||
459 &getAnchorScope() == cast<Instruction>(Val)->getFunction());
460 Values[Val].insert(ReturnInsts.begin(), ReturnInsts.end());
464 bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
466 // If we did abort the above traversal we haven't see all the values.
467 // Consequently, we cannot know if the information we would derive is
468 // accurate so we give up early.
470 indicatePessimisticFixpoint();
474 /// See AbstractAttribute::AbstractAttribute(...).
475 AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
476 : AAReturnedValues(F, InfoCache) {
477 // We do not have an associated argument yet.
478 AssociatedVal = nullptr;
481 /// See AbstractAttribute::initialize(...).
482 void initialize(Attributor &A) override {
484 AssociatedVal = nullptr;
487 HasOverdefinedReturnedCalls = false;
488 ReturnedValues.clear();
490 Function &F = cast<Function>(getAnchoredValue());
492 // The map from instruction opcodes to those instructions in the function.
493 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
495 // Look through all arguments, if one is marked as returned we are done.
496 for (Argument &Arg : F.args()) {
497 if (Arg.hasReturnedAttr()) {
499 auto &ReturnInstSet = ReturnedValues[&Arg];
500 for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
501 ReturnInstSet.insert(cast<ReturnInst>(RI));
503 indicateOptimisticFixpoint();
508 // If no argument was marked as returned we look at all return instructions
509 // and collect potentially returned values.
510 for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) {
511 SmallPtrSet<ReturnInst *, 1> RISet({cast<ReturnInst>(RI)});
512 collectValuesRecursively(A, cast<ReturnInst>(RI)->getReturnValue(), RISet,
517 /// See AbstractAttribute::manifest(...).
518 ChangeStatus manifest(Attributor &A) override;
520 /// See AbstractAttribute::getState(...).
521 AbstractState &getState() override { return *this; }
523 /// See AbstractAttribute::getState(...).
524 const AbstractState &getState() const override { return *this; }
526 /// See AbstractAttribute::getManifestPosition().
527 ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
529 /// See AbstractAttribute::updateImpl(Attributor &A).
530 ChangeStatus updateImpl(Attributor &A) override;
532 /// Return the number of potential return values, -1 if unknown.
533 size_t getNumReturnValues() const {
534 return isValidState() ? ReturnedValues.size() : -1;
537 /// Return an assumed unique return value if a single candidate is found. If
538 /// there cannot be one, return a nullptr. If it is not clear yet, return the
539 /// Optional::NoneType.
540 Optional<Value *> getAssumedUniqueReturnValue() const;
542 /// See AbstractState::checkForallReturnedValues(...).
544 checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
546 /// Pretty print the attribute similar to the IR representation.
547 const std::string getAsStr() const override;
549 /// See AbstractState::isAtFixpoint().
550 bool isAtFixpoint() const override { return IsFixed; }
552 /// See AbstractState::isValidState().
553 bool isValidState() const override { return IsValidState; }
555 /// See AbstractState::indicateOptimisticFixpoint(...).
556 void indicateOptimisticFixpoint() override {
558 IsValidState &= true;
560 void indicatePessimisticFixpoint() override {
562 IsValidState = false;
566 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
567 ChangeStatus Changed = ChangeStatus::UNCHANGED;
570 assert(isValidState());
573 // Check if we have an assumed unique return value that we could manifest.
574 Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
576 if (!UniqueRV.hasValue() || !UniqueRV.getValue())
580 NumFnUniqueReturned++;
582 // If the assumed unique return value is an argument, annotate it.
583 if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
584 AssociatedVal = UniqueRVArg;
585 Changed = AbstractAttribute::manifest(A) | Changed;
591 const std::string AAReturnedValuesImpl::getAsStr() const {
592 return (isAtFixpoint() ? "returns(#" : "may-return(#") +
593 (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
596 Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue() const {
597 // If checkForallReturnedValues provides a unique value, ignoring potential
598 // undef values that can also be present, it is assumed to be the actual
599 // return value and forwarded to the caller of this method. If there are
600 // multiple, a nullptr is returned indicating there cannot be a unique
602 Optional<Value *> UniqueRV;
604 std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
605 // If we found a second returned value and neither the current nor the saved
606 // one is an undef, there is no unique returned value. Undefs are special
607 // since we can pretend they have any value.
608 if (UniqueRV.hasValue() && UniqueRV != &RV &&
609 !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
614 // Do not overwrite a value with an undef.
615 if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
621 if (!checkForallReturnedValues(Pred))
627 bool AAReturnedValuesImpl::checkForallReturnedValues(
628 std::function<bool(Value &)> &Pred) const {
632 // Check all returned values but ignore call sites as long as we have not
633 // encountered an overdefined one during an update.
634 for (auto &It : ReturnedValues) {
635 Value *RV = It.first;
637 ImmutableCallSite ICS(RV);
638 if (ICS && !HasOverdefinedReturnedCalls)
648 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
650 // Check if we know of any values returned by the associated function,
651 // if not, we are done.
652 if (getNumReturnValues() == 0) {
653 indicateOptimisticFixpoint();
654 return ChangeStatus::UNCHANGED;
657 // Check if any of the returned values is a call site we can refine.
658 decltype(ReturnedValues) AddRVs;
659 bool HasCallSite = false;
661 // Look at all returned call sites.
662 for (auto &It : ReturnedValues) {
663 SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
664 Value *RV = It.first;
665 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
668 // Only call sites can change during an update, ignore the rest.
673 // For now, any call site we see will prevent us from directly fixing the
674 // state. However, if the information on the callees is fixed, the call
675 // sites will be removed and we will fix the information for this state.
678 // Try to find a assumed unique return value for the called function.
679 auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
681 HasOverdefinedReturnedCalls = true;
682 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
683 << ") with " << (RetCSAA ? "invalid" : "no")
684 << " associated state\n");
688 // Try to find a assumed unique return value for the called function.
689 Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
691 // If no assumed unique return value was found due to the lack of
692 // candidates, we may need to resolve more calls (through more update
693 // iterations) or the called function will not return. Either way, we simply
694 // stick with the call sites as return values. Because there were not
695 // multiple possibilities, we do not treat it as overdefined.
696 if (!AssumedUniqueRV.hasValue())
699 // If multiple, non-refinable values were found, there cannot be a unique
700 // return value for the called function. The returned call is overdefined!
701 if (!AssumedUniqueRV.getValue()) {
702 HasOverdefinedReturnedCalls = true;
703 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
704 "potentially returned values\n");
709 bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
710 dbgs() << "[AAReturnedValues] Returned call site "
711 << (UniqueRVIsKnown ? "known" : "assumed")
712 << " unique return value: " << *AssumedUniqueRV << "\n";
715 // The assumed unique return value.
716 Value *AssumedRetVal = AssumedUniqueRV.getValue();
718 // If the assumed unique return value is an argument, lookup the matching
719 // call site operand and recursively collect new returned values.
720 // If it is not an argument, it is just put into the set of returned values
721 // as we would have already looked through casts, phis, and similar values.
722 if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
723 collectValuesRecursively(A,
724 RetCS.getArgOperand(AssumedRetArg->getArgNo()),
725 ReturnInsts, AddRVs);
727 AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
730 // Keep track of any change to trigger updates on dependent attributes.
731 ChangeStatus Changed = ChangeStatus::UNCHANGED;
733 for (auto &It : AddRVs) {
734 assert(!It.second.empty() && "Entry does not add anything.");
735 auto &ReturnInsts = ReturnedValues[It.first];
736 for (ReturnInst *RI : It.second)
737 if (ReturnInsts.insert(RI).second) {
738 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
739 << *It.first << " => " << *RI << "\n");
740 Changed = ChangeStatus::CHANGED;
744 // If there is no call site in the returned values we are done.
746 indicateOptimisticFixpoint();
747 return ChangeStatus::CHANGED;
753 /// ------------------------ NoSync Function Attribute -------------------------
755 struct AANoSyncFunction : AANoSync, BooleanState {
757 AANoSyncFunction(Function &F, InformationCache &InfoCache)
758 : AANoSync(F, InfoCache) {}
760 /// See AbstractAttribute::getState()
762 AbstractState &getState() override { return *this; }
763 const AbstractState &getState() const override { return *this; }
766 /// See AbstractAttribute::getManifestPosition().
767 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
769 const std::string getAsStr() const override {
770 return getAssumed() ? "nosync" : "may-sync";
773 /// See AbstractAttribute::updateImpl(...).
774 ChangeStatus updateImpl(Attributor &A) override;
776 /// See AANoSync::isAssumedNoSync()
777 bool isAssumedNoSync() const override { return getAssumed(); }
779 /// See AANoSync::isKnownNoSync()
780 bool isKnownNoSync() const override { return getKnown(); }
782 /// Helper function used to determine whether an instruction is non-relaxed
783 /// atomic. In other words, if an atomic instruction does not have unordered
784 /// or monotonic ordering
785 static bool isNonRelaxedAtomic(Instruction *I);
787 /// Helper function used to determine whether an instruction is volatile.
788 static bool isVolatile(Instruction *I);
790 /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
792 static bool isNoSyncIntrinsic(Instruction *I);
795 bool AANoSyncFunction::isNonRelaxedAtomic(Instruction *I) {
799 AtomicOrdering Ordering;
800 switch (I->getOpcode()) {
801 case Instruction::AtomicRMW:
802 Ordering = cast<AtomicRMWInst>(I)->getOrdering();
804 case Instruction::Store:
805 Ordering = cast<StoreInst>(I)->getOrdering();
807 case Instruction::Load:
808 Ordering = cast<LoadInst>(I)->getOrdering();
810 case Instruction::Fence: {
811 auto *FI = cast<FenceInst>(I);
812 if (FI->getSyncScopeID() == SyncScope::SingleThread)
814 Ordering = FI->getOrdering();
817 case Instruction::AtomicCmpXchg: {
818 AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
819 AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
820 // Only if both are relaxed, than it can be treated as relaxed.
821 // Otherwise it is non-relaxed.
822 if (Success != AtomicOrdering::Unordered &&
823 Success != AtomicOrdering::Monotonic)
825 if (Failure != AtomicOrdering::Unordered &&
826 Failure != AtomicOrdering::Monotonic)
832 "New atomic operations need to be known in the attributor.");
836 if (Ordering == AtomicOrdering::Unordered ||
837 Ordering == AtomicOrdering::Monotonic)
842 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
843 /// FIXME: We should ipmrove the handling of intrinsics.
844 bool AANoSyncFunction::isNoSyncIntrinsic(Instruction *I) {
845 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
846 switch (II->getIntrinsicID()) {
847 /// Element wise atomic memory intrinsics are can only be unordered,
848 /// therefore nosync.
849 case Intrinsic::memset_element_unordered_atomic:
850 case Intrinsic::memmove_element_unordered_atomic:
851 case Intrinsic::memcpy_element_unordered_atomic:
853 case Intrinsic::memset:
854 case Intrinsic::memmove:
855 case Intrinsic::memcpy:
856 if (!cast<MemIntrinsic>(II)->isVolatile())
866 bool AANoSyncFunction::isVolatile(Instruction *I) {
867 assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
868 "Calls should not be checked here");
870 switch (I->getOpcode()) {
871 case Instruction::AtomicRMW:
872 return cast<AtomicRMWInst>(I)->isVolatile();
873 case Instruction::Store:
874 return cast<StoreInst>(I)->isVolatile();
875 case Instruction::Load:
876 return cast<LoadInst>(I)->isVolatile();
877 case Instruction::AtomicCmpXchg:
878 return cast<AtomicCmpXchgInst>(I)->isVolatile();
884 ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
885 Function &F = getAnchorScope();
887 /// We are looking for volatile instructions or Non-Relaxed atomics.
888 /// FIXME: We should ipmrove the handling of intrinsics.
889 for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) {
890 ImmutableCallSite ICS(I);
891 auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
893 if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
896 if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
897 !ICS.hasFnAttr(Attribute::NoSync)) {
898 indicatePessimisticFixpoint();
899 return ChangeStatus::CHANGED;
905 if (!isVolatile(I) && !isNonRelaxedAtomic(I))
908 indicatePessimisticFixpoint();
909 return ChangeStatus::CHANGED;
912 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
913 auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
914 (unsigned)Instruction::Call};
916 for (unsigned Opcode : Opcodes) {
917 for (Instruction *I : OpcodeInstMap[Opcode]) {
918 // At this point we handled all read/write effects and they are all
919 // nosync, so they can be skipped.
920 if (I->mayReadOrWriteMemory())
923 ImmutableCallSite ICS(I);
925 // non-convergent and readnone imply nosync.
926 if (!ICS.isConvergent())
929 indicatePessimisticFixpoint();
930 return ChangeStatus::CHANGED;
934 return ChangeStatus::UNCHANGED;
937 /// ------------------------ No-Free Attributes ----------------------------
939 struct AANoFreeFunction : AbstractAttribute, BooleanState {
941 /// See AbstractAttribute::AbstractAttribute(...).
942 AANoFreeFunction(Function &F, InformationCache &InfoCache)
943 : AbstractAttribute(F, InfoCache) {}
945 /// See AbstractAttribute::getState()
947 AbstractState &getState() override { return *this; }
948 const AbstractState &getState() const override { return *this; }
951 /// See AbstractAttribute::getManifestPosition().
952 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
954 /// See AbstractAttribute::getAsStr().
955 const std::string getAsStr() const override {
956 return getAssumed() ? "nofree" : "may-free";
959 /// See AbstractAttribute::updateImpl(...).
960 ChangeStatus updateImpl(Attributor &A) override;
962 /// See AbstractAttribute::getAttrKind().
963 Attribute::AttrKind getAttrKind() const override { return ID; }
965 /// Return true if "nofree" is assumed.
966 bool isAssumedNoFree() const { return getAssumed(); }
968 /// Return true if "nofree" is known.
969 bool isKnownNoFree() const { return getKnown(); }
971 /// The identifier used by the Attributor for this class of attributes.
972 static constexpr Attribute::AttrKind ID = Attribute::NoFree;
975 ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
976 Function &F = getAnchorScope();
978 // The map from instruction opcodes to those instructions in the function.
979 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
981 for (unsigned Opcode :
982 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
983 (unsigned)Instruction::Call}) {
984 for (Instruction *I : OpcodeInstMap[Opcode]) {
986 auto ICS = ImmutableCallSite(I);
987 auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
989 if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
990 !ICS.hasFnAttr(Attribute::NoFree)) {
991 indicatePessimisticFixpoint();
992 return ChangeStatus::CHANGED;
996 return ChangeStatus::UNCHANGED;
999 /// ------------------------ NonNull Argument Attribute ------------------------
1000 struct AANonNullImpl : AANonNull, BooleanState {
1002 AANonNullImpl(Value &V, InformationCache &InfoCache)
1003 : AANonNull(V, InfoCache) {}
1005 AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue,
1006 InformationCache &InfoCache)
1007 : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1009 /// See AbstractAttribute::getState()
1011 AbstractState &getState() override { return *this; }
1012 const AbstractState &getState() const override { return *this; }
1015 /// See AbstractAttribute::getAsStr().
1016 const std::string getAsStr() const override {
1017 return getAssumed() ? "nonnull" : "may-null";
1020 /// See AANonNull::isAssumedNonNull().
1021 bool isAssumedNonNull() const override { return getAssumed(); }
1023 /// See AANonNull::isKnownNonNull().
1024 bool isKnownNonNull() const override { return getKnown(); }
1026 /// Generate a predicate that checks if a given value is assumed nonnull.
1027 /// The generated function returns true if a value satisfies any of
1028 /// following conditions.
1029 /// (i) A value is known nonZero(=nonnull).
1030 /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
1032 std::function<bool(Value &)> generatePredicate(Attributor &);
1035 std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
1036 // FIXME: The `AAReturnedValues` should provide the predicate with the
1037 // `ReturnInst` vector as well such that we can use the control flow sensitive
1038 // version of `isKnownNonZero`. This should fix `test11` in
1039 // `test/Transforms/FunctionAttrs/nonnull.ll`
1041 std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1042 if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1045 auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1047 ImmutableCallSite ICS(&RV);
1049 if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
1050 (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
1059 /// NonNull attribute for function return value.
1060 struct AANonNullReturned : AANonNullImpl {
1062 AANonNullReturned(Function &F, InformationCache &InfoCache)
1063 : AANonNullImpl(F, InfoCache) {}
1065 /// See AbstractAttribute::getManifestPosition().
1066 ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1068 /// See AbstractAttriubute::initialize(...).
1069 void initialize(Attributor &A) override {
1070 Function &F = getAnchorScope();
1073 if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1074 Attribute::NonNull))
1075 indicateOptimisticFixpoint();
1078 /// See AbstractAttribute::updateImpl(...).
1079 ChangeStatus updateImpl(Attributor &A) override;
1082 ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
1083 Function &F = getAnchorScope();
1085 auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1087 indicatePessimisticFixpoint();
1088 return ChangeStatus::CHANGED;
1091 std::function<bool(Value &)> Pred = this->generatePredicate(A);
1092 if (!AARetVal->checkForallReturnedValues(Pred)) {
1093 indicatePessimisticFixpoint();
1094 return ChangeStatus::CHANGED;
1096 return ChangeStatus::UNCHANGED;
1099 /// NonNull attribute for function argument.
1100 struct AANonNullArgument : AANonNullImpl {
1102 AANonNullArgument(Argument &A, InformationCache &InfoCache)
1103 : AANonNullImpl(A, InfoCache) {}
1105 /// See AbstractAttribute::getManifestPosition().
1106 ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1108 /// See AbstractAttriubute::initialize(...).
1109 void initialize(Attributor &A) override {
1110 Argument *Arg = cast<Argument>(getAssociatedValue());
1111 if (Arg->hasNonNullAttr())
1112 indicateOptimisticFixpoint();
1115 /// See AbstractAttribute::updateImpl(...).
1116 ChangeStatus updateImpl(Attributor &A) override;
1119 /// NonNull attribute for a call site argument.
1120 struct AANonNullCallSiteArgument : AANonNullImpl {
1122 /// See AANonNullImpl::AANonNullImpl(...).
1123 AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
1124 InformationCache &InfoCache)
1125 : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1128 /// See AbstractAttribute::initialize(...).
1129 void initialize(Attributor &A) override {
1130 CallSite CS(&getAnchoredValue());
1131 if (isKnownNonZero(getAssociatedValue(),
1132 getAnchorScope().getParent()->getDataLayout()) ||
1133 CS.paramHasAttr(ArgNo, getAttrKind()))
1134 indicateOptimisticFixpoint();
1137 /// See AbstractAttribute::updateImpl(Attributor &A).
1138 ChangeStatus updateImpl(Attributor &A) override;
1140 /// See AbstractAttribute::getManifestPosition().
1141 ManifestPosition getManifestPosition() const override {
1142 return MP_CALL_SITE_ARGUMENT;
1145 // Return argument index of associated value.
1146 int getArgNo() const { return ArgNo; }
1151 ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
1152 Function &F = getAnchorScope();
1153 Argument &Arg = cast<Argument>(getAnchoredValue());
1155 unsigned ArgNo = Arg.getArgNo();
1157 // Callback function
1158 std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1159 assert(CS && "Sanity check: Call site was not initialized properly!");
1161 auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1163 // Check that NonNullAA is AANonNullCallSiteArgument.
1165 ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1166 if (ICS && CS.getInstruction() == ICS.getInstruction())
1167 return NonNullAA->isAssumedNonNull();
1171 if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1174 Value *V = CS.getArgOperand(ArgNo);
1175 if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1180 if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1181 indicatePessimisticFixpoint();
1182 return ChangeStatus::CHANGED;
1184 return ChangeStatus::UNCHANGED;
1187 ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
1188 // NOTE: Never look at the argument of the callee in this method.
1189 // If we do this, "nonnull" is always deduced because of the assumption.
1191 Value &V = *getAssociatedValue();
1193 auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1195 if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
1196 indicatePessimisticFixpoint();
1197 return ChangeStatus::CHANGED;
1200 return ChangeStatus::UNCHANGED;
1203 /// ------------------------ Will-Return Attributes ----------------------------
1205 struct AAWillReturnImpl : public AAWillReturn, BooleanState {
1207 /// See AbstractAttribute::AbstractAttribute(...).
1208 AAWillReturnImpl(Function &F, InformationCache &InfoCache)
1209 : AAWillReturn(F, InfoCache) {}
1211 /// See AAWillReturn::isKnownWillReturn().
1212 bool isKnownWillReturn() const override { return getKnown(); }
1214 /// See AAWillReturn::isAssumedWillReturn().
1215 bool isAssumedWillReturn() const override { return getAssumed(); }
1217 /// See AbstractAttribute::getState(...).
1218 AbstractState &getState() override { return *this; }
1220 /// See AbstractAttribute::getState(...).
1221 const AbstractState &getState() const override { return *this; }
1223 /// See AbstractAttribute::getAsStr()
1224 const std::string getAsStr() const override {
1225 return getAssumed() ? "willreturn" : "may-noreturn";
1229 struct AAWillReturnFunction final : AAWillReturnImpl {
1231 /// See AbstractAttribute::AbstractAttribute(...).
1232 AAWillReturnFunction(Function &F, InformationCache &InfoCache)
1233 : AAWillReturnImpl(F, InfoCache) {}
1235 /// See AbstractAttribute::getManifestPosition().
1236 ManifestPosition getManifestPosition() const override {
1240 /// See AbstractAttribute::initialize(...).
1241 void initialize(Attributor &A) override;
1243 /// See AbstractAttribute::updateImpl(...).
1244 ChangeStatus updateImpl(Attributor &A) override;
1247 // Helper function that checks whether a function has any cycle.
1248 // TODO: Replace with more efficent code
1249 bool containsCycle(Function &F) {
1250 SmallPtrSet<BasicBlock *, 32> Visited;
1252 // Traverse BB by dfs and check whether successor is already visited.
1253 for (BasicBlock *BB : depth_first(&F)) {
1255 for (auto *SuccBB : successors(BB)) {
1256 if (Visited.count(SuccBB))
1263 // Helper function that checks the function have a loop which might become an
1265 // FIXME: Any cycle is regarded as endless loop for now.
1266 // We have to allow some patterns.
1267 bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); }
1269 void AAWillReturnFunction::initialize(Attributor &A) {
1270 Function &F = getAnchorScope();
1272 if (containsPossiblyEndlessLoop(F))
1273 indicatePessimisticFixpoint();
1276 ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
1277 Function &F = getAnchorScope();
1279 // The map from instruction opcodes to those instructions in the function.
1280 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1282 for (unsigned Opcode :
1283 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1284 (unsigned)Instruction::Call}) {
1285 for (Instruction *I : OpcodeInstMap[Opcode]) {
1286 auto ICS = ImmutableCallSite(I);
1288 if (ICS.hasFnAttr(Attribute::WillReturn))
1291 auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1292 if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
1293 indicatePessimisticFixpoint();
1294 return ChangeStatus::CHANGED;
1297 auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1299 // FIXME: (i) Prohibit any recursion for now.
1300 // (ii) AANoRecurse isn't implemented yet so currently any call is
1301 // regarded as having recursion.
1302 // Code below should be
1303 // if ((!NoRecurseAA || !NoRecurseAA->isAssumedNoRecurse()) &&
1304 if (!NoRecurseAA && !ICS.hasFnAttr(Attribute::NoRecurse)) {
1305 indicatePessimisticFixpoint();
1306 return ChangeStatus::CHANGED;
1311 return ChangeStatus::UNCHANGED;
1314 /// ----------------------------------------------------------------------------
1316 /// ----------------------------------------------------------------------------
1318 bool Attributor::checkForAllCallSites(Function &F,
1319 std::function<bool(CallSite)> &Pred,
1320 bool RequireAllCallSites) {
1321 // We can try to determine information from
1322 // the call sites. However, this is only possible all call sites are known,
1323 // hence the function has internal linkage.
1324 if (RequireAllCallSites && !F.hasInternalLinkage()) {
1327 << "Attributor: Function " << F.getName()
1328 << " has no internal linkage, hence not all call sites are known\n");
1332 for (const Use &U : F.uses()) {
1334 CallSite CS(U.getUser());
1335 if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1336 if (!RequireAllCallSites)
1339 LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
1340 << " is an invalid use of " << F.getName() << "\n");
1347 LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
1348 << *CS.getInstruction() << "\n");
1355 ChangeStatus Attributor::run() {
1356 // Initialize all abstract attributes.
1357 for (AbstractAttribute *AA : AllAbstractAttributes)
1358 AA->initialize(*this);
1360 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
1361 << AllAbstractAttributes.size()
1362 << " abstract attributes.\n");
1364 // Now that all abstract attributes are collected and initialized we start
1365 // the abstract analysis.
1367 unsigned IterationCounter = 1;
1369 SmallVector<AbstractAttribute *, 64> ChangedAAs;
1370 SetVector<AbstractAttribute *> Worklist;
1371 Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
1374 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1375 << ", Worklist size: " << Worklist.size() << "\n");
1377 // Add all abstract attributes that are potentially dependent on one that
1378 // changed to the work list.
1379 for (AbstractAttribute *ChangedAA : ChangedAAs) {
1380 auto &QuerriedAAs = QueryMap[ChangedAA];
1381 Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
1384 // Reset the changed set.
1387 // Update all abstract attribute in the work list and record the ones that
1389 for (AbstractAttribute *AA : Worklist)
1390 if (AA->update(*this) == ChangeStatus::CHANGED)
1391 ChangedAAs.push_back(AA);
1393 // Reset the work list and repopulate with the changed abstract attributes.
1394 // Note that dependent ones are added above.
1396 Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1398 } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
1400 LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1401 << IterationCounter << "/" << MaxFixpointIterations
1402 << " iterations\n");
1404 bool FinishedAtFixpoint = Worklist.empty();
1406 // Reset abstract arguments not settled in a sound fixpoint by now. This
1407 // happens when we stopped the fixpoint iteration early. Note that only the
1408 // ones marked as "changed" *and* the ones transitively depending on them
1409 // need to be reverted to a pessimistic state. Others might not be in a
1410 // fixpoint state but we can use the optimistic results for them anyway.
1411 SmallPtrSet<AbstractAttribute *, 32> Visited;
1412 for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1413 AbstractAttribute *ChangedAA = ChangedAAs[u];
1414 if (!Visited.insert(ChangedAA).second)
1417 AbstractState &State = ChangedAA->getState();
1418 if (!State.isAtFixpoint()) {
1419 State.indicatePessimisticFixpoint();
1421 NumAttributesTimedOut++;
1424 auto &QuerriedAAs = QueryMap[ChangedAA];
1425 ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
1429 if (!Visited.empty())
1430 dbgs() << "\n[Attributor] Finalized " << Visited.size()
1431 << " abstract attributes.\n";
1434 unsigned NumManifested = 0;
1435 unsigned NumAtFixpoint = 0;
1436 ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1437 for (AbstractAttribute *AA : AllAbstractAttributes) {
1438 AbstractState &State = AA->getState();
1440 // If there is not already a fixpoint reached, we can now take the
1441 // optimistic state. This is correct because we enforced a pessimistic one
1442 // on abstract attributes that were transitively dependent on a changed one
1444 if (!State.isAtFixpoint())
1445 State.indicateOptimisticFixpoint();
1447 // If the state is invalid, we do not try to manifest it.
1448 if (!State.isValidState())
1451 // Manifest the state and record if we changed the IR.
1452 ChangeStatus LocalChange = AA->manifest(*this);
1453 ManifestChange = ManifestChange | LocalChange;
1456 NumManifested += (LocalChange == ChangeStatus::CHANGED);
1459 (void)NumManifested;
1460 (void)NumAtFixpoint;
1461 LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1462 << " arguments while " << NumAtFixpoint
1463 << " were in a valid fixpoint state\n");
1465 // If verification is requested, we finished this run at a fixpoint, and the
1466 // IR was changed, we re-run the whole fixpoint analysis, starting at
1467 // re-initialization of the arguments. This re-run should not result in an IR
1468 // change. Though, the (virtual) state of attributes at the end of the re-run
1469 // might be more optimistic than the known state or the IR state if the better
1470 // state cannot be manifested.
1471 if (VerifyAttributor && FinishedAtFixpoint &&
1472 ManifestChange == ChangeStatus::CHANGED) {
1473 VerifyAttributor = false;
1474 ChangeStatus VerifyStatus = run();
1475 if (VerifyStatus != ChangeStatus::UNCHANGED)
1477 "Attributor verification failed, re-run did result in an IR change "
1478 "even after a fixpoint was reached in the original run. (False "
1479 "positives possible!)");
1480 VerifyAttributor = true;
1483 NumAttributesManifested += NumManifested;
1484 NumAttributesValidFixpoint += NumAtFixpoint;
1486 return ManifestChange;
1489 void Attributor::identifyDefaultAbstractAttributes(
1490 Function &F, InformationCache &InfoCache,
1491 DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
1493 // Every function can be nounwind.
1494 registerAA(*new AANoUnwindFunction(F, InfoCache));
1496 // Every function might be marked "nosync"
1497 registerAA(*new AANoSyncFunction(F, InfoCache));
1499 // Every function might be "no-free".
1500 registerAA(*new AANoFreeFunction(F, InfoCache));
1502 // Return attributes are only appropriate if the return type is non void.
1503 Type *ReturnType = F.getReturnType();
1504 if (!ReturnType->isVoidTy()) {
1505 // Argument attribute "returned" --- Create only one per function even
1506 // though it is an argument attribute.
1507 if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
1508 registerAA(*new AAReturnedValuesImpl(F, InfoCache));
1510 // Every function with pointer return type might be marked nonnull.
1511 if (ReturnType->isPointerTy() &&
1512 (!Whitelist || Whitelist->count(AANonNullReturned::ID)))
1513 registerAA(*new AANonNullReturned(F, InfoCache));
1516 // Every argument with pointer type might be marked nonnull.
1517 for (Argument &Arg : F.args()) {
1518 if (Arg.getType()->isPointerTy())
1519 registerAA(*new AANonNullArgument(Arg, InfoCache));
1522 // Every function might be "will-return".
1523 registerAA(*new AAWillReturnFunction(F, InfoCache));
1525 // Walk all instructions to find more attribute opportunities and also
1526 // interesting instructions that might be queried by abstract attributes
1527 // during their initialization or update.
1528 auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
1529 auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
1531 for (Instruction &I : instructions(&F)) {
1532 bool IsInterestingOpcode = false;
1534 // To allow easy access to all instructions in a function with a given
1535 // opcode we store them in the InfoCache. As not all opcodes are interesting
1536 // to concrete attributes we only cache the ones that are as identified in
1537 // the following switch.
1538 // Note: There are no concrete attributes now so this is initially empty.
1539 switch (I.getOpcode()) {
1541 assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
1542 "New call site/base instruction type needs to be known int the "
1545 case Instruction::Call:
1546 case Instruction::CallBr:
1547 case Instruction::Invoke:
1548 case Instruction::CleanupRet:
1549 case Instruction::CatchSwitch:
1550 case Instruction::Resume:
1551 case Instruction::Ret:
1552 IsInterestingOpcode = true;
1554 if (IsInterestingOpcode)
1555 InstOpcodeMap[I.getOpcode()].push_back(&I);
1556 if (I.mayReadOrWriteMemory())
1557 ReadOrWriteInsts.push_back(&I);
1560 if (CS && CS.getCalledFunction()) {
1561 for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
1562 if (!CS.getArgument(i)->getType()->isPointerTy())
1565 // Call site argument attribute "non-null".
1566 registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
1572 /// Helpers to ease debugging through output streams and print calls.
1575 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
1576 return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
1579 raw_ostream &llvm::operator<<(raw_ostream &OS,
1580 AbstractAttribute::ManifestPosition AP) {
1582 case AbstractAttribute::MP_ARGUMENT:
1584 case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
1585 return OS << "cs_arg";
1586 case AbstractAttribute::MP_FUNCTION:
1588 case AbstractAttribute::MP_RETURNED:
1589 return OS << "fn_ret";
1591 llvm_unreachable("Unknown attribute position!");
1594 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
1595 return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
1598 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
1603 void AbstractAttribute::print(raw_ostream &OS) const {
1604 OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
1605 << AnchoredVal.getName() << "]";
1609 /// ----------------------------------------------------------------------------
1610 /// Pass (Manager) Boilerplate
1611 /// ----------------------------------------------------------------------------
1613 static bool runAttributorOnModule(Module &M) {
1614 if (DisableAttributor)
1617 LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
1618 << " functions.\n");
1620 // Create an Attributor and initially empty information cache that is filled
1621 // while we identify default attribute opportunities.
1623 InformationCache InfoCache;
1625 for (Function &F : M) {
1626 // TODO: Not all attributes require an exact definition. Find a way to
1627 // enable deduction for some but not all attributes in case the
1628 // definition might be changed at runtime, see also
1629 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1630 // TODO: We could always determine abstract attributes and if sufficient
1631 // information was found we could duplicate the functions that do not
1632 // have an exact definition.
1633 if (!F.hasExactDefinition()) {
1634 NumFnWithoutExactDefinition++;
1638 // For now we ignore naked and optnone functions.
1639 if (F.hasFnAttribute(Attribute::Naked) ||
1640 F.hasFnAttribute(Attribute::OptimizeNone))
1643 NumFnWithExactDefinition++;
1645 // Populate the Attributor with abstract attribute opportunities in the
1646 // function and the information cache with IR information.
1647 A.identifyDefaultAbstractAttributes(F, InfoCache);
1650 return A.run() == ChangeStatus::CHANGED;
1653 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
1654 if (runAttributorOnModule(M)) {
1655 // FIXME: Think about passes we will preserve and add them here.
1656 return PreservedAnalyses::none();
1658 return PreservedAnalyses::all();
1663 struct AttributorLegacyPass : public ModulePass {
1666 AttributorLegacyPass() : ModulePass(ID) {
1667 initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
1670 bool runOnModule(Module &M) override {
1673 return runAttributorOnModule(M);
1676 void getAnalysisUsage(AnalysisUsage &AU) const override {
1677 // FIXME: Think about passes we will preserve and add them here.
1678 AU.setPreservesCFG();
1682 } // end anonymous namespace
1684 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
1686 char AttributorLegacyPass::ID = 0;
1687 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
1688 "Deduce and propagate attributes", false, false)
1689 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
1690 "Deduce and propagate attributes", false, false)