LLVM  10.0.0svn
Attributor.cpp
Go to the documentation of this file.
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 
17 
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
27 #include "llvm/IR/Argument.h"
28 #include "llvm/IR/Attributes.h"
29 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/InstIterator.h"
31 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/Support/Debug.h"
37 
38 #include <cassert>
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "attributor"
43 
44 STATISTIC(NumFnWithExactDefinition,
45  "Number of function with exact definitions");
46 STATISTIC(NumFnWithoutExactDefinition,
47  "Number of function without exact definitions");
48 STATISTIC(NumAttributesTimedOut,
49  "Number of abstract attributes timed out before fixpoint");
50 STATISTIC(NumAttributesValidFixpoint,
51  "Number of abstract attributes in a valid fixpoint state");
52 STATISTIC(NumAttributesManifested,
53  "Number of abstract attributes manifested in IR");
54 STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind");
55 
56 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
57 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
58 STATISTIC(NumFnArgumentReturned,
59  "Number of function arguments marked returned");
60 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
61 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
62 STATISTIC(NumFnReturnedNonNull,
63  "Number of function return values marked nonnull");
64 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
65 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
66 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
67 STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
68 
69 // TODO: Determine a good default value.
70 //
71 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
72 // (when run with the first 5 abstract attributes). The results also indicate
73 // that we never reach 32 iterations but always find a fixpoint sooner.
74 //
75 // This will become more evolved once we perform two interleaved fixpoint
76 // iterations: bottom-up and top-down.
77 static cl::opt<unsigned>
78  MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
79  cl::desc("Maximal number of fixpoint iterations."),
80  cl::init(32));
81 
83  "attributor-disable", cl::Hidden,
84  cl::desc("Disable the attributor inter-procedural deduction pass."),
85  cl::init(true));
86 
88  "attributor-verify", cl::Hidden,
89  cl::desc("Verify the Attributor deduction and "
90  "manifestation of attributes -- may issue false-positive errors"),
91  cl::init(false));
92 
93 /// Logic operators for the change status enum class.
94 ///
95 ///{
97  return l == ChangeStatus::CHANGED ? l : r;
98 }
100  return l == ChangeStatus::UNCHANGED ? l : r;
101 }
102 ///}
103 
104 /// Helper to adjust the statistics.
106  const Attribute &Attr) {
107  if (!AreStatisticsEnabled())
108  return;
109 
110  if (!Attr.isEnumAttribute())
111  return;
112  switch (Attr.getKindAsEnum()) {
113  case Attribute::NoUnwind:
114  NumFnNoUnwind++;
115  return;
116  case Attribute::Returned:
117  NumFnArgumentReturned++;
118  return;
119  case Attribute::NoSync:
120  NumFnNoSync++;
121  break;
122  case Attribute::NoFree:
123  NumFnNoFree++;
124  break;
125  case Attribute::NonNull:
126  switch (MP) {
128  NumFnReturnedNonNull++;
129  break;
131  NumFnArgumentNonNull++;
132  break;
134  NumCSArgumentNonNull++;
135  break;
136  default:
137  break;
138  }
139  break;
140  case Attribute::WillReturn:
141  NumFnWillReturn++;
142  break;
143  case Attribute::NoAlias:
144  NumFnArgumentNoAlias++;
145  return;
146  default:
147  return;
148  }
149 }
150 
151 template <typename StateTy>
152 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
153 template <typename StateTy>
154 using visitValueCB_t = std::function<void(Value *, StateTy &State)>;
155 
156 /// Recursively visit all values that might become \p InitV at some point. This
157 /// will be done by looking through cast instructions, selects, phis, and calls
158 /// with the "returned" attribute. The callback \p FollowValueCB is asked before
159 /// a potential origin value is looked at. If no \p FollowValueCB is passed, a
160 /// default one is used that will make sure we visit every value only once. Once
161 /// we cannot look through the value any further, the callback \p VisitValueCB
162 /// is invoked and passed the current value and the \p State. To limit how much
163 /// effort is invested, we will never visit more than \p MaxValues values.
164 template <typename StateTy>
166  Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
167  followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
168 
169  SmallPtrSet<Value *, 16> Visited;
170  followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
171  return Visited.insert(Val).second;
172  };
173 
174  if (!FollowValueCB)
175  FollowValueCB = &DefaultFollowValueCB;
176 
177  SmallVector<Value *, 16> Worklist;
178  Worklist.push_back(InitV);
179 
180  int Iteration = 0;
181  do {
182  Value *V = Worklist.pop_back_val();
183 
184  // Check if we should process the current value. To prevent endless
185  // recursion keep a record of the values we followed!
186  if (!(*FollowValueCB)(V, State))
187  continue;
188 
189  // Make sure we limit the compile time for complex expressions.
190  if (Iteration++ >= MaxValues)
191  return false;
192 
193  // Explicitly look through calls with a "returned" attribute if we do
194  // not have a pointer as stripPointerCasts only works on them.
195  if (V->getType()->isPointerTy()) {
196  V = V->stripPointerCasts();
197  } else {
198  CallSite CS(V);
199  if (CS && CS.getCalledFunction()) {
200  Value *NewV = nullptr;
201  for (Argument &Arg : CS.getCalledFunction()->args())
202  if (Arg.hasReturnedAttr()) {
203  NewV = CS.getArgOperand(Arg.getArgNo());
204  break;
205  }
206  if (NewV) {
207  Worklist.push_back(NewV);
208  continue;
209  }
210  }
211  }
212 
213  // Look through select instructions, visit both potential values.
214  if (auto *SI = dyn_cast<SelectInst>(V)) {
215  Worklist.push_back(SI->getTrueValue());
216  Worklist.push_back(SI->getFalseValue());
217  continue;
218  }
219 
220  // Look through phi nodes, visit all operands.
221  if (auto *PHI = dyn_cast<PHINode>(V)) {
222  Worklist.append(PHI->op_begin(), PHI->op_end());
223  continue;
224  }
225 
226  // Once a leaf is reached we inform the user through the callback.
227  VisitValueCB(V, State);
228  } while (!Worklist.empty());
229 
230  // All values have been visited.
231  return true;
232 }
233 
234 /// Helper to identify the correct offset into an attribute list.
236  unsigned ArgNo = 0) {
237  switch (MP) {
240  return ArgNo + AttributeList::FirstArgIndex;
245  }
246  llvm_unreachable("Unknown manifest position!");
247 }
248 
249 /// Return true if \p New is equal or worse than \p Old.
250 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
251  if (!Old.isIntAttribute())
252  return true;
253 
254  return Old.getValueAsInt() >= New.getValueAsInt();
255 }
256 
257 /// Return true if the information provided by \p Attr was added to the
258 /// attribute list \p Attrs. This is only the case if it was not already present
259 /// in \p Attrs at the position describe by \p MP and \p ArgNo.
260 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
263  unsigned ArgNo = 0) {
264  unsigned AttrIdx = getAttrIndex(MP, ArgNo);
265 
266  if (Attr.isEnumAttribute()) {
268  if (Attrs.hasAttribute(AttrIdx, Kind))
269  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
270  return false;
271  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
272  return true;
273  }
274  if (Attr.isStringAttribute()) {
275  StringRef Kind = Attr.getKindAsString();
276  if (Attrs.hasAttribute(AttrIdx, Kind))
277  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
278  return false;
279  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
280  return true;
281  }
282 
283  llvm_unreachable("Expected enum or string attribute!");
284 }
285 
288  if (getState().isAtFixpoint())
289  return HasChanged;
290 
291  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
292 
293  HasChanged = updateImpl(A);
294 
295  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
296  << "\n");
297 
298  return HasChanged;
299 }
300 
302  assert(getState().isValidState() &&
303  "Attempted to manifest an invalid state!");
305  "Attempted to manifest an attribute without associated value!");
306 
308  SmallVector<Attribute, 4> DeducedAttrs;
309  getDeducedAttributes(DeducedAttrs);
310 
311  Function &ScopeFn = getAnchorScope();
312  LLVMContext &Ctx = ScopeFn.getContext();
314 
317 
318  // In the following some generic code that will manifest attributes in
319  // DeducedAttrs if they improve the current IR. Due to the different
320  // annotation positions we use the underlying AttributeList interface.
321  // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
322 
323  switch (MP) {
324  case MP_ARGUMENT:
325  ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
326  Attrs = ScopeFn.getAttributes();
327  break;
328  case MP_FUNCTION:
329  case MP_RETURNED:
330  ArgNos.push_back(0);
331  Attrs = ScopeFn.getAttributes();
332  break;
333  case MP_CALL_SITE_ARGUMENT: {
334  CallSite CS(&getAnchoredValue());
335  for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
336  if (CS.getArgOperand(u) == getAssociatedValue())
337  ArgNos.push_back(u);
338  Attrs = CS.getAttributes();
339  }
340  }
341 
342  for (const Attribute &Attr : DeducedAttrs) {
343  for (unsigned ArgNo : ArgNos) {
344  if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
345  continue;
346 
347  HasChanged = ChangeStatus::CHANGED;
348  bookkeeping(MP, Attr);
349  }
350  }
351 
352  if (HasChanged == ChangeStatus::UNCHANGED)
353  return HasChanged;
354 
355  switch (MP) {
356  case MP_ARGUMENT:
357  case MP_FUNCTION:
358  case MP_RETURNED:
359  ScopeFn.setAttributes(Attrs);
360  break;
363  }
364 
365  return HasChanged;
366 }
367 
369  Value &V = getAnchoredValue();
370  if (isa<Function>(V))
371  return cast<Function>(V);
372  if (isa<Argument>(V))
373  return *cast<Argument>(V).getParent();
374  if (isa<Instruction>(V))
375  return *cast<Instruction>(V).getFunction();
376  llvm_unreachable("No scope for anchored value found!");
377 }
378 
380  return const_cast<AbstractAttribute *>(this)->getAnchorScope();
381 }
382 
383 /// -----------------------NoUnwind Function Attribute--------------------------
384 
386 
388  : AANoUnwind(F, InfoCache) {}
389 
390  /// See AbstractAttribute::getState()
391  /// {
392  AbstractState &getState() override { return *this; }
393  const AbstractState &getState() const override { return *this; }
394  /// }
395 
396  /// See AbstractAttribute::getManifestPosition().
397  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
398 
399  const std::string getAsStr() const override {
400  return getAssumed() ? "nounwind" : "may-unwind";
401  }
402 
403  /// See AbstractAttribute::updateImpl(...).
404  ChangeStatus updateImpl(Attributor &A) override;
405 
406  /// See AANoUnwind::isAssumedNoUnwind().
407  bool isAssumedNoUnwind() const override { return getAssumed(); }
408 
409  /// See AANoUnwind::isKnownNoUnwind().
410  bool isKnownNoUnwind() const override { return getKnown(); }
411 };
412 
415 
416  // The map from instruction opcodes to those instructions in the function.
417  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
418  auto Opcodes = {
419  (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
420  (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
421  (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
422 
423  for (unsigned Opcode : Opcodes) {
424  for (Instruction *I : OpcodeInstMap[Opcode]) {
425  if (!I->mayThrow())
426  continue;
427 
428  auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
429 
430  if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
431  indicatePessimisticFixpoint();
432  return ChangeStatus::CHANGED;
433  }
434  }
435  }
437 }
438 
439 /// --------------------- Function Return Values -------------------------------
440 
441 /// "Attribute" that collects all potential returned values and the return
442 /// instructions that they arise from.
443 ///
444 /// If there is a unique returned value R, the manifest method will:
445 /// - mark R with the "returned" attribute, if R is an argument.
447 
448  /// Mapping of values potentially returned by the associated function to the
449  /// return instructions that might return them.
451 
452  /// State flags
453  ///
454  ///{
455  bool IsFixed;
456  bool IsValidState;
457  bool HasOverdefinedReturnedCalls;
458  ///}
459 
460  /// Collect values that could become \p V in the set \p Values, each mapped to
461  /// \p ReturnInsts.
462  void collectValuesRecursively(
463  Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
465 
466  visitValueCB_t<bool> VisitValueCB = [&](Value *Val, bool &) {
467  assert(!isa<Instruction>(Val) ||
468  &getAnchorScope() == cast<Instruction>(Val)->getFunction());
469  Values[Val].insert(ReturnInsts.begin(), ReturnInsts.end());
470  };
471 
472  bool UnusedBool;
473  bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
474 
475  // If we did abort the above traversal we haven't see all the values.
476  // Consequently, we cannot know if the information we would derive is
477  // accurate so we give up early.
478  if (!Success)
479  indicatePessimisticFixpoint();
480  }
481 
482 public:
483  /// See AbstractAttribute::AbstractAttribute(...).
485  : AAReturnedValues(F, InfoCache) {
486  // We do not have an associated argument yet.
487  AssociatedVal = nullptr;
488  }
489 
490  /// See AbstractAttribute::initialize(...).
491  void initialize(Attributor &A) override {
492  // Reset the state.
493  AssociatedVal = nullptr;
494  IsFixed = false;
495  IsValidState = true;
496  HasOverdefinedReturnedCalls = false;
497  ReturnedValues.clear();
498 
499  Function &F = cast<Function>(getAnchoredValue());
500 
501  // The map from instruction opcodes to those instructions in the function.
502  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
503 
504  // Look through all arguments, if one is marked as returned we are done.
505  for (Argument &Arg : F.args()) {
506  if (Arg.hasReturnedAttr()) {
507 
508  auto &ReturnInstSet = ReturnedValues[&Arg];
509  for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
510  ReturnInstSet.insert(cast<ReturnInst>(RI));
511 
512  indicateOptimisticFixpoint();
513  return;
514  }
515  }
516 
517  // If no argument was marked as returned we look at all return instructions
518  // and collect potentially returned values.
519  for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) {
520  SmallPtrSet<ReturnInst *, 1> RISet({cast<ReturnInst>(RI)});
521  collectValuesRecursively(A, cast<ReturnInst>(RI)->getReturnValue(), RISet,
522  ReturnedValues);
523  }
524  }
525 
526  /// See AbstractAttribute::manifest(...).
527  ChangeStatus manifest(Attributor &A) override;
528 
529  /// See AbstractAttribute::getState(...).
530  AbstractState &getState() override { return *this; }
531 
532  /// See AbstractAttribute::getState(...).
533  const AbstractState &getState() const override { return *this; }
534 
535  /// See AbstractAttribute::getManifestPosition().
536  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
537 
538  /// See AbstractAttribute::updateImpl(Attributor &A).
539  ChangeStatus updateImpl(Attributor &A) override;
540 
541  /// Return the number of potential return values, -1 if unknown.
542  size_t getNumReturnValues() const {
543  return isValidState() ? ReturnedValues.size() : -1;
544  }
545 
546  /// Return an assumed unique return value if a single candidate is found. If
547  /// there cannot be one, return a nullptr. If it is not clear yet, return the
548  /// Optional::NoneType.
549  Optional<Value *> getAssumedUniqueReturnValue() const;
550 
551  /// See AbstractState::checkForallReturnedValues(...).
552  bool
553  checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
554 
555  /// Pretty print the attribute similar to the IR representation.
556  const std::string getAsStr() const override;
557 
558  /// See AbstractState::isAtFixpoint().
559  bool isAtFixpoint() const override { return IsFixed; }
560 
561  /// See AbstractState::isValidState().
562  bool isValidState() const override { return IsValidState; }
563 
564  /// See AbstractState::indicateOptimisticFixpoint(...).
565  void indicateOptimisticFixpoint() override {
566  IsFixed = true;
567  IsValidState &= true;
568  }
569  void indicatePessimisticFixpoint() override {
570  IsFixed = true;
571  IsValidState = false;
572  }
573 };
574 
577 
578  // Bookkeeping.
579  assert(isValidState());
580  NumFnKnownReturns++;
581 
582  // Check if we have an assumed unique return value that we could manifest.
583  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
584 
585  if (!UniqueRV.hasValue() || !UniqueRV.getValue())
586  return Changed;
587 
588  // Bookkeeping.
589  NumFnUniqueReturned++;
590 
591  // If the assumed unique return value is an argument, annotate it.
592  if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
593  AssociatedVal = UniqueRVArg;
594  Changed = AbstractAttribute::manifest(A) | Changed;
595  }
596 
597  return Changed;
598 }
599 
600 const std::string AAReturnedValuesImpl::getAsStr() const {
601  return (isAtFixpoint() ? "returns(#" : "may-return(#") +
602  (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
603 }
604 
606  // If checkForallReturnedValues provides a unique value, ignoring potential
607  // undef values that can also be present, it is assumed to be the actual
608  // return value and forwarded to the caller of this method. If there are
609  // multiple, a nullptr is returned indicating there cannot be a unique
610  // returned value.
611  Optional<Value *> UniqueRV;
612 
613  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
614  // If we found a second returned value and neither the current nor the saved
615  // one is an undef, there is no unique returned value. Undefs are special
616  // since we can pretend they have any value.
617  if (UniqueRV.hasValue() && UniqueRV != &RV &&
618  !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
619  UniqueRV = nullptr;
620  return false;
621  }
622 
623  // Do not overwrite a value with an undef.
624  if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
625  UniqueRV = &RV;
626 
627  return true;
628  };
629 
630  if (!checkForallReturnedValues(Pred))
631  UniqueRV = nullptr;
632 
633  return UniqueRV;
634 }
635 
637  std::function<bool(Value &)> &Pred) const {
638  if (!isValidState())
639  return false;
640 
641  // Check all returned values but ignore call sites as long as we have not
642  // encountered an overdefined one during an update.
643  for (auto &It : ReturnedValues) {
644  Value *RV = It.first;
645 
646  ImmutableCallSite ICS(RV);
647  if (ICS && !HasOverdefinedReturnedCalls)
648  continue;
649 
650  if (!Pred(*RV))
651  return false;
652  }
653 
654  return true;
655 }
656 
658 
659  // Check if we know of any values returned by the associated function,
660  // if not, we are done.
661  if (getNumReturnValues() == 0) {
662  indicateOptimisticFixpoint();
664  }
665 
666  // Check if any of the returned values is a call site we can refine.
667  decltype(ReturnedValues) AddRVs;
668  bool HasCallSite = false;
669 
670  // Look at all returned call sites.
671  for (auto &It : ReturnedValues) {
672  SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
673  Value *RV = It.first;
674  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
675  << "\n");
676 
677  // Only call sites can change during an update, ignore the rest.
678  CallSite RetCS(RV);
679  if (!RetCS)
680  continue;
681 
682  // For now, any call site we see will prevent us from directly fixing the
683  // state. However, if the information on the callees is fixed, the call
684  // sites will be removed and we will fix the information for this state.
685  HasCallSite = true;
686 
687  // Try to find a assumed unique return value for the called function.
688  auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
689  if (!RetCSAA) {
690  HasOverdefinedReturnedCalls = true;
691  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
692  << ") with " << (RetCSAA ? "invalid" : "no")
693  << " associated state\n");
694  continue;
695  }
696 
697  // Try to find a assumed unique return value for the called function.
698  Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
699 
700  // If no assumed unique return value was found due to the lack of
701  // candidates, we may need to resolve more calls (through more update
702  // iterations) or the called function will not return. Either way, we simply
703  // stick with the call sites as return values. Because there were not
704  // multiple possibilities, we do not treat it as overdefined.
705  if (!AssumedUniqueRV.hasValue())
706  continue;
707 
708  // If multiple, non-refinable values were found, there cannot be a unique
709  // return value for the called function. The returned call is overdefined!
710  if (!AssumedUniqueRV.getValue()) {
711  HasOverdefinedReturnedCalls = true;
712  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
713  "potentially returned values\n");
714  continue;
715  }
716 
717  LLVM_DEBUG({
718  bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
719  dbgs() << "[AAReturnedValues] Returned call site "
720  << (UniqueRVIsKnown ? "known" : "assumed")
721  << " unique return value: " << *AssumedUniqueRV << "\n";
722  });
723 
724  // The assumed unique return value.
725  Value *AssumedRetVal = AssumedUniqueRV.getValue();
726 
727  // If the assumed unique return value is an argument, lookup the matching
728  // call site operand and recursively collect new returned values.
729  // If it is not an argument, it is just put into the set of returned values
730  // as we would have already looked through casts, phis, and similar values.
731  if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
732  collectValuesRecursively(A,
733  RetCS.getArgOperand(AssumedRetArg->getArgNo()),
734  ReturnInsts, AddRVs);
735  else
736  AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
737  }
738 
739  // Keep track of any change to trigger updates on dependent attributes.
741 
742  for (auto &It : AddRVs) {
743  assert(!It.second.empty() && "Entry does not add anything.");
744  auto &ReturnInsts = ReturnedValues[It.first];
745  for (ReturnInst *RI : It.second)
746  if (ReturnInsts.insert(RI).second) {
747  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
748  << *It.first << " => " << *RI << "\n");
749  Changed = ChangeStatus::CHANGED;
750  }
751  }
752 
753  // If there is no call site in the returned values we are done.
754  if (!HasCallSite) {
755  indicateOptimisticFixpoint();
756  return ChangeStatus::CHANGED;
757  }
758 
759  return Changed;
760 }
761 
762 /// ------------------------ NoSync Function Attribute -------------------------
763 
765 
767  : AANoSync(F, InfoCache) {}
768 
769  /// See AbstractAttribute::getState()
770  /// {
771  AbstractState &getState() override { return *this; }
772  const AbstractState &getState() const override { return *this; }
773  /// }
774 
775  /// See AbstractAttribute::getManifestPosition().
776  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
777 
778  const std::string getAsStr() const override {
779  return getAssumed() ? "nosync" : "may-sync";
780  }
781 
782  /// See AbstractAttribute::updateImpl(...).
783  ChangeStatus updateImpl(Attributor &A) override;
784 
785  /// See AANoSync::isAssumedNoSync()
786  bool isAssumedNoSync() const override { return getAssumed(); }
787 
788  /// See AANoSync::isKnownNoSync()
789  bool isKnownNoSync() const override { return getKnown(); }
790 
791  /// Helper function used to determine whether an instruction is non-relaxed
792  /// atomic. In other words, if an atomic instruction does not have unordered
793  /// or monotonic ordering
794  static bool isNonRelaxedAtomic(Instruction *I);
795 
796  /// Helper function used to determine whether an instruction is volatile.
797  static bool isVolatile(Instruction *I);
798 
799  /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
800  /// memset).
801  static bool isNoSyncIntrinsic(Instruction *I);
802 };
803 
805  if (!I->isAtomic())
806  return false;
807 
808  AtomicOrdering Ordering;
809  switch (I->getOpcode()) {
810  case Instruction::AtomicRMW:
811  Ordering = cast<AtomicRMWInst>(I)->getOrdering();
812  break;
813  case Instruction::Store:
814  Ordering = cast<StoreInst>(I)->getOrdering();
815  break;
816  case Instruction::Load:
817  Ordering = cast<LoadInst>(I)->getOrdering();
818  break;
819  case Instruction::Fence: {
820  auto *FI = cast<FenceInst>(I);
821  if (FI->getSyncScopeID() == SyncScope::SingleThread)
822  return false;
823  Ordering = FI->getOrdering();
824  break;
825  }
826  case Instruction::AtomicCmpXchg: {
827  AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
828  AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
829  // Only if both are relaxed, than it can be treated as relaxed.
830  // Otherwise it is non-relaxed.
831  if (Success != AtomicOrdering::Unordered &&
832  Success != AtomicOrdering::Monotonic)
833  return true;
834  if (Failure != AtomicOrdering::Unordered &&
835  Failure != AtomicOrdering::Monotonic)
836  return true;
837  return false;
838  }
839  default:
841  "New atomic operations need to be known in the attributor.");
842  }
843 
844  // Relaxed.
845  if (Ordering == AtomicOrdering::Unordered ||
846  Ordering == AtomicOrdering::Monotonic)
847  return false;
848  return true;
849 }
850 
851 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
852 /// FIXME: We should ipmrove the handling of intrinsics.
854  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
855  switch (II->getIntrinsicID()) {
856  /// Element wise atomic memory intrinsics are can only be unordered,
857  /// therefore nosync.
858  case Intrinsic::memset_element_unordered_atomic:
859  case Intrinsic::memmove_element_unordered_atomic:
860  case Intrinsic::memcpy_element_unordered_atomic:
861  return true;
862  case Intrinsic::memset:
863  case Intrinsic::memmove:
864  case Intrinsic::memcpy:
865  if (!cast<MemIntrinsic>(II)->isVolatile())
866  return true;
867  return false;
868  default:
869  return false;
870  }
871  }
872  return false;
873 }
874 
876  assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
877  "Calls should not be checked here");
878 
879  switch (I->getOpcode()) {
880  case Instruction::AtomicRMW:
881  return cast<AtomicRMWInst>(I)->isVolatile();
882  case Instruction::Store:
883  return cast<StoreInst>(I)->isVolatile();
884  case Instruction::Load:
885  return cast<LoadInst>(I)->isVolatile();
886  case Instruction::AtomicCmpXchg:
887  return cast<AtomicCmpXchgInst>(I)->isVolatile();
888  default:
889  return false;
890  }
891 }
892 
895 
896  /// We are looking for volatile instructions or Non-Relaxed atomics.
897  /// FIXME: We should ipmrove the handling of intrinsics.
899  ImmutableCallSite ICS(I);
900  auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
901 
902  if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
903  continue;
904 
905  if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
906  !ICS.hasFnAttr(Attribute::NoSync)) {
907  indicatePessimisticFixpoint();
908  return ChangeStatus::CHANGED;
909  }
910 
911  if (ICS)
912  continue;
913 
914  if (!isVolatile(I) && !isNonRelaxedAtomic(I))
915  continue;
916 
917  indicatePessimisticFixpoint();
918  return ChangeStatus::CHANGED;
919  }
920 
921  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
922  auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
924 
925  for (unsigned Opcode : Opcodes) {
926  for (Instruction *I : OpcodeInstMap[Opcode]) {
927  // At this point we handled all read/write effects and they are all
928  // nosync, so they can be skipped.
929  if (I->mayReadOrWriteMemory())
930  continue;
931 
932  ImmutableCallSite ICS(I);
933 
934  // non-convergent and readnone imply nosync.
935  if (!ICS.isConvergent())
936  continue;
937 
938  indicatePessimisticFixpoint();
939  return ChangeStatus::CHANGED;
940  }
941  }
942 
944 }
945 
946 /// ------------------------ No-Free Attributes ----------------------------
947 
949 
950  /// See AbstractAttribute::AbstractAttribute(...).
952  : AbstractAttribute(F, InfoCache) {}
953 
954  /// See AbstractAttribute::getState()
955  ///{
956  AbstractState &getState() override { return *this; }
957  const AbstractState &getState() const override { return *this; }
958  ///}
959 
960  /// See AbstractAttribute::getManifestPosition().
961  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
962 
963  /// See AbstractAttribute::getAsStr().
964  const std::string getAsStr() const override {
965  return getAssumed() ? "nofree" : "may-free";
966  }
967 
968  /// See AbstractAttribute::updateImpl(...).
969  ChangeStatus updateImpl(Attributor &A) override;
970 
971  /// See AbstractAttribute::getAttrKind().
972  Attribute::AttrKind getAttrKind() const override { return ID; }
973 
974  /// Return true if "nofree" is assumed.
975  bool isAssumedNoFree() const { return getAssumed(); }
976 
977  /// Return true if "nofree" is known.
978  bool isKnownNoFree() const { return getKnown(); }
979 
980  /// The identifier used by the Attributor for this class of attributes.
981  static constexpr Attribute::AttrKind ID = Attribute::NoFree;
982 };
983 
986 
987  // The map from instruction opcodes to those instructions in the function.
988  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
989 
990  for (unsigned Opcode :
991  {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
993  for (Instruction *I : OpcodeInstMap[Opcode]) {
994 
995  auto ICS = ImmutableCallSite(I);
996  auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
997 
998  if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
999  !ICS.hasFnAttr(Attribute::NoFree)) {
1000  indicatePessimisticFixpoint();
1001  return ChangeStatus::CHANGED;
1002  }
1003  }
1004  }
1005  return ChangeStatus::UNCHANGED;
1006 }
1007 
1008 /// ------------------------ NonNull Argument Attribute ------------------------
1010 
1012  : AANonNull(V, InfoCache) {}
1013 
1016  : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1017 
1018  /// See AbstractAttribute::getState()
1019  /// {
1020  AbstractState &getState() override { return *this; }
1021  const AbstractState &getState() const override { return *this; }
1022  /// }
1023 
1024  /// See AbstractAttribute::getAsStr().
1025  const std::string getAsStr() const override {
1026  return getAssumed() ? "nonnull" : "may-null";
1027  }
1028 
1029  /// See AANonNull::isAssumedNonNull().
1030  bool isAssumedNonNull() const override { return getAssumed(); }
1031 
1032  /// See AANonNull::isKnownNonNull().
1033  bool isKnownNonNull() const override { return getKnown(); }
1034 
1035  /// Generate a predicate that checks if a given value is assumed nonnull.
1036  /// The generated function returns true if a value satisfies any of
1037  /// following conditions.
1038  /// (i) A value is known nonZero(=nonnull).
1039  /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
1040  /// true.
1041  std::function<bool(Value &)> generatePredicate(Attributor &);
1042 };
1043 
1044 std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
1045  // FIXME: The `AAReturnedValues` should provide the predicate with the
1046  // `ReturnInst` vector as well such that we can use the control flow sensitive
1047  // version of `isKnownNonZero`. This should fix `test11` in
1048  // `test/Transforms/FunctionAttrs/nonnull.ll`
1049 
1050  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1051  if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1052  return true;
1053 
1054  auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1055 
1056  ImmutableCallSite ICS(&RV);
1057 
1058  if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
1059  (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
1060  return false;
1061 
1062  return true;
1063  };
1064 
1065  return Pred;
1066 }
1067 
1068 /// NonNull attribute for function return value.
1070 
1072  : AANonNullImpl(F, InfoCache) {}
1073 
1074  /// See AbstractAttribute::getManifestPosition().
1075  ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1076 
1077  /// See AbstractAttriubute::initialize(...).
1078  void initialize(Attributor &A) override {
1079  Function &F = getAnchorScope();
1080 
1081  // Already nonnull.
1083  Attribute::NonNull))
1084  indicateOptimisticFixpoint();
1085  }
1086 
1087  /// See AbstractAttribute::updateImpl(...).
1088  ChangeStatus updateImpl(Attributor &A) override;
1089 };
1090 
1092  Function &F = getAnchorScope();
1093 
1094  auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1095  if (!AARetVal) {
1096  indicatePessimisticFixpoint();
1097  return ChangeStatus::CHANGED;
1098  }
1099 
1100  std::function<bool(Value &)> Pred = this->generatePredicate(A);
1101  if (!AARetVal->checkForallReturnedValues(Pred)) {
1102  indicatePessimisticFixpoint();
1103  return ChangeStatus::CHANGED;
1104  }
1105  return ChangeStatus::UNCHANGED;
1106 }
1107 
1108 /// NonNull attribute for function argument.
1110 
1112  : AANonNullImpl(A, InfoCache) {}
1113 
1114  /// See AbstractAttribute::getManifestPosition().
1115  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1116 
1117  /// See AbstractAttriubute::initialize(...).
1118  void initialize(Attributor &A) override {
1119  Argument *Arg = cast<Argument>(getAssociatedValue());
1120  if (Arg->hasNonNullAttr())
1121  indicateOptimisticFixpoint();
1122  }
1123 
1124  /// See AbstractAttribute::updateImpl(...).
1125  ChangeStatus updateImpl(Attributor &A) override;
1126 };
1127 
1128 /// NonNull attribute for a call site argument.
1130 
1131  /// See AANonNullImpl::AANonNullImpl(...).
1134  : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1135  ArgNo(ArgNo) {}
1136 
1137  /// See AbstractAttribute::initialize(...).
1138  void initialize(Attributor &A) override {
1139  CallSite CS(&getAnchoredValue());
1141  getAnchorScope().getParent()->getDataLayout()) ||
1142  CS.paramHasAttr(ArgNo, getAttrKind()))
1143  indicateOptimisticFixpoint();
1144  }
1145 
1146  /// See AbstractAttribute::updateImpl(Attributor &A).
1147  ChangeStatus updateImpl(Attributor &A) override;
1148 
1149  /// See AbstractAttribute::getManifestPosition().
1151  return MP_CALL_SITE_ARGUMENT;
1152  };
1153 
1154  // Return argument index of associated value.
1155  int getArgNo() const { return ArgNo; }
1156 
1157 private:
1158  unsigned ArgNo;
1159 };
1161  Function &F = getAnchorScope();
1162  Argument &Arg = cast<Argument>(getAnchoredValue());
1163 
1164  unsigned ArgNo = Arg.getArgNo();
1165 
1166  // Callback function
1167  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1168  assert(CS && "Sanity check: Call site was not initialized properly!");
1169 
1170  auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1171 
1172  // Check that NonNullAA is AANonNullCallSiteArgument.
1173  if (NonNullAA) {
1174  ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1175  if (ICS && CS.getInstruction() == ICS.getInstruction())
1176  return NonNullAA->isAssumedNonNull();
1177  return false;
1178  }
1179 
1180  if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1181  return true;
1182 
1183  Value *V = CS.getArgOperand(ArgNo);
1184  if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1185  return true;
1186 
1187  return false;
1188  };
1189  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1190  indicatePessimisticFixpoint();
1191  return ChangeStatus::CHANGED;
1192  }
1193  return ChangeStatus::UNCHANGED;
1194 }
1195 
1197  // NOTE: Never look at the argument of the callee in this method.
1198  // If we do this, "nonnull" is always deduced because of the assumption.
1199 
1200  Value &V = *getAssociatedValue();
1201 
1202  auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1203 
1204  if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
1205  indicatePessimisticFixpoint();
1206  return ChangeStatus::CHANGED;
1207  }
1208 
1209  return ChangeStatus::UNCHANGED;
1210 }
1211 
1212 /// ------------------------ Will-Return Attributes ----------------------------
1213 
1215 
1216  /// See AbstractAttribute::AbstractAttribute(...).
1218  : AAWillReturn(F, InfoCache) {}
1219 
1220  /// See AAWillReturn::isKnownWillReturn().
1221  bool isKnownWillReturn() const override { return getKnown(); }
1222 
1223  /// See AAWillReturn::isAssumedWillReturn().
1224  bool isAssumedWillReturn() const override { return getAssumed(); }
1225 
1226  /// See AbstractAttribute::getState(...).
1227  AbstractState &getState() override { return *this; }
1228 
1229  /// See AbstractAttribute::getState(...).
1230  const AbstractState &getState() const override { return *this; }
1231 
1232  /// See AbstractAttribute::getAsStr()
1233  const std::string getAsStr() const override {
1234  return getAssumed() ? "willreturn" : "may-noreturn";
1235  }
1236 };
1237 
1239 
1240  /// See AbstractAttribute::AbstractAttribute(...).
1242  : AAWillReturnImpl(F, InfoCache) {}
1243 
1244  /// See AbstractAttribute::getManifestPosition().
1246  return MP_FUNCTION;
1247  }
1248 
1249  /// See AbstractAttribute::initialize(...).
1250  void initialize(Attributor &A) override;
1251 
1252  /// See AbstractAttribute::updateImpl(...).
1253  ChangeStatus updateImpl(Attributor &A) override;
1254 };
1255 
1256 // Helper function that checks whether a function has any cycle.
1257 // TODO: Replace with more efficent code
1260 
1261  // Traverse BB by dfs and check whether successor is already visited.
1262  for (BasicBlock *BB : depth_first(&F)) {
1263  Visited.insert(BB);
1264  for (auto *SuccBB : successors(BB)) {
1265  if (Visited.count(SuccBB))
1266  return true;
1267  }
1268  }
1269  return false;
1270 }
1271 
1272 // Helper function that checks the function have a loop which might become an
1273 // endless loop
1274 // FIXME: Any cycle is regarded as endless loop for now.
1275 // We have to allow some patterns.
1277 
1279  Function &F = getAnchorScope();
1280 
1282  indicatePessimisticFixpoint();
1283 }
1284 
1286  Function &F = getAnchorScope();
1287 
1288  // The map from instruction opcodes to those instructions in the function.
1289  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1290 
1291  for (unsigned Opcode :
1292  {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1294  for (Instruction *I : OpcodeInstMap[Opcode]) {
1295  auto ICS = ImmutableCallSite(I);
1296 
1297  if (ICS.hasFnAttr(Attribute::WillReturn))
1298  continue;
1299 
1300  auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1301  if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
1302  indicatePessimisticFixpoint();
1303  return ChangeStatus::CHANGED;
1304  }
1305 
1306  auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1307 
1308  // FIXME: (i) Prohibit any recursion for now.
1309  // (ii) AANoRecurse isn't implemented yet so currently any call is
1310  // regarded as having recursion.
1311  // Code below should be
1312  // if ((!NoRecurseAA || !NoRecurseAA->isAssumedNoRecurse()) &&
1313  if (!NoRecurseAA && !ICS.hasFnAttr(Attribute::NoRecurse)) {
1314  indicatePessimisticFixpoint();
1315  return ChangeStatus::CHANGED;
1316  }
1317  }
1318  }
1319 
1320  return ChangeStatus::UNCHANGED;
1321 }
1322 
1323 /// ------------------------ NoAlias Argument Attribute ------------------------
1324 
1326 
1328  : AANoAlias(V, InfoCache) {}
1329 
1330  /// See AbstractAttribute::getState()
1331  /// {
1332  AbstractState &getState() override { return *this; }
1333  const AbstractState &getState() const override { return *this; }
1334  /// }
1335 
1336  const std::string getAsStr() const override {
1337  return getAssumed() ? "noalias" : "may-alias";
1338  }
1339 
1340  /// See AANoAlias::isAssumedNoAlias().
1341  bool isAssumedNoAlias() const override { return getAssumed(); }
1342 
1343  /// See AANoAlias::isKnowndNoAlias().
1344  bool isKnownNoAlias() const override { return getKnown(); }
1345 };
1346 
1347 /// NoAlias attribute for function return value.
1349 
1351  : AANoAliasImpl(F, InfoCache) {}
1352 
1353  /// See AbstractAttribute::getManifestPosition().
1354  virtual ManifestPosition getManifestPosition() const override {
1355  return MP_RETURNED;
1356  }
1357 
1358  /// See AbstractAttriubute::initialize(...).
1359  void initialize(Attributor &A) override {
1360  Function &F = getAnchorScope();
1361 
1362  // Already noalias.
1363  if (F.returnDoesNotAlias()) {
1364  indicateOptimisticFixpoint();
1365  return;
1366  }
1367  }
1368 
1369  /// See AbstractAttribute::updateImpl(...).
1370  virtual ChangeStatus updateImpl(Attributor &A) override;
1371 };
1372 
1374  Function &F = getAnchorScope();
1375 
1376  auto *AARetValImpl = A.getAAFor<AAReturnedValuesImpl>(*this, F);
1377  if (!AARetValImpl) {
1378  indicatePessimisticFixpoint();
1379  return ChangeStatus::CHANGED;
1380  }
1381 
1382  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1383  if (Constant *C = dyn_cast<Constant>(&RV))
1384  if (C->isNullValue() || isa<UndefValue>(C))
1385  return true;
1386 
1387  /// For now, we can only deduce noalias if we have call sites.
1388  /// FIXME: add more support.
1389  ImmutableCallSite ICS(&RV);
1390  if (!ICS)
1391  return false;
1392 
1393  auto *NoAliasAA = A.getAAFor<AANoAlias>(*this, RV);
1394 
1395  if (!ICS.returnDoesNotAlias() && (!NoAliasAA ||
1396  !NoAliasAA->isAssumedNoAlias()))
1397  return false;
1398 
1399  /// FIXME: We can improve capture check in two ways:
1400  /// 1. Use the AANoCapture facilities.
1401  /// 2. Use the location of return insts for escape queries.
1402  if (PointerMayBeCaptured(&RV, /* ReturnCaptures */ false,
1403  /* StoreCaptures */ true))
1404  return false;
1405 
1406 
1407  return true;
1408  };
1409 
1410  if (!AARetValImpl->checkForallReturnedValues(Pred)) {
1411  indicatePessimisticFixpoint();
1412  return ChangeStatus::CHANGED;
1413  }
1414 
1415  return ChangeStatus::UNCHANGED;
1416 }
1417 
1418 /// -------------------AAIsDead Function Attribute-----------------------
1419 
1421 
1423  : AAIsDead(F, InfoCache) {}
1424 
1425  /// See AbstractAttribute::getState()
1426  /// {
1427  AbstractState &getState() override { return *this; }
1428  const AbstractState &getState() const override { return *this; }
1429  /// }
1430 
1431  /// See AbstractAttribute::getManifestPosition().
1432  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
1433 
1434  void initialize(Attributor &A) override {
1435  Function &F = getAnchorScope();
1436 
1437  ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
1438  AssumedLiveBlocks.insert(&(F.getEntryBlock()));
1439  for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
1440  explorePath(A, ToBeExploredPaths[i]);
1441  }
1442 
1443  /// Explores new instructions starting from \p I. If instruction is dead, stop
1444  /// and return true if it discovered a new instruction.
1445  bool explorePath(Attributor &A, Instruction *I);
1446 
1447  const std::string getAsStr() const override {
1448  return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" +
1449  std::to_string(getAnchorScope().size()) + ")";
1450  }
1451 
1452  /// See AbstractAttribute::manifest(...).
1454  assert(getState().isValidState() &&
1455  "Attempted to manifest an invalid state!");
1456 
1458 
1459  for (Instruction *I : NoReturnCalls) {
1460  BasicBlock *BB = I->getParent();
1461 
1462  /// Invoke is replaced with a call and unreachable is placed after it.
1463  if (auto *II = dyn_cast<InvokeInst>(I)) {
1464  changeToCall(II);
1465  changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1466  LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n");
1467  continue;
1468  }
1469 
1470  SplitBlock(BB, I->getNextNode());
1471  changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1472  HasChanged = ChangeStatus::CHANGED;
1473  }
1474 
1475  return HasChanged;
1476  }
1477 
1478  /// See AbstractAttribute::updateImpl(...).
1479  ChangeStatus updateImpl(Attributor &A) override;
1480 
1481  /// See AAIsDead::isAssumedDead().
1482  bool isAssumedDead(BasicBlock *BB) const override {
1483  if (!getAssumed())
1484  return false;
1485  return !AssumedLiveBlocks.count(BB);
1486  }
1487 
1488  /// See AAIsDead::isKnownDead().
1489  bool isKnownDead(BasicBlock *BB) const override {
1490  if (!getKnown())
1491  return false;
1492  return !AssumedLiveBlocks.count(BB);
1493  }
1494 
1495  /// Collection of to be explored paths.
1497 
1498  /// Collection of all assumed live BasicBlocks.
1500 
1501  /// Collection of calls with noreturn attribute, assumed or knwon.
1503 };
1504 
1506  BasicBlock *BB = I->getParent();
1507 
1508  while (I) {
1509  ImmutableCallSite ICS(I);
1510 
1511  if (ICS) {
1512  auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
1513 
1514  if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) {
1515  if (!NoReturnCalls.insert(I))
1516  // If I is already in the NoReturnCalls set, then it stayed noreturn
1517  // and we didn't discover any new instructions.
1518  return false;
1519 
1520  // Discovered new noreturn call, return true to indicate that I is not
1521  // noreturn anymore and should be deleted from NoReturnCalls.
1522  return true;
1523  }
1524 
1525  if (ICS.hasFnAttr(Attribute::NoReturn)) {
1526  if(!NoReturnCalls.insert(I))
1527  return false;
1528 
1529  return true;
1530  }
1531  }
1532 
1533  I = I->getNextNode();
1534  }
1535 
1536  // get new paths (reachable blocks).
1537  for (BasicBlock *SuccBB : successors(BB)) {
1538  Instruction *Inst = &(SuccBB->front());
1539  AssumedLiveBlocks.insert(SuccBB);
1540  ToBeExploredPaths.insert(Inst);
1541  }
1542 
1543  return true;
1544 }
1545 
1547  // Temporary collection to iterate over existing noreturn instructions. This
1548  // will alow easier modification of NoReturnCalls collection
1549  SmallVector<Instruction *, 8> NoReturnChanged;
1551 
1552  for (Instruction *I : NoReturnCalls)
1553  NoReturnChanged.push_back(I);
1554 
1555  for (Instruction *I : NoReturnChanged) {
1556  size_t Size = ToBeExploredPaths.size();
1557 
1558  // Still noreturn.
1559  if (!explorePath(A, I))
1560  continue;
1561 
1562  NoReturnCalls.remove(I);
1563 
1564  // No new paths.
1565  if (Size == ToBeExploredPaths.size())
1566  continue;
1567 
1568  // At least one new path.
1569  Status = ChangeStatus::CHANGED;
1570 
1571  // explore new paths.
1572  while (Size != ToBeExploredPaths.size())
1573  explorePath(A, ToBeExploredPaths[Size++]);
1574  }
1575 
1576  LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: "
1577  << AssumedLiveBlocks.size()
1578  << "Total number of blocks: "
1579  << getAnchorScope().size() << "\n");
1580 
1581  return Status;
1582 }
1583 
1584 /// ----------------------------------------------------------------------------
1585 /// Attributor
1586 /// ----------------------------------------------------------------------------
1587 
1589  std::function<bool(CallSite)> &Pred,
1590  bool RequireAllCallSites) {
1591  // We can try to determine information from
1592  // the call sites. However, this is only possible all call sites are known,
1593  // hence the function has internal linkage.
1594  if (RequireAllCallSites && !F.hasInternalLinkage()) {
1595  LLVM_DEBUG(
1596  dbgs()
1597  << "Attributor: Function " << F.getName()
1598  << " has no internal linkage, hence not all call sites are known\n");
1599  return false;
1600  }
1601 
1602  for (const Use &U : F.uses()) {
1603 
1604  CallSite CS(U.getUser());
1605  if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1606  if (!RequireAllCallSites)
1607  continue;
1608 
1609  LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
1610  << " is an invalid use of " << F.getName() << "\n");
1611  return false;
1612  }
1613 
1614  if (Pred(CS))
1615  continue;
1616 
1617  LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
1618  << *CS.getInstruction() << "\n");
1619  return false;
1620  }
1621 
1622  return true;
1623 }
1624 
1626  // Initialize all abstract attributes.
1627  for (AbstractAttribute *AA : AllAbstractAttributes)
1628  AA->initialize(*this);
1629 
1630  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
1631  << AllAbstractAttributes.size()
1632  << " abstract attributes.\n");
1633 
1634  // Now that all abstract attributes are collected and initialized we start
1635  // the abstract analysis.
1636 
1637  unsigned IterationCounter = 1;
1638 
1641  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
1642 
1643  do {
1644  LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1645  << ", Worklist size: " << Worklist.size() << "\n");
1646 
1647  // Add all abstract attributes that are potentially dependent on one that
1648  // changed to the work list.
1649  for (AbstractAttribute *ChangedAA : ChangedAAs) {
1650  auto &QuerriedAAs = QueryMap[ChangedAA];
1651  Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
1652  }
1653 
1654  // Reset the changed set.
1655  ChangedAAs.clear();
1656 
1657  // Update all abstract attribute in the work list and record the ones that
1658  // changed.
1659  for (AbstractAttribute *AA : Worklist)
1660  if (AA->update(*this) == ChangeStatus::CHANGED)
1661  ChangedAAs.push_back(AA);
1662 
1663  // Reset the work list and repopulate with the changed abstract attributes.
1664  // Note that dependent ones are added above.
1665  Worklist.clear();
1666  Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1667 
1668  } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
1669 
1670  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1671  << IterationCounter << "/" << MaxFixpointIterations
1672  << " iterations\n");
1673 
1674  bool FinishedAtFixpoint = Worklist.empty();
1675 
1676  // Reset abstract arguments not settled in a sound fixpoint by now. This
1677  // happens when we stopped the fixpoint iteration early. Note that only the
1678  // ones marked as "changed" *and* the ones transitively depending on them
1679  // need to be reverted to a pessimistic state. Others might not be in a
1680  // fixpoint state but we can use the optimistic results for them anyway.
1682  for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1683  AbstractAttribute *ChangedAA = ChangedAAs[u];
1684  if (!Visited.insert(ChangedAA).second)
1685  continue;
1686 
1687  AbstractState &State = ChangedAA->getState();
1688  if (!State.isAtFixpoint()) {
1690 
1691  NumAttributesTimedOut++;
1692  }
1693 
1694  auto &QuerriedAAs = QueryMap[ChangedAA];
1695  ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
1696  }
1697 
1698  LLVM_DEBUG({
1699  if (!Visited.empty())
1700  dbgs() << "\n[Attributor] Finalized " << Visited.size()
1701  << " abstract attributes.\n";
1702  });
1703 
1704  unsigned NumManifested = 0;
1705  unsigned NumAtFixpoint = 0;
1706  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1707  for (AbstractAttribute *AA : AllAbstractAttributes) {
1708  AbstractState &State = AA->getState();
1709 
1710  // If there is not already a fixpoint reached, we can now take the
1711  // optimistic state. This is correct because we enforced a pessimistic one
1712  // on abstract attributes that were transitively dependent on a changed one
1713  // already above.
1714  if (!State.isAtFixpoint())
1716 
1717  // If the state is invalid, we do not try to manifest it.
1718  if (!State.isValidState())
1719  continue;
1720 
1721  // Manifest the state and record if we changed the IR.
1722  ChangeStatus LocalChange = AA->manifest(*this);
1723  ManifestChange = ManifestChange | LocalChange;
1724 
1725  NumAtFixpoint++;
1726  NumManifested += (LocalChange == ChangeStatus::CHANGED);
1727  }
1728 
1729  (void)NumManifested;
1730  (void)NumAtFixpoint;
1731  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1732  << " arguments while " << NumAtFixpoint
1733  << " were in a valid fixpoint state\n");
1734 
1735  // If verification is requested, we finished this run at a fixpoint, and the
1736  // IR was changed, we re-run the whole fixpoint analysis, starting at
1737  // re-initialization of the arguments. This re-run should not result in an IR
1738  // change. Though, the (virtual) state of attributes at the end of the re-run
1739  // might be more optimistic than the known state or the IR state if the better
1740  // state cannot be manifested.
1741  if (VerifyAttributor && FinishedAtFixpoint &&
1742  ManifestChange == ChangeStatus::CHANGED) {
1743  VerifyAttributor = false;
1744  ChangeStatus VerifyStatus = run();
1745  if (VerifyStatus != ChangeStatus::UNCHANGED)
1747  "Attributor verification failed, re-run did result in an IR change "
1748  "even after a fixpoint was reached in the original run. (False "
1749  "positives possible!)");
1750  VerifyAttributor = true;
1751  }
1752 
1753  NumAttributesManifested += NumManifested;
1754  NumAttributesValidFixpoint += NumAtFixpoint;
1755 
1756  return ManifestChange;
1757 }
1758 
1762 
1763  // Every function can be nounwind.
1764  registerAA(*new AANoUnwindFunction(F, InfoCache));
1765 
1766  // Every function might be marked "nosync"
1767  registerAA(*new AANoSyncFunction(F, InfoCache));
1768 
1769  // Every function might be "no-free".
1770  registerAA(*new AANoFreeFunction(F, InfoCache));
1771 
1772  // Return attributes are only appropriate if the return type is non void.
1773  Type *ReturnType = F.getReturnType();
1774  if (!ReturnType->isVoidTy()) {
1775  // Argument attribute "returned" --- Create only one per function even
1776  // though it is an argument attribute.
1777  if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
1778  registerAA(*new AAReturnedValuesImpl(F, InfoCache));
1779 
1780  if (ReturnType->isPointerTy()) {
1781  // Every function with pointer return type might be marked nonnull.
1782  if (!Whitelist || Whitelist->count(AANonNullReturned::ID))
1783  registerAA(*new AANonNullReturned(F, InfoCache));
1784 
1785  // Every function with pointer return type might be marked noalias.
1786  if (!Whitelist || Whitelist->count(AANoAliasReturned::ID))
1787  registerAA(*new AANoAliasReturned(F, InfoCache));
1788  }
1789  }
1790 
1791  // Every argument with pointer type might be marked nonnull.
1792  for (Argument &Arg : F.args()) {
1793  if (Arg.getType()->isPointerTy())
1794  registerAA(*new AANonNullArgument(Arg, InfoCache));
1795  }
1796 
1797  // Every function might be "will-return".
1798  registerAA(*new AAWillReturnFunction(F, InfoCache));
1799 
1800  // Check for dead BasicBlocks in every function.
1801  registerAA(*new AAIsDeadFunction(F, InfoCache));
1802 
1803  // Walk all instructions to find more attribute opportunities and also
1804  // interesting instructions that might be queried by abstract attributes
1805  // during their initialization or update.
1806  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
1807  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
1808 
1809  for (Instruction &I : instructions(&F)) {
1810  bool IsInterestingOpcode = false;
1811 
1812  // To allow easy access to all instructions in a function with a given
1813  // opcode we store them in the InfoCache. As not all opcodes are interesting
1814  // to concrete attributes we only cache the ones that are as identified in
1815  // the following switch.
1816  // Note: There are no concrete attributes now so this is initially empty.
1817  switch (I.getOpcode()) {
1818  default:
1819  assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
1820  "New call site/base instruction type needs to be known int the "
1821  "attributor.");
1822  break;
1823  case Instruction::Call:
1824  case Instruction::CallBr:
1825  case Instruction::Invoke:
1826  case Instruction::CleanupRet:
1827  case Instruction::CatchSwitch:
1828  case Instruction::Resume:
1829  case Instruction::Ret:
1830  IsInterestingOpcode = true;
1831  }
1832  if (IsInterestingOpcode)
1833  InstOpcodeMap[I.getOpcode()].push_back(&I);
1834  if (I.mayReadOrWriteMemory())
1835  ReadOrWriteInsts.push_back(&I);
1836 
1837  CallSite CS(&I);
1838  if (CS && CS.getCalledFunction()) {
1839  for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
1840  if (!CS.getArgument(i)->getType()->isPointerTy())
1841  continue;
1842 
1843  // Call site argument attribute "non-null".
1844  registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
1845  }
1846  }
1847  }
1848 }
1849 
1850 /// Helpers to ease debugging through output streams and print calls.
1851 ///
1852 ///{
1854  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
1855 }
1856 
1859  switch (AP) {
1861  return OS << "arg";
1863  return OS << "cs_arg";
1865  return OS << "fn";
1867  return OS << "fn_ret";
1868  }
1869  llvm_unreachable("Unknown attribute position!");
1870 }
1871 
1873  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
1874 }
1875 
1877  AA.print(OS);
1878  return OS;
1879 }
1880 
1882  OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
1883  << AnchoredVal.getName() << "]";
1884 }
1885 ///}
1886 
1887 /// ----------------------------------------------------------------------------
1888 /// Pass (Manager) Boilerplate
1889 /// ----------------------------------------------------------------------------
1890 
1892  if (DisableAttributor)
1893  return false;
1894 
1895  LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
1896  << " functions.\n");
1897 
1898  // Create an Attributor and initially empty information cache that is filled
1899  // while we identify default attribute opportunities.
1900  Attributor A;
1902 
1903  for (Function &F : M) {
1904  // TODO: Not all attributes require an exact definition. Find a way to
1905  // enable deduction for some but not all attributes in case the
1906  // definition might be changed at runtime, see also
1907  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1908  // TODO: We could always determine abstract attributes and if sufficient
1909  // information was found we could duplicate the functions that do not
1910  // have an exact definition.
1911  if (!F.hasExactDefinition()) {
1912  NumFnWithoutExactDefinition++;
1913  continue;
1914  }
1915 
1916  // For now we ignore naked and optnone functions.
1917  if (F.hasFnAttribute(Attribute::Naked) ||
1918  F.hasFnAttribute(Attribute::OptimizeNone))
1919  continue;
1920 
1921  NumFnWithExactDefinition++;
1922 
1923  // Populate the Attributor with abstract attribute opportunities in the
1924  // function and the information cache with IR information.
1925  A.identifyDefaultAbstractAttributes(F, InfoCache);
1926  }
1927 
1928  return A.run() == ChangeStatus::CHANGED;
1929 }
1930 
1932  if (runAttributorOnModule(M)) {
1933  // FIXME: Think about passes we will preserve and add them here.
1934  return PreservedAnalyses::none();
1935  }
1936  return PreservedAnalyses::all();
1937 }
1938 
1939 namespace {
1940 
1941 struct AttributorLegacyPass : public ModulePass {
1942  static char ID;
1943 
1944  AttributorLegacyPass() : ModulePass(ID) {
1946  }
1947 
1948  bool runOnModule(Module &M) override {
1949  if (skipModule(M))
1950  return false;
1951  return runAttributorOnModule(M);
1952  }
1953 
1954  void getAnalysisUsage(AnalysisUsage &AU) const override {
1955  // FIXME: Think about passes we will preserve and add them here.
1956  AU.setPreservesCFG();
1957  }
1958 };
1959 
1960 } // end anonymous namespace
1961 
1962 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
1963 
1964 char AttributorLegacyPass::ID = 0;
1965 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
1966  "Deduce and propagate attributes", false, false)
1967 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
1968  "Deduce and propagate attributes", false, false)
AbstractState & getState() override
See AbstractAttribute::getState() {.
size_t size() const
Definition: Function.h:685
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
ManifestPosition getManifestPosition() const override
}
Definition: Attributor.cpp:961
uint64_t CallInst * C
Return a value (possibly void), from a function.
AbstractState & getState() override
See AbstractAttribute::getState() {.
Definition: Attributor.cpp:771
Function & getAnchorScope()
}
Definition: Attributor.cpp:368
static bool isNonRelaxedAtomic(Instruction *I)
Helper function used to determine whether an instruction is non-relaxed atomic.
Definition: Attributor.cpp:804
iterator_range< use_iterator > uses()
Definition: Value.h:354
StringRef getKindAsString() const
Return the attribute&#39;s kind as a string.
Definition: Attributes.cpp:216
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old)
Return true if New is equal or worse than Old.
Definition: Attributor.cpp:250
void indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...).
Definition: Attributor.cpp:565
bool isKnownNoSync() const override
See AANoSync::isKnownNoSync()
Definition: Attributor.cpp:789
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
virtual void indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
An attribute for a function as a whole.
Definition: Attributor.h:520
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
This is the interface for a simple mod/ref and alias analysis over globals.
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
const AbstractState & getState() const override
Return the internal abstract state for inspection.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void initialize(Attributor &A) override
See AbstractAttriubute::initialize(...).
DenseSet< BasicBlock * > AssumedLiveBlocks
Collection of all assumed live BasicBlocks.
bool isAssumedNoSync() const override
See AANoSync::isAssumedNoSync()
Definition: Attributor.cpp:786
ChangeStatus
Simple enum class that forces the status to be spelled out explicitly.
Definition: Attributor.h:114
virtual void print(raw_ostream &OS) const
Helper functions, for debug purposes only.
ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
Definition: Attributor.cpp:536
ManifestPosition getManifestPosition() const override
}
Definition: Attributor.cpp:776
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
AAIsDeadFunction(Function &F, InformationCache &InfoCache)
bool isKnownNoUnwind() const override
See AANoUnwind::isKnownNoUnwind().
Definition: Attributor.cpp:410
Abstract Attribute Classes
Definition: Attributor.h:664
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
An abstract attribute for willreturn.
Definition: Attributor.h:767
STATISTIC(NumFunctions, "Total number of functions")
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1978
F(f)
bool isAssumedNonNull() const override
See AANonNull::isAssumedNonNull().
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(Attributor &A).
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:111
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
--------------------—NoUnwind Function Attribute-----------------------—
Definition: Attributor.cpp:385
bool isAssumedWillReturn() const override
See AAWillReturn::isAssumedWillReturn().
NoAlias attribute for function return value.
AbstractState & getState() override
See AbstractAttribute::getState() {.
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
bool containsPossiblyEndlessLoop(Function &F)
AAWillReturnImpl(Function &F, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
An attribute for a function argument.
Definition: Attributor.h:518
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
bool checkForAllCallSites(Function &F, std::function< bool(CallSite)> &Pred, bool RequireAllCallSites)
Check Pred on all function call sites.
const AbstractState & getState() const override
Return the internal abstract state for inspection.
Definition: Attributor.cpp:772
static bool runAttributorOnModule(Module &M)
}
AbstractState & getState() override
See AbstractAttribute::getState() {.
Definition: Attributor.cpp:956
const std::string getAsStr() const override
See AbstractAttribute::getAsStr()
bool isAssumedNoAlias() const override
See AANoAlias::isAssumedNoAlias().
An AbstractAttribute for noreturn.
Definition: Attributor.h:809
uint64_t getValueAsInt() const
Return the attribute&#39;s value as an integer.
Definition: Attributes.cpp:209
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:194
static constexpr Attribute::AttrKind ID
The identifier used by the Attributor for this class of attributes.
Definition: Attributor.h:681
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
AANonNullImpl(Value &V, InformationCache &InfoCache)
An abstract attribute for norecurse.
Definition: Attributor.h:745
const AAType * getAAFor(AbstractAttribute &QueryingAA, const Value &V, int ArgNo=-1)
Lookup an abstract attribute of type AAType anchored at value V and argument number ArgNo...
Definition: Attributor.h:174
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:893
This file contains the simple types necessary to represent the attributes associated with functions a...
AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo, InformationCache &InfoCache)
See AANonNullImpl::AANonNullImpl(...).
bool explorePath(Attributor &A, Instruction *I)
Explores new instructions starting from I.
ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
static cl::opt< unsigned > MaxFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32))
An abstract interface for all noalias attributes.
Definition: Attributor.h:789
Optional< Value * > getAssumedUniqueReturnValue() const
Return an assumed unique return value if a single candidate is found.
Definition: Attributor.cpp:605
InformationCache & InfoCache
The information cache accessible to this abstract attribute.
Definition: Attributor.h:641
AtomicOrdering
Atomic ordering for LLVM&#39;s memory model.
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.cpp:301
attributor
An attribute for a call site argument.
Definition: Attributor.h:519
ManifestPosition getManifestPosition() const override
}
Definition: Attributor.cpp:397
const AbstractState & getState() const override
Return the internal abstract state for inspection.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
An abstract interface for liveness abstract attribute.
Definition: Attributor.h:829
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.cpp:491
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
Attribute::AttrKind getAttrKind() const override
See AbstractAttribute::getAttrKind().
Definition: Attributor.cpp:972
---------------------— No-Free Attributes -------------------------—
Definition: Attributor.cpp:948
void initializeAttributorLegacyPassPass(PassRegistry &)
std::function< void(Value *, StateTy &State)> visitValueCB_t
Definition: Attributor.cpp:154
void indicatePessimisticFixpoint() override
Indicate that the abstract state should converge to the pessimistic state.
Definition: Attributor.cpp:569
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the call or the callee has the given attribute.
Definition: CallSite.h:385
AANoAliasReturned(Function &F, InformationCache &InfoCache)
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:223
AANoSyncFunction(Function &F, InformationCache &InfoCache)
Definition: Attributor.cpp:766
An abstract interface for all nonnull attributes.
Definition: Attributor.h:720
virtual Attribute::AttrKind getAttrKind() const =0
Return the kind that identifies the abstract attribute implementation.
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
virtual void indicateOptimisticFixpoint()=0
Indicate that the abstract state should converge to the optimistic state.
NonNull attribute for a call site argument.
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:286
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
virtual bool isAtFixpoint() const =0
Return if this abstract state is fixed, thus does not need to be updated if information changes as it...
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
bool isValidState() const override
See AbstractState::isValidState().
Definition: Attributor.cpp:562
InstructionVectorTy & getReadOrWriteInstsForFunction(Function &F)
Return the instructions in F that may read or write memory.
Definition: Attributor.h:324
void initialize(Attributor &A) override
Initialize the state with the information in the Attributor A.
bool isKnownNoFree() const
Return true if "nofree" is known.
Definition: Attributor.cpp:978
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:140
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, AttributeList &Attrs, AbstractAttribute::ManifestPosition MP, unsigned ArgNo=0)
Return true if the information provided by Attr was added to the attribute list Attrs.
Definition: Attributor.cpp:260
static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP, unsigned ArgNo=0)
Helper to identify the correct offset into an attribute list.
Definition: Attributor.cpp:235
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:168
Value * AssociatedVal
The value this abstract attribute is associated with.
Definition: Attributor.h:635
bool isKnownWillReturn() const override
See AAWillReturn::isKnownWillReturn().
bool containsCycle(Function &F)
ManifestPosition
The positions attributes can be manifested in.
Definition: Attributor.h:517
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
unsigned getNumArgOperands() const
Definition: CallSite.h:303
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
bool hasNonNullAttr() const
Return true if this argument has the nonnull attribute.
Definition: Function.cpp:75
const std::string getAsStr() const override
}
This is an important base class in LLVM.
Definition: Constant.h:41
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
Definition: Function.h:607
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
const Instruction & front() const
Definition: BasicBlock.h:280
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:337
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:193
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
static bool isNoSyncIntrinsic(Instruction *I)
Helper function uset to check if intrinsic is volatile (memcpy, memmove, memset). ...
Definition: Attributor.cpp:853
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:550
bool hasInternalLinkage() const
Definition: GlobalValue.h:443
static constexpr Attribute::AttrKind ID
The identifier used by the Attributor for this class of attributes.
Definition: Attributor.h:805
void initialize(Attributor &A) override
See AbstractAttriubute::initialize(...).
Attribute::AttrKind getKindAsEnum() const
Return the attribute&#39;s kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:202
bool isEnumAttribute() const
Return true if the attribute is an Attribute::AttrKind type.
Definition: Attributes.cpp:186
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:722
AbstractState & getState() override
See AbstractAttribute::getState() {.
Definition: Attributor.cpp:392
---------------—— Function Return Values -------------------------——
Definition: Attributor.cpp:446
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
virtual ManifestPosition getManifestPosition() const =0
}
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:413
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
AANoAliasImpl(Value &V, InformationCache &InfoCache)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:205
An attribute for the function return value.
Definition: Attributor.h:521
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Value & getAnchoredValue()
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:563
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
Definition: Value.cpp:535
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Attribute getAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return the attribute object that exists at the given index.
size_t size() const
Definition: SmallVector.h:52
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:514
bool isAssumedNoUnwind() const override
See AANoUnwind::isAssumedNoUnwind().
Definition: Attributor.cpp:407
static bool isVolatile(Instruction *I)
Helper function used to determine whether an instruction is volatile.
Definition: Attributor.cpp:875
std::function< bool(Value &)> generatePredicate(Attributor &)
Generate a predicate that checks if a given value is assumed nonnull.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const AbstractState & getState() const override
See AbstractAttribute::getState(...).
Definition: Attributor.cpp:533
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
size_type size() const
Definition: SmallPtrSet.h:92
virtual void getDeducedAttributes(SmallVectorImpl< Attribute > &Attrs) const
Return the deduced attributes in Attrs.
Definition: Attributor.h:590
static void bookkeeping(AbstractAttribute::ManifestPosition MP, const Attribute &Attr)
}
Definition: Attributor.cpp:105
void changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoek into a normall call.
Definition: Local.cpp:1967
virtual const AbstractState & getState() const =0
Return the internal abstract state for inspection.
const std::string getAsStr() const override
Pretty print the attribute similar to the IR representation.
Definition: Attributor.cpp:600
Value & AnchoredVal
The value this abstract attribute is anchored at.
Definition: Attributor.h:638
static bool genericValueTraversal(Value *InitV, StateTy &State, visitValueCB_t< StateTy > &VisitValueCB, followValueCB_t< StateTy > *FollowValueCB=nullptr, int MaxValues=8)
Recursively visit all values that might become InitV at some point.
Definition: Attributor.cpp:165
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:310
AAWillReturnFunction(Function &F, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
bool isConvergent() const
Determine if the call is convergent.
Definition: CallSite.h:534
bool checkForallReturnedValues(std::function< bool(Value &)> &Pred) const override
See AbstractState::checkForallReturnedValues(...).
Definition: Attributor.cpp:636
static cl::opt< bool > VerifyAttributor("attributor-verify", cl::Hidden, cl::desc("Verify the Attributor deduction and " "manifestation of attributes -- may issue false-positive errors"), cl::init(false))
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:984
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:226
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
----------------—AAIsDead Function Attribute--------------------—
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
OpcodeInstMapTy & getOpcodeInstMapForFunction(Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F...
Definition: Attributor.h:316
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if this function has the given attribute.
Definition: CallSite.h:370
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(Attributor &A).
Definition: Attributor.cpp:657
---------------------— Will-Return Attributes -------------------------—
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
Definition: Argument.h:47
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
ManifestPosition getManifestPosition() const override
}
virtual const std::string getAsStr() const =0
This function should return the "summarized" assumed state as string.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue, InformationCache &InfoCache)
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
bool isAssumedDead(BasicBlock *BB) const override
See AAIsDead::isAssumedDead().
void identifyDefaultAbstractAttributes(Function &F, InformationCache &InfoCache, DenseSet< unsigned > *Whitelist=nullptr)
Determine opportunities to derive &#39;default&#39; attributes in F and create abstract attribute objects for...
const AbstractState & getState() const override
Return the internal abstract state for inspection.
Definition: Attributor.cpp:393
INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) INITIALIZE_PASS_END(AttributorLegacyPass
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:190
#define Success
AbstractState & getState() override
See AbstractAttribute::getState() {.
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:363
void initialize(Attributor &A) override
See AbstractAttriubute::initialize(...).
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool hasValue() const
Definition: Optional.h:259
LLVM_NODISCARD AttributeList addAttribute(LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const
Add an attribute to the attribute set at the given index.
std::function< bool(Value *, StateTy &State)> followValueCB_t
Definition: Attributor.cpp:152
iterator begin() const
Definition: SmallPtrSet.h:396
AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
Definition: Attributor.cpp:484
Pass * createAttributorLegacyPass()
---------------------— NoAlias Argument Attribute ---------------------—
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
NonNull attribute for function return value.
bool isAssumedNoFree() const
Return true if "nofree" is assumed.
Definition: Attributor.cpp:975
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
Definition: Attributor.cpp:964
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:416
Establish a view to a call site for examination.
Definition: CallSite.h:897
size_t size() const
Definition: Module.h:606
AANonNullReturned(Function &F, InformationCache &InfoCache)
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
AANoUnwindFunction(Function &F, InformationCache &InfoCache)
Definition: Attributor.cpp:387
SmallSetVector< Instruction *, 4 > NoReturnCalls
Collection of calls with noreturn attribute, assumed or knwon.
AbstractState & getState() override
See AbstractAttribute::getState(...).
---------------------— NonNull Argument Attribute ---------------------—
const AbstractState & getState() const override
See AbstractAttribute::getState(...).
uint32_t Size
Definition: Profile.cpp:46
size_t getNumReturnValues() const
Return the number of potential return values, -1 if unknown.
Definition: Attributor.cpp:542
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
virtual ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
---------------------— NoSync Function Attribute ----------------------—
Definition: Attributor.cpp:764
AANonNullArgument(Argument &A, InformationCache &InfoCache)
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
iterator end() const
Definition: SmallPtrSet.h:401
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.cpp:575
ManifestPosition getManifestPosition() const override
See AbstractAttribute::getManifestPosition().
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
Definition: Attributor.cpp:399
bool isKnownDead(BasicBlock *BB) const override
See AAIsDead::isKnownDead().
iterator_range< df_iterator< T > > depth_first(const T &G)
Synchronized with respect to signal handlers executing in the same thread.
Definition: LLVMContext.h:51
Deduce and propagate attributes
virtual Value * getAssociatedValue()
}
Definition: Attributor.h:579
const AbstractState & getState() const override
Return the internal abstract state for inspection.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isKnownNonNull() const override
See AANonNull::isKnownNonNull().
AANoFreeFunction(Function &F, InformationCache &InfoCache)
See AbstractAttribute::AbstractAttribute(...).
Definition: Attributor.cpp:951
LLVM Value Representation.
Definition: Value.h:72
static cl::opt< bool > DisableAttributor("attributor-disable", cl::Hidden, cl::desc("Disable the attributor inter-procedural deduction pass."), cl::init(true))
A vector that has set insertion semantics.
Definition: SetVector.h:40
bool returnDoesNotAlias() const
Determine if the return value is marked with NoAlias attribute.
Definition: CallSite.h:436
succ_range successors(Instruction *I)
Definition: CFG.h:259
static const Function * getParent(const Value *V)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
NonNull attribute for function argument.
print Print MemDeps of function
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
bool isKnownNoAlias() const override
See AANoAlias::isKnowndNoAlias().
static bool isVolatile(Instruction *Inst)
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:1998
virtual ChangeStatus updateImpl(Attributor &A)=0
The actual update/transfer function which has to be implemented by the derived classes.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
Definition: Attributor.cpp:778
const std::string getAsStr() const override
}
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint().
Definition: Attributor.cpp:559
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1923
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:133
const AbstractState & getState() const override
Return the internal abstract state for inspection.
Definition: Attributor.cpp:957
static constexpr Attribute::AttrKind ID
The identifier used by the Attributor for this class of attributes.
Definition: Attributor.h:741
ValTy * getArgOperand(unsigned i) const
Definition: CallSite.h:307
iterator_range< arg_iterator > args()
Definition: Function.h:713
AbstractState & getState() override
See AbstractAttribute::getState(...).
Definition: Attributor.cpp:530
const BasicBlock * getParent() const
Definition: Instruction.h:66
Simple wrapper for a single bit (boolean) state.
Definition: Attributor.h:467
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:69
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=DefaultMaxUsesToExplore)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
virtual ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
SmallSetVector< Instruction *, 8 > ToBeExploredPaths
Collection of to be explored paths.