1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
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 // 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.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Transforms/IPO/Attributor.h"
17
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"
33 #include <cassert>
34
35 using namespace llvm;
36
37 #define DEBUG_TYPE "attributor"
38
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");
50
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");
62
63 // TODO: Determine a good default value.
64 //
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.
68 //
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."),
74 cl::init(32));
75
76 static cl::opt<bool> DisableAttributor(
77 "attributor-disable", cl::Hidden,
78 cl::desc("Disable the attributor inter-procedural deduction pass."),
79 cl::init(true));
80
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"),
85 cl::init(false));
86
87 /// Logic operators for the change status enum class.
88 ///
89 ///{
operator |(ChangeStatus l,ChangeStatus r)90 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
91 return l == ChangeStatus::CHANGED ? l : r;
92 }
operator &(ChangeStatus l,ChangeStatus r)93 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
94 return l == ChangeStatus::UNCHANGED ? l : r;
95 }
96 ///}
97
98 /// Helper to adjust the statistics.
bookkeeping(AbstractAttribute::ManifestPosition MP,const Attribute & Attr)99 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
100 const Attribute &Attr) {
101 if (!AreStatisticsEnabled())
102 return;
103
104 if (!Attr.isEnumAttribute())
105 return;
106 switch (Attr.getKindAsEnum()) {
107 case Attribute::NoUnwind:
108 NumFnNoUnwind++;
109 return;
110 case Attribute::Returned:
111 NumFnArgumentReturned++;
112 return;
113 case Attribute::NoSync:
114 NumFnNoSync++;
115 break;
116 case Attribute::NoFree:
117 NumFnNoFree++;
118 break;
119 case Attribute::NonNull:
120 switch (MP) {
121 case AbstractAttribute::MP_RETURNED:
122 NumFnReturnedNonNull++;
123 break;
124 case AbstractAttribute::MP_ARGUMENT:
125 NumFnArgumentNonNull++;
126 break;
127 case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
128 NumCSArgumentNonNull++;
129 break;
130 default:
131 break;
132 }
133 break;
134 case Attribute::WillReturn:
135 NumFnWillReturn++;
136 break;
137 default:
138 return;
139 }
140 }
141
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)>;
146
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>
genericValueTraversal(Value * InitV,StateTy & State,visitValueCB_t<StateTy> & VisitValueCB,followValueCB_t<StateTy> * FollowValueCB=nullptr,int MaxValues=8)156 static bool genericValueTraversal(
157 Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
158 followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
159
160 SmallPtrSet<Value *, 16> Visited;
161 followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
162 return Visited.insert(Val).second;
163 };
164
165 if (!FollowValueCB)
166 FollowValueCB = &DefaultFollowValueCB;
167
168 SmallVector<Value *, 16> Worklist;
169 Worklist.push_back(InitV);
170
171 int Iteration = 0;
172 do {
173 Value *V = Worklist.pop_back_val();
174
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))
178 continue;
179
180 // Make sure we limit the compile time for complex expressions.
181 if (Iteration++ >= MaxValues)
182 return false;
183
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();
188 } else {
189 CallSite CS(V);
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());
195 break;
196 }
197 if (NewV) {
198 Worklist.push_back(NewV);
199 continue;
200 }
201 }
202 }
203
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());
208 continue;
209 }
210
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());
214 continue;
215 }
216
217 // Once a leaf is reached we inform the user through the callback.
218 VisitValueCB(V, State);
219 } while (!Worklist.empty());
220
221 // All values have been visited.
222 return true;
223 }
224
225 /// Helper to identify the correct offset into an attribute list.
getAttrIndex(AbstractAttribute::ManifestPosition MP,unsigned ArgNo=0)226 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
227 unsigned ArgNo = 0) {
228 switch (MP) {
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;
236 }
237 llvm_unreachable("Unknown manifest position!");
238 }
239
240 /// Return true if \p New is equal or worse than \p Old.
isEqualOrWorse(const Attribute & New,const Attribute & Old)241 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
242 if (!Old.isIntAttribute())
243 return true;
244
245 return Old.getValueAsInt() >= New.getValueAsInt();
246 }
247
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.
addIfNotExistent(LLVMContext & Ctx,const Attribute & Attr,AttributeList & Attrs,AbstractAttribute::ManifestPosition MP,unsigned ArgNo=0)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);
256
257 if (Attr.isEnumAttribute()) {
258 Attribute::AttrKind Kind = Attr.getKindAsEnum();
259 if (Attrs.hasAttribute(AttrIdx, Kind))
260 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
261 return false;
262 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
263 return true;
264 }
265 if (Attr.isStringAttribute()) {
266 StringRef Kind = Attr.getKindAsString();
267 if (Attrs.hasAttribute(AttrIdx, Kind))
268 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
269 return false;
270 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
271 return true;
272 }
273
274 llvm_unreachable("Expected enum or string attribute!");
275 }
276
update(Attributor & A)277 ChangeStatus AbstractAttribute::update(Attributor &A) {
278 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
279 if (getState().isAtFixpoint())
280 return HasChanged;
281
282 LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
283
284 HasChanged = updateImpl(A);
285
286 LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
287 << "\n");
288
289 return HasChanged;
290 }
291
manifest(Attributor & A)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!");
297
298 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
299 SmallVector<Attribute, 4> DeducedAttrs;
300 getDeducedAttributes(DeducedAttrs);
301
302 Function &ScopeFn = getAnchorScope();
303 LLVMContext &Ctx = ScopeFn.getContext();
304 ManifestPosition MP = getManifestPosition();
305
306 AttributeList Attrs;
307 SmallVector<unsigned, 4> ArgNos;
308
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.
313
314 switch (MP) {
315 case MP_ARGUMENT:
316 ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
317 Attrs = ScopeFn.getAttributes();
318 break;
319 case MP_FUNCTION:
320 case MP_RETURNED:
321 ArgNos.push_back(0);
322 Attrs = ScopeFn.getAttributes();
323 break;
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())
328 ArgNos.push_back(u);
329 Attrs = CS.getAttributes();
330 }
331 }
332
333 for (const Attribute &Attr : DeducedAttrs) {
334 for (unsigned ArgNo : ArgNos) {
335 if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
336 continue;
337
338 HasChanged = ChangeStatus::CHANGED;
339 bookkeeping(MP, Attr);
340 }
341 }
342
343 if (HasChanged == ChangeStatus::UNCHANGED)
344 return HasChanged;
345
346 switch (MP) {
347 case MP_ARGUMENT:
348 case MP_FUNCTION:
349 case MP_RETURNED:
350 ScopeFn.setAttributes(Attrs);
351 break;
352 case MP_CALL_SITE_ARGUMENT:
353 CallSite(&getAnchoredValue()).setAttributes(Attrs);
354 }
355
356 return HasChanged;
357 }
358
getAnchorScope()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!");
368 }
369
getAnchorScope() const370 const Function &AbstractAttribute::getAnchorScope() const {
371 return const_cast<AbstractAttribute *>(this)->getAnchorScope();
372 }
373
374 /// -----------------------NoUnwind Function Attribute--------------------------
375
376 struct AANoUnwindFunction : AANoUnwind, BooleanState {
377
AANoUnwindFunctionAANoUnwindFunction378 AANoUnwindFunction(Function &F, InformationCache &InfoCache)
379 : AANoUnwind(F, InfoCache) {}
380
381 /// See AbstractAttribute::getState()
382 /// {
getStateAANoUnwindFunction383 AbstractState &getState() override { return *this; }
getStateAANoUnwindFunction384 const AbstractState &getState() const override { return *this; }
385 /// }
386
387 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANoUnwindFunction388 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
389
getAsStrAANoUnwindFunction390 const std::string getAsStr() const override {
391 return getAssumed() ? "nounwind" : "may-unwind";
392 }
393
394 /// See AbstractAttribute::updateImpl(...).
395 ChangeStatus updateImpl(Attributor &A) override;
396
397 /// See AANoUnwind::isAssumedNoUnwind().
isAssumedNoUnwindAANoUnwindFunction398 bool isAssumedNoUnwind() const override { return getAssumed(); }
399
400 /// See AANoUnwind::isKnownNoUnwind().
isKnownNoUnwindAANoUnwindFunction401 bool isKnownNoUnwind() const override { return getKnown(); }
402 };
403
updateImpl(Attributor & A)404 ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
405 Function &F = getAnchorScope();
406
407 // The map from instruction opcodes to those instructions in the function.
408 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
409 auto Opcodes = {
410 (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
411 (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
412 (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
413
414 for (unsigned Opcode : Opcodes) {
415 for (Instruction *I : OpcodeInstMap[Opcode]) {
416 if (!I->mayThrow())
417 continue;
418
419 auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
420
421 if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
422 indicatePessimisticFixpoint();
423 return ChangeStatus::CHANGED;
424 }
425 }
426 }
427 return ChangeStatus::UNCHANGED;
428 }
429
430 /// --------------------- Function Return Values -------------------------------
431
432 /// "Attribute" that collects all potential returned values and the return
433 /// instructions that they arise from.
434 ///
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 {
438
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;
442
443 /// State flags
444 ///
445 ///{
446 bool IsFixed;
447 bool IsValidState;
448 bool HasOverdefinedReturnedCalls;
449 ///}
450
451 /// Collect values that could become \p V in the set \p Values, each mapped to
452 /// \p ReturnInsts.
collectValuesRecursively(Attributor & A,Value * V,SmallPtrSetImpl<ReturnInst * > & ReturnInsts,DenseMap<Value *,SmallPtrSet<ReturnInst *,2>> & Values)453 void collectValuesRecursively(
454 Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
455 DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> &Values) {
456
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());
461 };
462
463 bool UnusedBool;
464 bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
465
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.
469 if (!Success)
470 indicatePessimisticFixpoint();
471 }
472
473 public:
474 /// See AbstractAttribute::AbstractAttribute(...).
AAReturnedValuesImpl(Function & F,InformationCache & InfoCache)475 AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
476 : AAReturnedValues(F, InfoCache) {
477 // We do not have an associated argument yet.
478 AssociatedVal = nullptr;
479 }
480
481 /// See AbstractAttribute::initialize(...).
initialize(Attributor & A)482 void initialize(Attributor &A) override {
483 // Reset the state.
484 AssociatedVal = nullptr;
485 IsFixed = false;
486 IsValidState = true;
487 HasOverdefinedReturnedCalls = false;
488 ReturnedValues.clear();
489
490 Function &F = cast<Function>(getAnchoredValue());
491
492 // The map from instruction opcodes to those instructions in the function.
493 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
494
495 // Look through all arguments, if one is marked as returned we are done.
496 for (Argument &Arg : F.args()) {
497 if (Arg.hasReturnedAttr()) {
498
499 auto &ReturnInstSet = ReturnedValues[&Arg];
500 for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
501 ReturnInstSet.insert(cast<ReturnInst>(RI));
502
503 indicateOptimisticFixpoint();
504 return;
505 }
506 }
507
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,
513 ReturnedValues);
514 }
515 }
516
517 /// See AbstractAttribute::manifest(...).
518 ChangeStatus manifest(Attributor &A) override;
519
520 /// See AbstractAttribute::getState(...).
getState()521 AbstractState &getState() override { return *this; }
522
523 /// See AbstractAttribute::getState(...).
getState() const524 const AbstractState &getState() const override { return *this; }
525
526 /// See AbstractAttribute::getManifestPosition().
getManifestPosition() const527 ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
528
529 /// See AbstractAttribute::updateImpl(Attributor &A).
530 ChangeStatus updateImpl(Attributor &A) override;
531
532 /// Return the number of potential return values, -1 if unknown.
getNumReturnValues() const533 size_t getNumReturnValues() const {
534 return isValidState() ? ReturnedValues.size() : -1;
535 }
536
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;
541
542 /// See AbstractState::checkForallReturnedValues(...).
543 bool
544 checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
545
546 /// Pretty print the attribute similar to the IR representation.
547 const std::string getAsStr() const override;
548
549 /// See AbstractState::isAtFixpoint().
isAtFixpoint() const550 bool isAtFixpoint() const override { return IsFixed; }
551
552 /// See AbstractState::isValidState().
isValidState() const553 bool isValidState() const override { return IsValidState; }
554
555 /// See AbstractState::indicateOptimisticFixpoint(...).
indicateOptimisticFixpoint()556 void indicateOptimisticFixpoint() override {
557 IsFixed = true;
558 IsValidState &= true;
559 }
indicatePessimisticFixpoint()560 void indicatePessimisticFixpoint() override {
561 IsFixed = true;
562 IsValidState = false;
563 }
564 };
565
manifest(Attributor & A)566 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
567 ChangeStatus Changed = ChangeStatus::UNCHANGED;
568
569 // Bookkeeping.
570 assert(isValidState());
571 NumFnKnownReturns++;
572
573 // Check if we have an assumed unique return value that we could manifest.
574 Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
575
576 if (!UniqueRV.hasValue() || !UniqueRV.getValue())
577 return Changed;
578
579 // Bookkeeping.
580 NumFnUniqueReturned++;
581
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;
586 }
587
588 return Changed;
589 }
590
getAsStr() const591 const std::string AAReturnedValuesImpl::getAsStr() const {
592 return (isAtFixpoint() ? "returns(#" : "may-return(#") +
593 (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
594 }
595
getAssumedUniqueReturnValue() const596 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
601 // returned value.
602 Optional<Value *> UniqueRV;
603
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()))) {
610 UniqueRV = nullptr;
611 return false;
612 }
613
614 // Do not overwrite a value with an undef.
615 if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
616 UniqueRV = &RV;
617
618 return true;
619 };
620
621 if (!checkForallReturnedValues(Pred))
622 UniqueRV = nullptr;
623
624 return UniqueRV;
625 }
626
checkForallReturnedValues(std::function<bool (Value &)> & Pred) const627 bool AAReturnedValuesImpl::checkForallReturnedValues(
628 std::function<bool(Value &)> &Pred) const {
629 if (!isValidState())
630 return false;
631
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;
636
637 ImmutableCallSite ICS(RV);
638 if (ICS && !HasOverdefinedReturnedCalls)
639 continue;
640
641 if (!Pred(*RV))
642 return false;
643 }
644
645 return true;
646 }
647
updateImpl(Attributor & A)648 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
649
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;
655 }
656
657 // Check if any of the returned values is a call site we can refine.
658 decltype(ReturnedValues) AddRVs;
659 bool HasCallSite = false;
660
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
666 << "\n");
667
668 // Only call sites can change during an update, ignore the rest.
669 CallSite RetCS(RV);
670 if (!RetCS)
671 continue;
672
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.
676 HasCallSite = true;
677
678 // Try to find a assumed unique return value for the called function.
679 auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
680 if (!RetCSAA) {
681 HasOverdefinedReturnedCalls = true;
682 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
683 << ") with " << (RetCSAA ? "invalid" : "no")
684 << " associated state\n");
685 continue;
686 }
687
688 // Try to find a assumed unique return value for the called function.
689 Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
690
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())
697 continue;
698
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");
705 continue;
706 }
707
708 LLVM_DEBUG({
709 bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
710 dbgs() << "[AAReturnedValues] Returned call site "
711 << (UniqueRVIsKnown ? "known" : "assumed")
712 << " unique return value: " << *AssumedUniqueRV << "\n";
713 });
714
715 // The assumed unique return value.
716 Value *AssumedRetVal = AssumedUniqueRV.getValue();
717
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);
726 else
727 AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
728 }
729
730 // Keep track of any change to trigger updates on dependent attributes.
731 ChangeStatus Changed = ChangeStatus::UNCHANGED;
732
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;
741 }
742 }
743
744 // If there is no call site in the returned values we are done.
745 if (!HasCallSite) {
746 indicateOptimisticFixpoint();
747 return ChangeStatus::CHANGED;
748 }
749
750 return Changed;
751 }
752
753 /// ------------------------ NoSync Function Attribute -------------------------
754
755 struct AANoSyncFunction : AANoSync, BooleanState {
756
AANoSyncFunctionAANoSyncFunction757 AANoSyncFunction(Function &F, InformationCache &InfoCache)
758 : AANoSync(F, InfoCache) {}
759
760 /// See AbstractAttribute::getState()
761 /// {
getStateAANoSyncFunction762 AbstractState &getState() override { return *this; }
getStateAANoSyncFunction763 const AbstractState &getState() const override { return *this; }
764 /// }
765
766 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANoSyncFunction767 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
768
getAsStrAANoSyncFunction769 const std::string getAsStr() const override {
770 return getAssumed() ? "nosync" : "may-sync";
771 }
772
773 /// See AbstractAttribute::updateImpl(...).
774 ChangeStatus updateImpl(Attributor &A) override;
775
776 /// See AANoSync::isAssumedNoSync()
isAssumedNoSyncAANoSyncFunction777 bool isAssumedNoSync() const override { return getAssumed(); }
778
779 /// See AANoSync::isKnownNoSync()
isKnownNoSyncAANoSyncFunction780 bool isKnownNoSync() const override { return getKnown(); }
781
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);
786
787 /// Helper function used to determine whether an instruction is volatile.
788 static bool isVolatile(Instruction *I);
789
790 /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
791 /// memset).
792 static bool isNoSyncIntrinsic(Instruction *I);
793 };
794
isNonRelaxedAtomic(Instruction * I)795 bool AANoSyncFunction::isNonRelaxedAtomic(Instruction *I) {
796 if (!I->isAtomic())
797 return false;
798
799 AtomicOrdering Ordering;
800 switch (I->getOpcode()) {
801 case Instruction::AtomicRMW:
802 Ordering = cast<AtomicRMWInst>(I)->getOrdering();
803 break;
804 case Instruction::Store:
805 Ordering = cast<StoreInst>(I)->getOrdering();
806 break;
807 case Instruction::Load:
808 Ordering = cast<LoadInst>(I)->getOrdering();
809 break;
810 case Instruction::Fence: {
811 auto *FI = cast<FenceInst>(I);
812 if (FI->getSyncScopeID() == SyncScope::SingleThread)
813 return false;
814 Ordering = FI->getOrdering();
815 break;
816 }
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)
824 return true;
825 if (Failure != AtomicOrdering::Unordered &&
826 Failure != AtomicOrdering::Monotonic)
827 return true;
828 return false;
829 }
830 default:
831 llvm_unreachable(
832 "New atomic operations need to be known in the attributor.");
833 }
834
835 // Relaxed.
836 if (Ordering == AtomicOrdering::Unordered ||
837 Ordering == AtomicOrdering::Monotonic)
838 return false;
839 return true;
840 }
841
842 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
843 /// FIXME: We should ipmrove the handling of intrinsics.
isNoSyncIntrinsic(Instruction * I)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:
852 return true;
853 case Intrinsic::memset:
854 case Intrinsic::memmove:
855 case Intrinsic::memcpy:
856 if (!cast<MemIntrinsic>(II)->isVolatile())
857 return true;
858 return false;
859 default:
860 return false;
861 }
862 }
863 return false;
864 }
865
isVolatile(Instruction * I)866 bool AANoSyncFunction::isVolatile(Instruction *I) {
867 assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
868 "Calls should not be checked here");
869
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();
879 default:
880 return false;
881 }
882 }
883
updateImpl(Attributor & A)884 ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
885 Function &F = getAnchorScope();
886
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);
892
893 if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
894 continue;
895
896 if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
897 !ICS.hasFnAttr(Attribute::NoSync)) {
898 indicatePessimisticFixpoint();
899 return ChangeStatus::CHANGED;
900 }
901
902 if (ICS)
903 continue;
904
905 if (!isVolatile(I) && !isNonRelaxedAtomic(I))
906 continue;
907
908 indicatePessimisticFixpoint();
909 return ChangeStatus::CHANGED;
910 }
911
912 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
913 auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
914 (unsigned)Instruction::Call};
915
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())
921 continue;
922
923 ImmutableCallSite ICS(I);
924
925 // non-convergent and readnone imply nosync.
926 if (!ICS.isConvergent())
927 continue;
928
929 indicatePessimisticFixpoint();
930 return ChangeStatus::CHANGED;
931 }
932 }
933
934 return ChangeStatus::UNCHANGED;
935 }
936
937 /// ------------------------ No-Free Attributes ----------------------------
938
939 struct AANoFreeFunction : AbstractAttribute, BooleanState {
940
941 /// See AbstractAttribute::AbstractAttribute(...).
AANoFreeFunctionAANoFreeFunction942 AANoFreeFunction(Function &F, InformationCache &InfoCache)
943 : AbstractAttribute(F, InfoCache) {}
944
945 /// See AbstractAttribute::getState()
946 ///{
getStateAANoFreeFunction947 AbstractState &getState() override { return *this; }
getStateAANoFreeFunction948 const AbstractState &getState() const override { return *this; }
949 ///}
950
951 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANoFreeFunction952 ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
953
954 /// See AbstractAttribute::getAsStr().
getAsStrAANoFreeFunction955 const std::string getAsStr() const override {
956 return getAssumed() ? "nofree" : "may-free";
957 }
958
959 /// See AbstractAttribute::updateImpl(...).
960 ChangeStatus updateImpl(Attributor &A) override;
961
962 /// See AbstractAttribute::getAttrKind().
getAttrKindAANoFreeFunction963 Attribute::AttrKind getAttrKind() const override { return ID; }
964
965 /// Return true if "nofree" is assumed.
isAssumedNoFreeAANoFreeFunction966 bool isAssumedNoFree() const { return getAssumed(); }
967
968 /// Return true if "nofree" is known.
isKnownNoFreeAANoFreeFunction969 bool isKnownNoFree() const { return getKnown(); }
970
971 /// The identifier used by the Attributor for this class of attributes.
972 static constexpr Attribute::AttrKind ID = Attribute::NoFree;
973 };
974
updateImpl(Attributor & A)975 ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
976 Function &F = getAnchorScope();
977
978 // The map from instruction opcodes to those instructions in the function.
979 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
980
981 for (unsigned Opcode :
982 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
983 (unsigned)Instruction::Call}) {
984 for (Instruction *I : OpcodeInstMap[Opcode]) {
985
986 auto ICS = ImmutableCallSite(I);
987 auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
988
989 if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
990 !ICS.hasFnAttr(Attribute::NoFree)) {
991 indicatePessimisticFixpoint();
992 return ChangeStatus::CHANGED;
993 }
994 }
995 }
996 return ChangeStatus::UNCHANGED;
997 }
998
999 /// ------------------------ NonNull Argument Attribute ------------------------
1000 struct AANonNullImpl : AANonNull, BooleanState {
1001
AANonNullImplAANonNullImpl1002 AANonNullImpl(Value &V, InformationCache &InfoCache)
1003 : AANonNull(V, InfoCache) {}
1004
AANonNullImplAANonNullImpl1005 AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue,
1006 InformationCache &InfoCache)
1007 : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1008
1009 /// See AbstractAttribute::getState()
1010 /// {
getStateAANonNullImpl1011 AbstractState &getState() override { return *this; }
getStateAANonNullImpl1012 const AbstractState &getState() const override { return *this; }
1013 /// }
1014
1015 /// See AbstractAttribute::getAsStr().
getAsStrAANonNullImpl1016 const std::string getAsStr() const override {
1017 return getAssumed() ? "nonnull" : "may-null";
1018 }
1019
1020 /// See AANonNull::isAssumedNonNull().
isAssumedNonNullAANonNullImpl1021 bool isAssumedNonNull() const override { return getAssumed(); }
1022
1023 /// See AANonNull::isKnownNonNull().
isKnownNonNullAANonNullImpl1024 bool isKnownNonNull() const override { return getKnown(); }
1025
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
1031 /// true.
1032 std::function<bool(Value &)> generatePredicate(Attributor &);
1033 };
1034
generatePredicate(Attributor & A)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`
1040
1041 std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1042 if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1043 return true;
1044
1045 auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1046
1047 ImmutableCallSite ICS(&RV);
1048
1049 if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
1050 (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
1051 return false;
1052
1053 return true;
1054 };
1055
1056 return Pred;
1057 }
1058
1059 /// NonNull attribute for function return value.
1060 struct AANonNullReturned : AANonNullImpl {
1061
AANonNullReturnedAANonNullReturned1062 AANonNullReturned(Function &F, InformationCache &InfoCache)
1063 : AANonNullImpl(F, InfoCache) {}
1064
1065 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANonNullReturned1066 ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1067
1068 /// See AbstractAttriubute::initialize(...).
initializeAANonNullReturned1069 void initialize(Attributor &A) override {
1070 Function &F = getAnchorScope();
1071
1072 // Already nonnull.
1073 if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1074 Attribute::NonNull))
1075 indicateOptimisticFixpoint();
1076 }
1077
1078 /// See AbstractAttribute::updateImpl(...).
1079 ChangeStatus updateImpl(Attributor &A) override;
1080 };
1081
updateImpl(Attributor & A)1082 ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
1083 Function &F = getAnchorScope();
1084
1085 auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1086 if (!AARetVal) {
1087 indicatePessimisticFixpoint();
1088 return ChangeStatus::CHANGED;
1089 }
1090
1091 std::function<bool(Value &)> Pred = this->generatePredicate(A);
1092 if (!AARetVal->checkForallReturnedValues(Pred)) {
1093 indicatePessimisticFixpoint();
1094 return ChangeStatus::CHANGED;
1095 }
1096 return ChangeStatus::UNCHANGED;
1097 }
1098
1099 /// NonNull attribute for function argument.
1100 struct AANonNullArgument : AANonNullImpl {
1101
AANonNullArgumentAANonNullArgument1102 AANonNullArgument(Argument &A, InformationCache &InfoCache)
1103 : AANonNullImpl(A, InfoCache) {}
1104
1105 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANonNullArgument1106 ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1107
1108 /// See AbstractAttriubute::initialize(...).
initializeAANonNullArgument1109 void initialize(Attributor &A) override {
1110 Argument *Arg = cast<Argument>(getAssociatedValue());
1111 if (Arg->hasNonNullAttr())
1112 indicateOptimisticFixpoint();
1113 }
1114
1115 /// See AbstractAttribute::updateImpl(...).
1116 ChangeStatus updateImpl(Attributor &A) override;
1117 };
1118
1119 /// NonNull attribute for a call site argument.
1120 struct AANonNullCallSiteArgument : AANonNullImpl {
1121
1122 /// See AANonNullImpl::AANonNullImpl(...).
AANonNullCallSiteArgumentAANonNullCallSiteArgument1123 AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
1124 InformationCache &InfoCache)
1125 : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1126 ArgNo(ArgNo) {}
1127
1128 /// See AbstractAttribute::initialize(...).
initializeAANonNullCallSiteArgument1129 void initialize(Attributor &A) override {
1130 CallSite CS(&getAnchoredValue());
1131 if (isKnownNonZero(getAssociatedValue(),
1132 getAnchorScope().getParent()->getDataLayout()) ||
1133 CS.paramHasAttr(ArgNo, getAttrKind()))
1134 indicateOptimisticFixpoint();
1135 }
1136
1137 /// See AbstractAttribute::updateImpl(Attributor &A).
1138 ChangeStatus updateImpl(Attributor &A) override;
1139
1140 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAANonNullCallSiteArgument1141 ManifestPosition getManifestPosition() const override {
1142 return MP_CALL_SITE_ARGUMENT;
1143 };
1144
1145 // Return argument index of associated value.
getArgNoAANonNullCallSiteArgument1146 int getArgNo() const { return ArgNo; }
1147
1148 private:
1149 unsigned ArgNo;
1150 };
updateImpl(Attributor & A)1151 ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
1152 Function &F = getAnchorScope();
1153 Argument &Arg = cast<Argument>(getAnchoredValue());
1154
1155 unsigned ArgNo = Arg.getArgNo();
1156
1157 // Callback function
1158 std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1159 assert(CS && "Sanity check: Call site was not initialized properly!");
1160
1161 auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1162
1163 // Check that NonNullAA is AANonNullCallSiteArgument.
1164 if (NonNullAA) {
1165 ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1166 if (ICS && CS.getInstruction() == ICS.getInstruction())
1167 return NonNullAA->isAssumedNonNull();
1168 return false;
1169 }
1170
1171 if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1172 return true;
1173
1174 Value *V = CS.getArgOperand(ArgNo);
1175 if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1176 return true;
1177
1178 return false;
1179 };
1180 if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1181 indicatePessimisticFixpoint();
1182 return ChangeStatus::CHANGED;
1183 }
1184 return ChangeStatus::UNCHANGED;
1185 }
1186
updateImpl(Attributor & A)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.
1190
1191 Value &V = *getAssociatedValue();
1192
1193 auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1194
1195 if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
1196 indicatePessimisticFixpoint();
1197 return ChangeStatus::CHANGED;
1198 }
1199
1200 return ChangeStatus::UNCHANGED;
1201 }
1202
1203 /// ------------------------ Will-Return Attributes ----------------------------
1204
1205 struct AAWillReturnImpl : public AAWillReturn, BooleanState {
1206
1207 /// See AbstractAttribute::AbstractAttribute(...).
AAWillReturnImplAAWillReturnImpl1208 AAWillReturnImpl(Function &F, InformationCache &InfoCache)
1209 : AAWillReturn(F, InfoCache) {}
1210
1211 /// See AAWillReturn::isKnownWillReturn().
isKnownWillReturnAAWillReturnImpl1212 bool isKnownWillReturn() const override { return getKnown(); }
1213
1214 /// See AAWillReturn::isAssumedWillReturn().
isAssumedWillReturnAAWillReturnImpl1215 bool isAssumedWillReturn() const override { return getAssumed(); }
1216
1217 /// See AbstractAttribute::getState(...).
getStateAAWillReturnImpl1218 AbstractState &getState() override { return *this; }
1219
1220 /// See AbstractAttribute::getState(...).
getStateAAWillReturnImpl1221 const AbstractState &getState() const override { return *this; }
1222
1223 /// See AbstractAttribute::getAsStr()
getAsStrAAWillReturnImpl1224 const std::string getAsStr() const override {
1225 return getAssumed() ? "willreturn" : "may-noreturn";
1226 }
1227 };
1228
1229 struct AAWillReturnFunction final : AAWillReturnImpl {
1230
1231 /// See AbstractAttribute::AbstractAttribute(...).
AAWillReturnFunctionAAWillReturnFunction1232 AAWillReturnFunction(Function &F, InformationCache &InfoCache)
1233 : AAWillReturnImpl(F, InfoCache) {}
1234
1235 /// See AbstractAttribute::getManifestPosition().
getManifestPositionAAWillReturnFunction1236 ManifestPosition getManifestPosition() const override {
1237 return MP_FUNCTION;
1238 }
1239
1240 /// See AbstractAttribute::initialize(...).
1241 void initialize(Attributor &A) override;
1242
1243 /// See AbstractAttribute::updateImpl(...).
1244 ChangeStatus updateImpl(Attributor &A) override;
1245 };
1246
1247 // Helper function that checks whether a function has any cycle.
1248 // TODO: Replace with more efficent code
containsCycle(Function & F)1249 bool containsCycle(Function &F) {
1250 SmallPtrSet<BasicBlock *, 32> Visited;
1251
1252 // Traverse BB by dfs and check whether successor is already visited.
1253 for (BasicBlock *BB : depth_first(&F)) {
1254 Visited.insert(BB);
1255 for (auto *SuccBB : successors(BB)) {
1256 if (Visited.count(SuccBB))
1257 return true;
1258 }
1259 }
1260 return false;
1261 }
1262
1263 // Helper function that checks the function have a loop which might become an
1264 // endless loop
1265 // FIXME: Any cycle is regarded as endless loop for now.
1266 // We have to allow some patterns.
containsPossiblyEndlessLoop(Function & F)1267 bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); }
1268
initialize(Attributor & A)1269 void AAWillReturnFunction::initialize(Attributor &A) {
1270 Function &F = getAnchorScope();
1271
1272 if (containsPossiblyEndlessLoop(F))
1273 indicatePessimisticFixpoint();
1274 }
1275
updateImpl(Attributor & A)1276 ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
1277 Function &F = getAnchorScope();
1278
1279 // The map from instruction opcodes to those instructions in the function.
1280 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1281
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);
1287
1288 if (ICS.hasFnAttr(Attribute::WillReturn))
1289 continue;
1290
1291 auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1292 if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
1293 indicatePessimisticFixpoint();
1294 return ChangeStatus::CHANGED;
1295 }
1296
1297 auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1298
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;
1307 }
1308 }
1309 }
1310
1311 return ChangeStatus::UNCHANGED;
1312 }
1313
1314 /// ----------------------------------------------------------------------------
1315 /// Attributor
1316 /// ----------------------------------------------------------------------------
1317
checkForAllCallSites(Function & F,std::function<bool (CallSite)> & Pred,bool RequireAllCallSites)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()) {
1325 LLVM_DEBUG(
1326 dbgs()
1327 << "Attributor: Function " << F.getName()
1328 << " has no internal linkage, hence not all call sites are known\n");
1329 return false;
1330 }
1331
1332 for (const Use &U : F.uses()) {
1333
1334 CallSite CS(U.getUser());
1335 if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1336 if (!RequireAllCallSites)
1337 continue;
1338
1339 LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
1340 << " is an invalid use of " << F.getName() << "\n");
1341 return false;
1342 }
1343
1344 if (Pred(CS))
1345 continue;
1346
1347 LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
1348 << *CS.getInstruction() << "\n");
1349 return false;
1350 }
1351
1352 return true;
1353 }
1354
run()1355 ChangeStatus Attributor::run() {
1356 // Initialize all abstract attributes.
1357 for (AbstractAttribute *AA : AllAbstractAttributes)
1358 AA->initialize(*this);
1359
1360 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
1361 << AllAbstractAttributes.size()
1362 << " abstract attributes.\n");
1363
1364 // Now that all abstract attributes are collected and initialized we start
1365 // the abstract analysis.
1366
1367 unsigned IterationCounter = 1;
1368
1369 SmallVector<AbstractAttribute *, 64> ChangedAAs;
1370 SetVector<AbstractAttribute *> Worklist;
1371 Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
1372
1373 do {
1374 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1375 << ", Worklist size: " << Worklist.size() << "\n");
1376
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());
1382 }
1383
1384 // Reset the changed set.
1385 ChangedAAs.clear();
1386
1387 // Update all abstract attribute in the work list and record the ones that
1388 // changed.
1389 for (AbstractAttribute *AA : Worklist)
1390 if (AA->update(*this) == ChangeStatus::CHANGED)
1391 ChangedAAs.push_back(AA);
1392
1393 // Reset the work list and repopulate with the changed abstract attributes.
1394 // Note that dependent ones are added above.
1395 Worklist.clear();
1396 Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1397
1398 } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
1399
1400 LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1401 << IterationCounter << "/" << MaxFixpointIterations
1402 << " iterations\n");
1403
1404 bool FinishedAtFixpoint = Worklist.empty();
1405
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)
1415 continue;
1416
1417 AbstractState &State = ChangedAA->getState();
1418 if (!State.isAtFixpoint()) {
1419 State.indicatePessimisticFixpoint();
1420
1421 NumAttributesTimedOut++;
1422 }
1423
1424 auto &QuerriedAAs = QueryMap[ChangedAA];
1425 ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
1426 }
1427
1428 LLVM_DEBUG({
1429 if (!Visited.empty())
1430 dbgs() << "\n[Attributor] Finalized " << Visited.size()
1431 << " abstract attributes.\n";
1432 });
1433
1434 unsigned NumManifested = 0;
1435 unsigned NumAtFixpoint = 0;
1436 ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1437 for (AbstractAttribute *AA : AllAbstractAttributes) {
1438 AbstractState &State = AA->getState();
1439
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
1443 // already above.
1444 if (!State.isAtFixpoint())
1445 State.indicateOptimisticFixpoint();
1446
1447 // If the state is invalid, we do not try to manifest it.
1448 if (!State.isValidState())
1449 continue;
1450
1451 // Manifest the state and record if we changed the IR.
1452 ChangeStatus LocalChange = AA->manifest(*this);
1453 ManifestChange = ManifestChange | LocalChange;
1454
1455 NumAtFixpoint++;
1456 NumManifested += (LocalChange == ChangeStatus::CHANGED);
1457 }
1458
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");
1464
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)
1476 llvm_unreachable(
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;
1481 }
1482
1483 NumAttributesManifested += NumManifested;
1484 NumAttributesValidFixpoint += NumAtFixpoint;
1485
1486 return ManifestChange;
1487 }
1488
identifyDefaultAbstractAttributes(Function & F,InformationCache & InfoCache,DenseSet<unsigned> * Whitelist)1489 void Attributor::identifyDefaultAbstractAttributes(
1490 Function &F, InformationCache &InfoCache,
1491 DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
1492
1493 // Every function can be nounwind.
1494 registerAA(*new AANoUnwindFunction(F, InfoCache));
1495
1496 // Every function might be marked "nosync"
1497 registerAA(*new AANoSyncFunction(F, InfoCache));
1498
1499 // Every function might be "no-free".
1500 registerAA(*new AANoFreeFunction(F, InfoCache));
1501
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));
1509
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));
1514 }
1515
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));
1520 }
1521
1522 // Every function might be "will-return".
1523 registerAA(*new AAWillReturnFunction(F, InfoCache));
1524
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];
1530
1531 for (Instruction &I : instructions(&F)) {
1532 bool IsInterestingOpcode = false;
1533
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()) {
1540 default:
1541 assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
1542 "New call site/base instruction type needs to be known int the "
1543 "attributor.");
1544 break;
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;
1553 }
1554 if (IsInterestingOpcode)
1555 InstOpcodeMap[I.getOpcode()].push_back(&I);
1556 if (I.mayReadOrWriteMemory())
1557 ReadOrWriteInsts.push_back(&I);
1558
1559 CallSite CS(&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())
1563 continue;
1564
1565 // Call site argument attribute "non-null".
1566 registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
1567 }
1568 }
1569 }
1570 }
1571
1572 /// Helpers to ease debugging through output streams and print calls.
1573 ///
1574 ///{
operator <<(raw_ostream & OS,ChangeStatus S)1575 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
1576 return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
1577 }
1578
operator <<(raw_ostream & OS,AbstractAttribute::ManifestPosition AP)1579 raw_ostream &llvm::operator<<(raw_ostream &OS,
1580 AbstractAttribute::ManifestPosition AP) {
1581 switch (AP) {
1582 case AbstractAttribute::MP_ARGUMENT:
1583 return OS << "arg";
1584 case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
1585 return OS << "cs_arg";
1586 case AbstractAttribute::MP_FUNCTION:
1587 return OS << "fn";
1588 case AbstractAttribute::MP_RETURNED:
1589 return OS << "fn_ret";
1590 }
1591 llvm_unreachable("Unknown attribute position!");
1592 }
1593
operator <<(raw_ostream & OS,const AbstractState & S)1594 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
1595 return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
1596 }
1597
operator <<(raw_ostream & OS,const AbstractAttribute & AA)1598 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
1599 AA.print(OS);
1600 return OS;
1601 }
1602
print(raw_ostream & OS) const1603 void AbstractAttribute::print(raw_ostream &OS) const {
1604 OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
1605 << AnchoredVal.getName() << "]";
1606 }
1607 ///}
1608
1609 /// ----------------------------------------------------------------------------
1610 /// Pass (Manager) Boilerplate
1611 /// ----------------------------------------------------------------------------
1612
runAttributorOnModule(Module & M)1613 static bool runAttributorOnModule(Module &M) {
1614 if (DisableAttributor)
1615 return false;
1616
1617 LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
1618 << " functions.\n");
1619
1620 // Create an Attributor and initially empty information cache that is filled
1621 // while we identify default attribute opportunities.
1622 Attributor A;
1623 InformationCache InfoCache;
1624
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++;
1635 continue;
1636 }
1637
1638 // For now we ignore naked and optnone functions.
1639 if (F.hasFnAttribute(Attribute::Naked) ||
1640 F.hasFnAttribute(Attribute::OptimizeNone))
1641 continue;
1642
1643 NumFnWithExactDefinition++;
1644
1645 // Populate the Attributor with abstract attribute opportunities in the
1646 // function and the information cache with IR information.
1647 A.identifyDefaultAbstractAttributes(F, InfoCache);
1648 }
1649
1650 return A.run() == ChangeStatus::CHANGED;
1651 }
1652
run(Module & M,ModuleAnalysisManager & AM)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();
1657 }
1658 return PreservedAnalyses::all();
1659 }
1660
1661 namespace {
1662
1663 struct AttributorLegacyPass : public ModulePass {
1664 static char ID;
1665
AttributorLegacyPass__anon14ddac3b0611::AttributorLegacyPass1666 AttributorLegacyPass() : ModulePass(ID) {
1667 initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
1668 }
1669
runOnModule__anon14ddac3b0611::AttributorLegacyPass1670 bool runOnModule(Module &M) override {
1671 if (skipModule(M))
1672 return false;
1673 return runAttributorOnModule(M);
1674 }
1675
getAnalysisUsage__anon14ddac3b0611::AttributorLegacyPass1676 void getAnalysisUsage(AnalysisUsage &AU) const override {
1677 // FIXME: Think about passes we will preserve and add them here.
1678 AU.setPreservesCFG();
1679 }
1680 };
1681
1682 } // end anonymous namespace
1683
createAttributorLegacyPass()1684 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
1685
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)
1691