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/Analysis/Loads.h"
29 #include "llvm/IR/Argument.h"
30 #include "llvm/IR/Attributes.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/InstIterator.h"
33 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/Support/Debug.h"
39 
40 #include <cassert>
41 
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "attributor"
45 
46 STATISTIC(NumFnWithExactDefinition,
47  "Number of function with exact definitions");
48 STATISTIC(NumFnWithoutExactDefinition,
49  "Number of function without exact definitions");
50 STATISTIC(NumAttributesTimedOut,
51  "Number of abstract attributes timed out before fixpoint");
52 STATISTIC(NumAttributesValidFixpoint,
53  "Number of abstract attributes in a valid fixpoint state");
54 STATISTIC(NumAttributesManifested,
55  "Number of abstract attributes manifested in IR");
56 
57 // Some helper macros to deal with statistics tracking.
58 //
59 // Usage:
60 // For simple IR attribute tracking overload trackStatistics in the abstract
61 // attribute and choose the right STATS_DECLTRACK_********* macro,
62 // e.g.,:
63 // void trackStatistics() const override {
64 // STATS_DECLTRACK_ARG_ATTR(returned)
65 // }
66 // If there is a single "increment" side one can use the macro
67 // STATS_DECLTRACK with a custom message. If there are multiple increment
68 // sides, STATS_DECL and STATS_TRACK can also be used separatly.
69 //
70 #define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME) \
71  ("Number of " #TYPE " marked '" #NAME "'")
72 #define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME
73 #define STATS_DECL(NAME, TYPE, MSG) STATISTIC(BUILD_STAT_NAME(NAME, TYPE), MSG);
74 #define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE));
75 #define STATS_DECLTRACK(NAME, TYPE, MSG) \
76  { \
77  STATS_DECL(NAME, TYPE, MSG) \
78  STATS_TRACK(NAME, TYPE) \
79  }
80 #define STATS_DECLTRACK_ARG_ATTR(NAME) \
81  STATS_DECLTRACK(NAME, Arguments, BUILD_STAT_MSG_IR_ATTR(arguments, NAME))
82 #define STATS_DECLTRACK_CSARG_ATTR(NAME) \
83  STATS_DECLTRACK(NAME, CSArguments, \
84  BUILD_STAT_MSG_IR_ATTR(call site arguments, NAME))
85 #define STATS_DECLTRACK_FN_ATTR(NAME) \
86  STATS_DECLTRACK(NAME, Function, BUILD_STAT_MSG_IR_ATTR(functions, NAME))
87 #define STATS_DECLTRACK_CS_ATTR(NAME) \
88  STATS_DECLTRACK(NAME, CS, BUILD_STAT_MSG_IR_ATTR(call site, NAME))
89 #define STATS_DECLTRACK_FNRET_ATTR(NAME) \
90  STATS_DECLTRACK(NAME, FunctionReturn, \
91  BUILD_STAT_MSG_IR_ATTR(function returns, NAME));
92 #define STATS_DECLTRACK_CSRET_ATTR(NAME) \
93  STATS_DECLTRACK(NAME, CSReturn, \
94  BUILD_STAT_MSG_IR_ATTR(call site returns, NAME))
95 #define STATS_DECLTRACK_FLOATING_ATTR(NAME) \
96  STATS_DECLTRACK(NAME, Floating, \
97  ("Number of floating values known to be '" #NAME "'"))
98 
99 // TODO: Determine a good default value.
100 //
101 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
102 // (when run with the first 5 abstract attributes). The results also indicate
103 // that we never reach 32 iterations but always find a fixpoint sooner.
104 //
105 // This will become more evolved once we perform two interleaved fixpoint
106 // iterations: bottom-up and top-down.
107 static cl::opt<unsigned>
108  MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
109  cl::desc("Maximal number of fixpoint iterations."),
110  cl::init(32));
111 
113  "attributor-disable", cl::Hidden,
114  cl::desc("Disable the attributor inter-procedural deduction pass."),
115  cl::init(true));
116 
118  "attributor-verify", cl::Hidden,
119  cl::desc("Verify the Attributor deduction and "
120  "manifestation of attributes -- may issue false-positive errors"),
121  cl::init(false));
122 
123 /// Logic operators for the change status enum class.
124 ///
125 ///{
127  return l == ChangeStatus::CHANGED ? l : r;
128 }
130  return l == ChangeStatus::UNCHANGED ? l : r;
131 }
132 ///}
133 
134 /// Recursively visit all values that might become \p IRP at some point. This
135 /// will be done by looking through cast instructions, selects, phis, and calls
136 /// with the "returned" attribute. Once we cannot look through the value any
137 /// further, the callback \p VisitValueCB is invoked and passed the current
138 /// value, the \p State, and a flag to indicate if we stripped anything. To
139 /// limit how much effort is invested, we will never visit more values than
140 /// specified by \p MaxValues.
141 template <typename AAType, typename StateTy>
143  Attributor &A, IRPosition IRP, const AAType &QueryingAA, StateTy &State,
144  const function_ref<bool(Value &, StateTy &, bool)> &VisitValueCB,
145  int MaxValues = 8) {
146 
147  const AAIsDead *LivenessAA = nullptr;
148  if (IRP.getAnchorScope())
149  LivenessAA = &A.getAAFor<AAIsDead>(
150  QueryingAA, IRPosition::function(*IRP.getAnchorScope()));
151 
152  // TODO: Use Positions here to allow context sensitivity in VisitValueCB
153  SmallPtrSet<Value *, 16> Visited;
154  SmallVector<Value *, 16> Worklist;
155  Worklist.push_back(&IRP.getAssociatedValue());
156 
157  int Iteration = 0;
158  do {
159  Value *V = Worklist.pop_back_val();
160 
161  // Check if we should process the current value. To prevent endless
162  // recursion keep a record of the values we followed!
163  if (!Visited.insert(V).second)
164  continue;
165 
166  // Make sure we limit the compile time for complex expressions.
167  if (Iteration++ >= MaxValues)
168  return false;
169 
170  // Explicitly look through calls with a "returned" attribute if we do
171  // not have a pointer as stripPointerCasts only works on them.
172  Value *NewV = nullptr;
173  if (V->getType()->isPointerTy()) {
174  NewV = V->stripPointerCasts();
175  } else {
176  CallSite CS(V);
177  if (CS && CS.getCalledFunction()) {
178  for (Argument &Arg : CS.getCalledFunction()->args())
179  if (Arg.hasReturnedAttr()) {
180  NewV = CS.getArgOperand(Arg.getArgNo());
181  break;
182  }
183  }
184  }
185  if (NewV && NewV != V) {
186  Worklist.push_back(NewV);
187  continue;
188  }
189 
190  // Look through select instructions, visit both potential values.
191  if (auto *SI = dyn_cast<SelectInst>(V)) {
192  Worklist.push_back(SI->getTrueValue());
193  Worklist.push_back(SI->getFalseValue());
194  continue;
195  }
196 
197  // Look through phi nodes, visit all live operands.
198  if (auto *PHI = dyn_cast<PHINode>(V)) {
199  assert(LivenessAA &&
200  "Expected liveness in the presence of instructions!");
201  for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
202  const BasicBlock *IncomingBB = PHI->getIncomingBlock(u);
203  if (!LivenessAA->isAssumedDead(IncomingBB->getTerminator()))
204  Worklist.push_back(PHI->getIncomingValue(u));
205  }
206  continue;
207  }
208 
209  // Once a leaf is reached we inform the user through the callback.
210  if (!VisitValueCB(*V, State, Iteration > 1))
211  return false;
212  } while (!Worklist.empty());
213 
214  // All values have been visited.
215  return true;
216 }
217 
218 /// Return true if \p New is equal or worse than \p Old.
219 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
220  if (!Old.isIntAttribute())
221  return true;
222 
223  return Old.getValueAsInt() >= New.getValueAsInt();
224 }
225 
226 /// Return true if the information provided by \p Attr was added to the
227 /// attribute list \p Attrs. This is only the case if it was not already present
228 /// in \p Attrs at the position describe by \p PK and \p AttrIdx.
229 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
230  AttributeList &Attrs, int AttrIdx) {
231 
232  if (Attr.isEnumAttribute()) {
234  if (Attrs.hasAttribute(AttrIdx, Kind))
235  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
236  return false;
237  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
238  return true;
239  }
240  if (Attr.isStringAttribute()) {
241  StringRef Kind = Attr.getKindAsString();
242  if (Attrs.hasAttribute(AttrIdx, Kind))
243  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
244  return false;
245  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
246  return true;
247  }
248  if (Attr.isIntAttribute()) {
250  if (Attrs.hasAttribute(AttrIdx, Kind))
251  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
252  return false;
253  Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
254  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
255  return true;
256  }
257 
258  llvm_unreachable("Expected enum or string attribute!");
259 }
260 
263  if (getState().isAtFixpoint())
264  return HasChanged;
265 
266  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
267 
268  HasChanged = updateImpl(A);
269 
270  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
271  << "\n");
272 
273  return HasChanged;
274 }
275 
278  const ArrayRef<Attribute> &DeducedAttrs) {
279  Function *ScopeFn = IRP.getAssociatedFunction();
281 
282  // In the following some generic code that will manifest attributes in
283  // DeducedAttrs if they improve the current IR. Due to the different
284  // annotation positions we use the underlying AttributeList interface.
285 
287  switch (PK) {
294  Attrs = ScopeFn->getAttributes();
295  break;
300  break;
301  }
302 
304  LLVMContext &Ctx = IRP.getAnchorValue().getContext();
305  for (const Attribute &Attr : DeducedAttrs) {
306  if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx()))
307  continue;
308 
309  HasChanged = ChangeStatus::CHANGED;
310  }
311 
312  if (HasChanged == ChangeStatus::UNCHANGED)
313  return HasChanged;
314 
315  switch (PK) {
319  ScopeFn->setAttributes(Attrs);
320  break;
324  CallSite(&IRP.getAnchorValue()).setAttributes(Attrs);
325  break;
328  break;
329  }
330 
331  return HasChanged;
332 }
333 
336 
338  IRPositions.emplace_back(IRP);
339 
340  ImmutableCallSite ICS(&IRP.getAnchorValue());
341  switch (IRP.getPositionKind()) {
345  return;
348  IRPositions.emplace_back(
350  return;
352  assert(ICS && "Expected call site!");
353  // TODO: We need to look at the operand bundles similar to the redirection
354  // in CallBase.
355  if (!ICS.hasOperandBundles())
356  if (const Function *Callee = ICS.getCalledFunction())
357  IRPositions.emplace_back(IRPosition::function(*Callee));
358  return;
360  assert(ICS && "Expected call site!");
361  // TODO: We need to look at the operand bundles similar to the redirection
362  // in CallBase.
363  if (!ICS.hasOperandBundles()) {
364  if (const Function *Callee = ICS.getCalledFunction()) {
365  IRPositions.emplace_back(IRPosition::returned(*Callee));
366  IRPositions.emplace_back(IRPosition::function(*Callee));
367  }
368  }
369  IRPositions.emplace_back(
370  IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction())));
371  return;
373  int ArgNo = IRP.getArgNo();
374  assert(ICS && ArgNo >= 0 && "Expected call site!");
375  // TODO: We need to look at the operand bundles similar to the redirection
376  // in CallBase.
377  if (!ICS.hasOperandBundles()) {
378  const Function *Callee = ICS.getCalledFunction();
379  if (Callee && Callee->arg_size() > unsigned(ArgNo))
380  IRPositions.emplace_back(IRPosition::argument(*Callee->getArg(ArgNo)));
381  if (Callee)
382  IRPositions.emplace_back(IRPosition::function(*Callee));
383  }
384  IRPositions.emplace_back(IRPosition::value(IRP.getAssociatedValue()));
385  return;
386  }
387  }
388 }
389 
391  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this))
392  for (Attribute::AttrKind AK : AKs)
393  if (EquivIRP.getAttr(AK).getKindAsEnum() == AK)
394  return true;
395  return false;
396 }
397 
400  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this))
401  for (Attribute::AttrKind AK : AKs) {
402  const Attribute &Attr = EquivIRP.getAttr(AK);
403  if (Attr.getKindAsEnum() == AK)
404  Attrs.push_back(Attr);
405  }
406 }
407 
408 void IRPosition::verify() {
409  switch (KindOrArgNo) {
410  default:
411  assert(KindOrArgNo >= 0 && "Expected argument or call site argument!");
412  assert((isa<CallBase>(AnchorVal) || isa<Argument>(AnchorVal)) &&
413  "Expected call base or argument for positive attribute index!");
414  if (auto *Arg = dyn_cast<Argument>(AnchorVal)) {
415  assert(Arg->getArgNo() == unsigned(getArgNo()) &&
416  "Argument number mismatch!");
417  assert(Arg == &getAssociatedValue() && "Associated value mismatch!");
418  } else {
419  auto &CB = cast<CallBase>(*AnchorVal);
420  (void)CB;
421  assert(CB.arg_size() > unsigned(getArgNo()) &&
422  "Call site argument number mismatch!");
423  assert(CB.getArgOperand(getArgNo()) == &getAssociatedValue() &&
424  "Associated value mismatch!");
425  }
426  break;
427  case IRP_INVALID:
428  assert(!AnchorVal && "Expected no value for an invalid position!");
429  break;
430  case IRP_FLOAT:
431  assert((!isa<CallBase>(&getAssociatedValue()) &&
432  !isa<Argument>(&getAssociatedValue())) &&
433  "Expected specialized kind for call base and argument values!");
434  break;
435  case IRP_RETURNED:
436  assert(isa<Function>(AnchorVal) &&
437  "Expected function for a 'returned' position!");
438  assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!");
439  break;
440  case IRP_CALL_SITE_RETURNED:
441  assert((isa<CallBase>(AnchorVal)) &&
442  "Expected call base for 'call site returned' position!");
443  assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!");
444  break;
445  case IRP_CALL_SITE:
446  assert((isa<CallBase>(AnchorVal)) &&
447  "Expected call base for 'call site function' position!");
448  assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!");
449  break;
450  case IRP_FUNCTION:
451  assert(isa<Function>(AnchorVal) &&
452  "Expected function for a 'function' position!");
453  assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!");
454  break;
455  }
456 }
457 
458 /// Helper functions to clamp a state \p S of type \p StateType with the
459 /// information in \p R and indicate/return if \p S did change (as-in update is
460 /// required to be run again).
461 ///
462 ///{
463 template <typename StateType>
465 
466 template <>
468  const IntegerState &R) {
469  auto Assumed = S.getAssumed();
470  S ^= R;
471  return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
473 }
474 
475 template <>
477  const BooleanState &R) {
479 }
480 ///}
481 
482 /// Clamp the information known for all returned values of a function
483 /// (identified by \p QueryingAA) into \p S.
484 template <typename AAType, typename StateType = typename AAType::StateType>
485 static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA,
486  StateType &S) {
487  LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for "
488  << static_cast<const AbstractAttribute &>(QueryingAA)
489  << " into " << S << "\n");
490 
491  assert((QueryingAA.getIRPosition().getPositionKind() ==
493  QueryingAA.getIRPosition().getPositionKind() ==
495  "Can only clamp returned value states for a function returned or call "
496  "site returned position!");
497 
498  // Use an optional state as there might not be any return values and we want
499  // to join (IntegerState::operator&) the state of all there are.
501 
502  // Callback for each possibly returned value.
503  auto CheckReturnValue = [&](Value &RV) -> bool {
504  const IRPosition &RVPos = IRPosition::value(RV);
505  const AAType &AA = A.getAAFor<AAType>(QueryingAA, RVPos);
506  LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr()
507  << " @ " << RVPos << "\n");
508  const StateType &AAS = static_cast<const StateType &>(AA.getState());
509  if (T.hasValue())
510  *T &= AAS;
511  else
512  T = AAS;
513  LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T
514  << "\n");
515  return T->isValidState();
516  };
517 
518  if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA))
519  S.indicatePessimisticFixpoint();
520  else if (T.hasValue())
521  S ^= *T;
522 }
523 
524 /// Helper class for generic deduction: return value -> returned position.
525 template <typename AAType, typename Base,
526  typename StateType = typename AAType::StateType>
527 struct AAReturnedFromReturnedValues : public Base {
528  AAReturnedFromReturnedValues(const IRPosition &IRP) : Base(IRP) {}
529 
530  /// See AbstractAttribute::updateImpl(...).
532  StateType S;
533  clampReturnedValueStates<AAType, StateType>(A, *this, S);
534  // TODO: If we know we visited all returned values, thus no are assumed
535  // dead, we can take the known information from the state T.
536  return clampStateAndIndicateChange<StateType>(this->getState(), S);
537  }
538 };
539 
540 /// Clamp the information known at all call sites for a given argument
541 /// (identified by \p QueryingAA) into \p S.
542 template <typename AAType, typename StateType = typename AAType::StateType>
543 static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA,
544  StateType &S) {
545  LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for "
546  << static_cast<const AbstractAttribute &>(QueryingAA)
547  << " into " << S << "\n");
548 
549  assert(QueryingAA.getIRPosition().getPositionKind() ==
551  "Can only clamp call site argument states for an argument position!");
552 
553  // Use an optional state as there might not be any return values and we want
554  // to join (IntegerState::operator&) the state of all there are.
556 
557  // The argument number which is also the call site argument number.
558  unsigned ArgNo = QueryingAA.getIRPosition().getArgNo();
559 
560  auto CallSiteCheck = [&](CallSite CS) {
561  const IRPosition &CSArgPos = IRPosition::callsite_argument(CS, ArgNo);
562  const AAType &AA = A.getAAFor<AAType>(QueryingAA, CSArgPos);
563  LLVM_DEBUG(dbgs() << "[Attributor] CS: " << *CS.getInstruction()
564  << " AA: " << AA.getAsStr() << " @" << CSArgPos << "\n");
565  const StateType &AAS = static_cast<const StateType &>(AA.getState());
566  if (T.hasValue())
567  *T &= AAS;
568  else
569  T = AAS;
570  LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T
571  << "\n");
572  return T->isValidState();
573  };
574 
575  if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true))
576  S.indicatePessimisticFixpoint();
577  else if (T.hasValue())
578  S ^= *T;
579 }
580 
581 /// Helper class for generic deduction: call site argument -> argument position.
582 template <typename AAType, typename Base,
583  typename StateType = typename AAType::StateType>
584 struct AAArgumentFromCallSiteArguments : public Base {
585  AAArgumentFromCallSiteArguments(const IRPosition &IRP) : Base(IRP) {}
586 
587  /// See AbstractAttribute::updateImpl(...).
589  StateType S;
590  clampCallSiteArgumentStates<AAType, StateType>(A, *this, S);
591  // TODO: If we know we visited all incoming values, thus no are assumed
592  // dead, we can take the known information from the state T.
593  return clampStateAndIndicateChange<StateType>(this->getState(), S);
594  }
595 };
596 
597 /// Helper class for generic replication: function returned -> cs returned.
598 template <typename AAType, typename Base>
599 struct AACallSiteReturnedFromReturned : public Base {
600  AACallSiteReturnedFromReturned(const IRPosition &IRP) : Base(IRP) {}
601 
602  /// See AbstractAttribute::updateImpl(...).
604  assert(this->getIRPosition().getPositionKind() ==
606  "Can only wrap function returned positions for call site returned "
607  "positions!");
608  auto &S = this->getState();
609 
610  const Function *AssociatedFunction =
612  if (!AssociatedFunction)
613  return S.indicatePessimisticFixpoint();
614 
615  IRPosition FnPos = IRPosition::returned(*AssociatedFunction);
616  const AAType &AA = A.getAAFor<AAType>(*this, FnPos);
618  S, static_cast<const typename AAType::StateType &>(AA.getState()));
619  }
620 };
621 
622 /// -----------------------NoUnwind Function Attribute--------------------------
623 
625  AANoUnwindImpl(const IRPosition &IRP) : AANoUnwind(IRP) {}
626 
627  /// See AbstractAttribute::initialize(...).
628  void initialize(Attributor &A) override {
629  if (hasAttr({Attribute::NoUnwind}))
630  indicateOptimisticFixpoint();
631  }
632 
633  const std::string getAsStr() const override {
634  return getAssumed() ? "nounwind" : "may-unwind";
635  }
636 
637  /// See AbstractAttribute::updateImpl(...).
639  auto Opcodes = {
640  (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
641  (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
642  (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
643 
644  auto CheckForNoUnwind = [&](Instruction &I) {
645  if (!I.mayThrow())
646  return true;
647 
648  if (ImmutableCallSite ICS = ImmutableCallSite(&I)) {
649  const auto &NoUnwindAA =
651  return NoUnwindAA.isAssumedNoUnwind();
652  }
653  return false;
654  };
655 
656  if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes))
657  return indicatePessimisticFixpoint();
658 
660  }
661 };
662 
663 struct AANoUnwindFunction final : public AANoUnwindImpl {
665 
666  /// See AbstractAttribute::trackStatistics()
667  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) }
668 };
669 
670 /// NoUnwind attribute deduction for a call sites.
672 
673 /// --------------------- Function Return Values -------------------------------
674 
675 /// "Attribute" that collects all potential returned values and the return
676 /// instructions that they arise from.
677 ///
678 /// If there is a unique returned value R, the manifest method will:
679 /// - mark R with the "returned" attribute, if R is an argument.
681 
682  /// Mapping of values potentially returned by the associated function to the
683  /// return instructions that might return them.
685 
686  SmallPtrSet<CallBase *, 8> UnresolvedCalls;
687 
688  /// State flags
689  ///
690  ///{
691  bool IsFixed;
692  bool IsValidState;
693  ///}
694 
695 public:
697 
698  /// See AbstractAttribute::initialize(...).
699  void initialize(Attributor &A) override {
700  // Reset the state.
701  IsFixed = false;
702  IsValidState = true;
703  ReturnedValues.clear();
704 
705  Function *F = getAssociatedFunction();
706  if (!F || !F->hasExactDefinition()) {
707  indicatePessimisticFixpoint();
708  return;
709  }
710 
711  // The map from instruction opcodes to those instructions in the function.
712  auto &OpcodeInstMap = A.getInfoCache().getOpcodeInstMapForFunction(*F);
713 
714  // Look through all arguments, if one is marked as returned we are done.
715  for (Argument &Arg : F->args()) {
716  if (Arg.hasReturnedAttr()) {
717  auto &ReturnInstSet = ReturnedValues[&Arg];
718  for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
719  ReturnInstSet.insert(cast<ReturnInst>(RI));
720 
721  indicateOptimisticFixpoint();
722  return;
723  }
724  }
725  }
726 
727  /// See AbstractAttribute::manifest(...).
728  ChangeStatus manifest(Attributor &A) override;
729 
730  /// See AbstractAttribute::getState(...).
731  AbstractState &getState() override { return *this; }
732 
733  /// See AbstractAttribute::getState(...).
734  const AbstractState &getState() const override { return *this; }
735 
736  /// See AbstractAttribute::updateImpl(Attributor &A).
737  ChangeStatus updateImpl(Attributor &A) override;
738 
740  return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
741  }
742 
744  return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
745  }
746 
748  return UnresolvedCalls;
749  }
750 
751  /// Return the number of potential return values, -1 if unknown.
752  size_t getNumReturnValues() const override {
753  return isValidState() ? ReturnedValues.size() : -1;
754  }
755 
756  /// Return an assumed unique return value if a single candidate is found. If
757  /// there cannot be one, return a nullptr. If it is not clear yet, return the
758  /// Optional::NoneType.
759  Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
760 
761  /// See AbstractState::checkForAllReturnedValues(...).
762  bool checkForAllReturnedValuesAndReturnInsts(
763  const function_ref<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)>
764  &Pred) const override;
765 
766  /// Pretty print the attribute similar to the IR representation.
767  const std::string getAsStr() const override;
768 
769  /// See AbstractState::isAtFixpoint().
770  bool isAtFixpoint() const override { return IsFixed; }
771 
772  /// See AbstractState::isValidState().
773  bool isValidState() const override { return IsValidState; }
774 
775  /// See AbstractState::indicateOptimisticFixpoint(...).
777  IsFixed = true;
778  IsValidState &= true;
780  }
781 
783  IsFixed = true;
784  IsValidState = false;
785  return ChangeStatus::CHANGED;
786  }
787 };
788 
791 
792  // Bookkeeping.
793  assert(isValidState());
794  STATS_DECLTRACK(KnownReturnValues, FunctionReturn,
795  "Number of function with known return values");
796 
797  // Check if we have an assumed unique return value that we could manifest.
798  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue(A);
799 
800  if (!UniqueRV.hasValue() || !UniqueRV.getValue())
801  return Changed;
802 
803  // Bookkeeping.
804  STATS_DECLTRACK(UniqueReturnValue, FunctionReturn,
805  "Number of function with unique return");
806 
807  // If the assumed unique return value is an argument, annotate it.
808  if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
809  getIRPosition() = IRPosition::argument(*UniqueRVArg);
810  Changed = IRAttribute::manifest(A) | Changed;
811  }
812 
813  return Changed;
814 }
815 
816 const std::string AAReturnedValuesImpl::getAsStr() const {
817  return (isAtFixpoint() ? "returns(#" : "may-return(#") +
818  (isValidState() ? std::to_string(getNumReturnValues()) : "?") +
819  ")[#UC: " + std::to_string(UnresolvedCalls.size()) + "]";
820 }
821 
824  // If checkForAllReturnedValues provides a unique value, ignoring potential
825  // undef values that can also be present, it is assumed to be the actual
826  // return value and forwarded to the caller of this method. If there are
827  // multiple, a nullptr is returned indicating there cannot be a unique
828  // returned value.
829  Optional<Value *> UniqueRV;
830 
831  auto Pred = [&](Value &RV) -> bool {
832  // If we found a second returned value and neither the current nor the saved
833  // one is an undef, there is no unique returned value. Undefs are special
834  // since we can pretend they have any value.
835  if (UniqueRV.hasValue() && UniqueRV != &RV &&
836  !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
837  UniqueRV = nullptr;
838  return false;
839  }
840 
841  // Do not overwrite a value with an undef.
842  if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
843  UniqueRV = &RV;
844 
845  return true;
846  };
847 
848  if (!A.checkForAllReturnedValues(Pred, *this))
849  UniqueRV = nullptr;
850 
851  return UniqueRV;
852 }
853 
855  const function_ref<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)>
856  &Pred) const {
857  if (!isValidState())
858  return false;
859 
860  // Check all returned values but ignore call sites as long as we have not
861  // encountered an overdefined one during an update.
862  for (auto &It : ReturnedValues) {
863  Value *RV = It.first;
864  const SmallPtrSetImpl<ReturnInst *> &RetInsts = It.second;
865 
866  CallBase *CB = dyn_cast<CallBase>(RV);
867  if (CB && !UnresolvedCalls.count(CB))
868  continue;
869 
870  if (!Pred(*RV, RetInsts))
871  return false;
872  }
873 
874  return true;
875 }
876 
878  size_t NumUnresolvedCalls = UnresolvedCalls.size();
879  bool Changed = false;
880 
881  // State used in the value traversals starting in returned values.
882  struct RVState {
883  // The map in which we collect return values -> return instrs.
884  decltype(ReturnedValues) &RetValsMap;
885  // The flag to indicate a change.
886  bool &Changed;
887  // The return instrs we come from.
889  };
890 
891  // Callback for a leaf value returned by the associated function.
892  auto VisitValueCB = [](Value &Val, RVState &RVS, bool) -> bool {
893  auto Size = RVS.RetValsMap[&Val].size();
894  RVS.RetValsMap[&Val].insert(RVS.RetInsts.begin(), RVS.RetInsts.end());
895  bool Inserted = RVS.RetValsMap[&Val].size() != Size;
896  RVS.Changed |= Inserted;
897  LLVM_DEBUG({
898  if (Inserted)
899  dbgs() << "[AAReturnedValues] 1 Add new returned value " << Val
900  << " => " << RVS.RetInsts.size() << "\n";
901  });
902  return true;
903  };
904 
905  // Helper method to invoke the generic value traversal.
906  auto VisitReturnedValue = [&](Value &RV, RVState &RVS) {
907  IRPosition RetValPos = IRPosition::value(RV);
908  return genericValueTraversal<AAReturnedValues, RVState>(A, RetValPos, *this,
909  RVS, VisitValueCB);
910  };
911 
912  // Callback for all "return intructions" live in the associated function.
913  auto CheckReturnInst = [this, &VisitReturnedValue, &Changed](Instruction &I) {
914  ReturnInst &Ret = cast<ReturnInst>(I);
915  RVState RVS({ReturnedValues, Changed, {}});
916  RVS.RetInsts.insert(&Ret);
917  return VisitReturnedValue(*Ret.getReturnValue(), RVS);
918  };
919 
920  // Start by discovering returned values from all live returned instructions in
921  // the associated function.
922  if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}))
923  return indicatePessimisticFixpoint();
924 
925  // Once returned values "directly" present in the code are handled we try to
926  // resolve returned calls.
927  decltype(ReturnedValues) NewRVsMap;
928  for (auto &It : ReturnedValues) {
929  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *It.first
930  << " by #" << It.second.size() << " RIs\n");
931  CallBase *CB = dyn_cast<CallBase>(It.first);
932  if (!CB || UnresolvedCalls.count(CB))
933  continue;
934 
935  const auto &RetValAA =
937  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Found another AAReturnedValues: "
938  << static_cast<const AbstractAttribute &>(RetValAA)
939  << "\n");
940 
941  // Skip dead ends, thus if we do not know anything about the returned
942  // call we mark it as unresolved and it will stay that way.
943  if (!RetValAA.getState().isValidState()) {
944  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB
945  << "\n");
946  UnresolvedCalls.insert(CB);
947  continue;
948  }
949 
950  // Do not try to learn partial information. If the callee has unresolved
951  // return values we will treat the call as unresolved/opaque.
952  auto &RetValAAUnresolvedCalls = RetValAA.getUnresolvedCalls();
953  if (!RetValAAUnresolvedCalls.empty()) {
954  UnresolvedCalls.insert(CB);
955  continue;
956  }
957 
958  // Now check if we can track transitively returned values. If possible, thus
959  // if all return value can be represented in the current scope, do so.
960  bool Unresolved = false;
961  for (auto &RetValAAIt : RetValAA.returned_values()) {
962  Value *RetVal = RetValAAIt.first;
963  if (isa<Argument>(RetVal) || isa<CallBase>(RetVal) ||
964  isa<Constant>(RetVal))
965  continue;
966  // Anything that did not fit in the above categories cannot be resolved,
967  // mark the call as unresolved.
968  LLVM_DEBUG(dbgs() << "[AAReturnedValues] transitively returned value "
969  "cannot be translated: "
970  << *RetVal << "\n");
971  UnresolvedCalls.insert(CB);
972  Unresolved = true;
973  break;
974  }
975 
976  if (Unresolved)
977  continue;
978 
979  for (auto &RetValAAIt : RetValAA.returned_values()) {
980  Value *RetVal = RetValAAIt.first;
981  if (Argument *Arg = dyn_cast<Argument>(RetVal)) {
982  // Arguments are mapped to call site operands and we begin the traversal
983  // again.
984  bool Unused = false;
985  RVState RVS({NewRVsMap, Unused, RetValAAIt.second});
986  VisitReturnedValue(*CB->getArgOperand(Arg->getArgNo()), RVS);
987  continue;
988  } else if (isa<CallBase>(RetVal)) {
989  // Call sites are resolved by the callee attribute over time, no need to
990  // do anything for us.
991  continue;
992  } else if (isa<Constant>(RetVal)) {
993  // Constants are valid everywhere, we can simply take them.
994  NewRVsMap[RetVal].insert(It.second.begin(), It.second.end());
995  continue;
996  }
997  }
998  }
999 
1000  // To avoid modifications to the ReturnedValues map while we iterate over it
1001  // we kept record of potential new entries in a copy map, NewRVsMap.
1002  for (auto &It : NewRVsMap) {
1003  assert(!It.second.empty() && "Entry does not add anything.");
1004  auto &ReturnInsts = ReturnedValues[It.first];
1005  for (ReturnInst *RI : It.second)
1006  if (ReturnInsts.insert(RI).second) {
1007  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
1008  << *It.first << " => " << *RI << "\n");
1009  Changed = true;
1010  }
1011  }
1012 
1013  Changed |= (NumUnresolvedCalls != UnresolvedCalls.size());
1015 }
1016 
1019 
1020  /// See AbstractAttribute::trackStatistics()
1021  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(returned) }
1022 };
1023 
1024 /// Returned values information for a call sites.
1026 
1027 /// ------------------------ NoSync Function Attribute -------------------------
1028 
1030  AANoSyncImpl(const IRPosition &IRP) : AANoSync(IRP) {}
1031 
1032  /// See AbstractAttribute::initialize(...).
1033  void initialize(Attributor &A) override {
1034  if (hasAttr({Attribute::NoSync}))
1035  indicateOptimisticFixpoint();
1036  }
1037 
1038  const std::string getAsStr() const override {
1039  return getAssumed() ? "nosync" : "may-sync";
1040  }
1041 
1042  /// See AbstractAttribute::updateImpl(...).
1043  ChangeStatus updateImpl(Attributor &A) override;
1044 
1045  /// Helper function used to determine whether an instruction is non-relaxed
1046  /// atomic. In other words, if an atomic instruction does not have unordered
1047  /// or monotonic ordering
1048  static bool isNonRelaxedAtomic(Instruction *I);
1049 
1050  /// Helper function used to determine whether an instruction is volatile.
1051  static bool isVolatile(Instruction *I);
1052 
1053  /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
1054  /// memset).
1055  static bool isNoSyncIntrinsic(Instruction *I);
1056 };
1057 
1059  if (!I->isAtomic())
1060  return false;
1061 
1062  AtomicOrdering Ordering;
1063  switch (I->getOpcode()) {
1064  case Instruction::AtomicRMW:
1065  Ordering = cast<AtomicRMWInst>(I)->getOrdering();
1066  break;
1067  case Instruction::Store:
1068  Ordering = cast<StoreInst>(I)->getOrdering();
1069  break;
1070  case Instruction::Load:
1071  Ordering = cast<LoadInst>(I)->getOrdering();
1072  break;
1073  case Instruction::Fence: {
1074  auto *FI = cast<FenceInst>(I);
1075  if (FI->getSyncScopeID() == SyncScope::SingleThread)
1076  return false;
1077  Ordering = FI->getOrdering();
1078  break;
1079  }
1080  case Instruction::AtomicCmpXchg: {
1081  AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
1082  AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
1083  // Only if both are relaxed, than it can be treated as relaxed.
1084  // Otherwise it is non-relaxed.
1085  if (Success != AtomicOrdering::Unordered &&
1086  Success != AtomicOrdering::Monotonic)
1087  return true;
1088  if (Failure != AtomicOrdering::Unordered &&
1089  Failure != AtomicOrdering::Monotonic)
1090  return true;
1091  return false;
1092  }
1093  default:
1095  "New atomic operations need to be known in the attributor.");
1096  }
1097 
1098  // Relaxed.
1099  if (Ordering == AtomicOrdering::Unordered ||
1100  Ordering == AtomicOrdering::Monotonic)
1101  return false;
1102  return true;
1103 }
1104 
1105 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
1106 /// FIXME: We should ipmrove the handling of intrinsics.
1108  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1109  switch (II->getIntrinsicID()) {
1110  /// Element wise atomic memory intrinsics are can only be unordered,
1111  /// therefore nosync.
1112  case Intrinsic::memset_element_unordered_atomic:
1113  case Intrinsic::memmove_element_unordered_atomic:
1114  case Intrinsic::memcpy_element_unordered_atomic:
1115  return true;
1116  case Intrinsic::memset:
1117  case Intrinsic::memmove:
1118  case Intrinsic::memcpy:
1119  if (!cast<MemIntrinsic>(II)->isVolatile())
1120  return true;
1121  return false;
1122  default:
1123  return false;
1124  }
1125  }
1126  return false;
1127 }
1128 
1130  assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
1131  "Calls should not be checked here");
1132 
1133  switch (I->getOpcode()) {
1134  case Instruction::AtomicRMW:
1135  return cast<AtomicRMWInst>(I)->isVolatile();
1136  case Instruction::Store:
1137  return cast<StoreInst>(I)->isVolatile();
1138  case Instruction::Load:
1139  return cast<LoadInst>(I)->isVolatile();
1140  case Instruction::AtomicCmpXchg:
1141  return cast<AtomicCmpXchgInst>(I)->isVolatile();
1142  default:
1143  return false;
1144  }
1145 }
1146 
1148 
1149  auto CheckRWInstForNoSync = [&](Instruction &I) {
1150  /// We are looking for volatile instructions or Non-Relaxed atomics.
1151  /// FIXME: We should ipmrove the handling of intrinsics.
1152 
1153  if (isa<IntrinsicInst>(&I) && isNoSyncIntrinsic(&I))
1154  return true;
1155 
1156  if (ImmutableCallSite ICS = ImmutableCallSite(&I)) {
1157  if (ICS.hasFnAttr(Attribute::NoSync))
1158  return true;
1159 
1160  const auto &NoSyncAA =
1162  if (NoSyncAA.isAssumedNoSync())
1163  return true;
1164  return false;
1165  }
1166 
1167  if (!isVolatile(&I) && !isNonRelaxedAtomic(&I))
1168  return true;
1169 
1170  return false;
1171  };
1172 
1173  auto CheckForNoSync = [&](Instruction &I) {
1174  // At this point we handled all read/write effects and they are all
1175  // nosync, so they can be skipped.
1176  if (I.mayReadOrWriteMemory())
1177  return true;
1178 
1179  // non-convergent and readnone imply nosync.
1180  return !ImmutableCallSite(&I).isConvergent();
1181  };
1182 
1183  if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this) ||
1184  !A.checkForAllCallLikeInstructions(CheckForNoSync, *this))
1185  return indicatePessimisticFixpoint();
1186 
1187  return ChangeStatus::UNCHANGED;
1188 }
1189 
1190 struct AANoSyncFunction final : public AANoSyncImpl {
1192 
1193  /// See AbstractAttribute::trackStatistics()
1194  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) }
1195 };
1196 
1197 /// NoSync attribute deduction for a call sites.
1199 
1200 /// ------------------------ No-Free Attributes ----------------------------
1201 
1202 struct AANoFreeImpl : public AANoFree {
1203  AANoFreeImpl(const IRPosition &IRP) : AANoFree(IRP) {}
1204 
1205  /// See AbstractAttribute::initialize(...).
1206  void initialize(Attributor &A) override {
1207  if (hasAttr({Attribute::NoFree}))
1208  indicateOptimisticFixpoint();
1209  }
1210 
1211  /// See AbstractAttribute::updateImpl(...).
1213  auto CheckForNoFree = [&](Instruction &I) {
1214  ImmutableCallSite ICS(&I);
1215  if (ICS.hasFnAttr(Attribute::NoFree))
1216  return true;
1217 
1218  const auto &NoFreeAA =
1220  return NoFreeAA.isAssumedNoFree();
1221  };
1222 
1223  if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this))
1224  return indicatePessimisticFixpoint();
1225  return ChangeStatus::UNCHANGED;
1226  }
1227 
1228  /// See AbstractAttribute::getAsStr().
1229  const std::string getAsStr() const override {
1230  return getAssumed() ? "nofree" : "may-free";
1231  }
1232 };
1233 
1234 struct AANoFreeFunction final : public AANoFreeImpl {
1236 
1237  /// See AbstractAttribute::trackStatistics()
1238  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
1239 };
1240 
1241 /// NoFree attribute deduction for a call sites.
1243 
1244 /// ------------------------ NonNull Argument Attribute ------------------------
1246  AANonNullImpl(const IRPosition &IRP) : AANonNull(IRP) {}
1247 
1248  /// See AbstractAttribute::initialize(...).
1249  void initialize(Attributor &A) override {
1250  if (hasAttr({Attribute::NonNull, Attribute::Dereferenceable}))
1251  indicateOptimisticFixpoint();
1252  }
1253 
1254  /// See AbstractAttribute::getAsStr().
1255  const std::string getAsStr() const override {
1256  return getAssumed() ? "nonnull" : "may-null";
1257  }
1258 };
1259 
1260 /// NonNull attribute for a floating value.
1263 
1264  /// See AbstractAttribute::initialize(...).
1265  void initialize(Attributor &A) override {
1267 
1268  if (isAtFixpoint())
1269  return;
1270 
1271  const IRPosition &IRP = getIRPosition();
1272  const Value &V = IRP.getAssociatedValue();
1273  const DataLayout &DL = A.getDataLayout();
1274 
1275  // TODO: This context sensitive query should be removed once we can do
1276  // context sensitive queries in the genericValueTraversal below.
1277  if (isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, IRP.getCtxI(),
1278  /* TODO: DT */ nullptr))
1279  indicateOptimisticFixpoint();
1280  }
1281 
1282  /// See AbstractAttribute::updateImpl(...).
1284  const DataLayout &DL = A.getDataLayout();
1285 
1286  auto VisitValueCB = [&](Value &V, AAAlign::StateType &T,
1287  bool Stripped) -> bool {
1288  const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V));
1289  if (!Stripped && this == &AA) {
1290  if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr,
1291  /* TODO: CtxI */ nullptr,
1292  /* TODO: DT */ nullptr))
1294  } else {
1295  // Use abstract attribute information.
1296  const AANonNull::StateType &NS =
1297  static_cast<const AANonNull::StateType &>(AA.getState());
1298  T ^= NS;
1299  }
1300  return T.isValidState();
1301  };
1302 
1303  StateType T;
1304  if (!genericValueTraversal<AANonNull, StateType>(A, getIRPosition(), *this,
1305  T, VisitValueCB))
1306  return indicatePessimisticFixpoint();
1307 
1309  }
1310 
1311  /// See AbstractAttribute::trackStatistics()
1312  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
1313 };
1314 
1315 /// NonNull attribute for function return value.
1316 struct AANonNullReturned final
1317  : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl> {
1320 
1321  /// See AbstractAttribute::trackStatistics()
1322  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
1323 };
1324 
1325 /// NonNull attribute for function argument.
1326 struct AANonNullArgument final
1327  : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
1330 
1331  /// See AbstractAttribute::trackStatistics()
1332  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
1333 };
1334 
1337 
1338  /// See AbstractAttribute::trackStatistics()
1340 };
1341 
1342 /// NonNull attribute for a call site return position.
1344  : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl> {
1347 
1348  /// See AbstractAttribute::trackStatistics()
1349  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
1350 };
1351 
1352 /// ------------------------ No-Recurse Attributes ----------------------------
1353 
1354 struct AANoRecurseImpl : public AANoRecurse {
1356 
1357  /// See AbstractAttribute::initialize(...).
1358  void initialize(Attributor &A) override {
1359  if (hasAttr({getAttrKind()})) {
1360  indicateOptimisticFixpoint();
1361  return;
1362  }
1363  }
1364 
1365  /// See AbstractAttribute::getAsStr()
1366  const std::string getAsStr() const override {
1367  return getAssumed() ? "norecurse" : "may-recurse";
1368  }
1369 };
1370 
1373 
1374  /// See AbstractAttribute::updateImpl(...).
1376  // TODO: Implement this.
1377  return indicatePessimisticFixpoint();
1378  }
1379 
1380  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
1381 };
1382 
1384 
1385 /// ------------------------ Will-Return Attributes ----------------------------
1386 
1387 // Helper function that checks whether a function has any cycle.
1388 // TODO: Replace with more efficent code
1389 static bool containsCycle(Function &F) {
1391 
1392  // Traverse BB by dfs and check whether successor is already visited.
1393  for (BasicBlock *BB : depth_first(&F)) {
1394  Visited.insert(BB);
1395  for (auto *SuccBB : successors(BB)) {
1396  if (Visited.count(SuccBB))
1397  return true;
1398  }
1399  }
1400  return false;
1401 }
1402 
1403 // Helper function that checks the function have a loop which might become an
1404 // endless loop
1405 // FIXME: Any cycle is regarded as endless loop for now.
1406 // We have to allow some patterns.
1408  return !F || !F->hasExactDefinition() || containsCycle(*F);
1409 }
1410 
1413 
1414  /// See AbstractAttribute::initialize(...).
1415  void initialize(Attributor &A) override {
1416  if (hasAttr({Attribute::WillReturn})) {
1417  indicateOptimisticFixpoint();
1418  return;
1419  }
1420 
1421  Function *F = getAssociatedFunction();
1423  indicatePessimisticFixpoint();
1424  }
1425 
1426  /// See AbstractAttribute::updateImpl(...).
1428  auto CheckForWillReturn = [&](Instruction &I) {
1430  const auto &WillReturnAA = A.getAAFor<AAWillReturn>(*this, IPos);
1431  if (WillReturnAA.isKnownWillReturn())
1432  return true;
1433  if (!WillReturnAA.isAssumedWillReturn())
1434  return false;
1435  const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(*this, IPos);
1436  return NoRecurseAA.isAssumedNoRecurse();
1437  };
1438 
1439  if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this))
1440  return indicatePessimisticFixpoint();
1441 
1442  return ChangeStatus::UNCHANGED;
1443  }
1444 
1445  /// See AbstractAttribute::getAsStr()
1446  const std::string getAsStr() const override {
1447  return getAssumed() ? "willreturn" : "may-noreturn";
1448  }
1449 };
1450 
1453 
1454  /// See AbstractAttribute::trackStatistics()
1455  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
1456 };
1457 
1458 /// WillReturn attribute deduction for a call sites.
1460 
1461 /// ------------------------ NoAlias Argument Attribute ------------------------
1462 
1464  AANoAliasImpl(const IRPosition &IRP) : AANoAlias(IRP) {}
1465 
1466  /// See AbstractAttribute::initialize(...).
1467  void initialize(Attributor &A) override {
1468  if (hasAttr({Attribute::NoAlias}))
1469  indicateOptimisticFixpoint();
1470  }
1471 
1472  const std::string getAsStr() const override {
1473  return getAssumed() ? "noalias" : "may-alias";
1474  }
1475 };
1476 
1477 /// NoAlias attribute for a floating value.
1480 
1481  /// See AbstractAttribute::updateImpl(...).
1483  // TODO: Implement this.
1484  return indicatePessimisticFixpoint();
1485  }
1486 
1487  /// See AbstractAttribute::trackStatistics()
1488  void trackStatistics() const override {
1490  }
1491 };
1492 
1493 /// NoAlias attribute for an argument.
1496 
1497  /// See AbstractAttribute::updateImpl(...).
1499  // TODO: Implement this.
1500  return indicatePessimisticFixpoint();
1501  }
1502 
1503  /// See AbstractAttribute::trackStatistics()
1504  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
1505 };
1506 
1509 
1510  /// See AbstractAttribute::updateImpl(...).
1512  // TODO: Implement this.
1513  return indicatePessimisticFixpoint();
1514  }
1515 
1516  /// See AbstractAttribute::trackStatistics()
1517  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
1518 };
1519 
1520 /// NoAlias attribute for function return value.
1523 
1524  /// See AbstractAttribute::updateImpl(...).
1525  virtual ChangeStatus updateImpl(Attributor &A) override {
1526 
1527  auto CheckReturnValue = [&](Value &RV) -> bool {
1528  if (Constant *C = dyn_cast<Constant>(&RV))
1529  if (C->isNullValue() || isa<UndefValue>(C))
1530  return true;
1531 
1532  /// For now, we can only deduce noalias if we have call sites.
1533  /// FIXME: add more support.
1534  ImmutableCallSite ICS(&RV);
1535  if (!ICS)
1536  return false;
1537 
1538  const auto &NoAliasAA =
1540  if (!NoAliasAA.isAssumedNoAlias())
1541  return false;
1542 
1543  /// FIXME: We can improve capture check in two ways:
1544  /// 1. Use the AANoCapture facilities.
1545  /// 2. Use the location of return insts for escape queries.
1546  if (PointerMayBeCaptured(&RV, /* ReturnCaptures */ false,
1547  /* StoreCaptures */ true))
1548  return false;
1549 
1550  return true;
1551  };
1552 
1553  if (!A.checkForAllReturnedValues(CheckReturnValue, *this))
1554  return indicatePessimisticFixpoint();
1555 
1556  return ChangeStatus::UNCHANGED;
1557  }
1558 
1559  /// See AbstractAttribute::trackStatistics()
1560  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) }
1561 };
1562 
1563 /// NoAlias attribute deduction for a call site return value.
1565 
1566 /// -------------------AAIsDead Function Attribute-----------------------
1567 
1568 struct AAIsDeadImpl : public AAIsDead {
1569  AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {}
1570 
1571  void initialize(Attributor &A) override {
1572  const Function *F = getAssociatedFunction();
1573 
1574  if (F->hasInternalLinkage())
1575  return;
1576 
1577  if (!F || !F->hasExactDefinition()) {
1578  indicatePessimisticFixpoint();
1579  return;
1580  }
1581 
1582  exploreFromEntry(A, F);
1583  }
1584 
1586  ToBeExploredPaths.insert(&(F->getEntryBlock().front()));
1587  AssumedLiveBlocks.insert(&(F->getEntryBlock()));
1588 
1589  for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
1590  if (const Instruction *NextNoReturnI =
1591  findNextNoReturn(A, ToBeExploredPaths[i]))
1592  NoReturnCalls.insert(NextNoReturnI);
1593  }
1594 
1595  /// Find the next assumed noreturn instruction in the block of \p I starting
1596  /// from, thus including, \p I.
1597  ///
1598  /// The caller is responsible to monitor the ToBeExploredPaths set as new
1599  /// instructions discovered in other basic block will be placed in there.
1600  ///
1601  /// \returns The next assumed noreturn instructions in the block of \p I
1602  /// starting from, thus including, \p I.
1603  const Instruction *findNextNoReturn(Attributor &A, const Instruction *I);
1604 
1605  /// See AbstractAttribute::getAsStr().
1606  const std::string getAsStr() const override {
1607  return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
1608  std::to_string(getAssociatedFunction()->size()) + "][#NRI " +
1609  std::to_string(NoReturnCalls.size()) + "]";
1610  }
1611 
1612  /// See AbstractAttribute::manifest(...).
1614  assert(getState().isValidState() &&
1615  "Attempted to manifest an invalid state!");
1616 
1618  Function &F = *getAssociatedFunction();
1619 
1620  if (AssumedLiveBlocks.empty()) {
1622  return ChangeStatus::CHANGED;
1623  }
1624 
1625  // Flag to determine if we can change an invoke to a call assuming the
1626  // callee is nounwind. This is not possible if the personality of the
1627  // function allows to catch asynchronous exceptions.
1628  bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
1629 
1630  for (const Instruction *NRC : NoReturnCalls) {
1631  Instruction *I = const_cast<Instruction *>(NRC);
1632  BasicBlock *BB = I->getParent();
1633  Instruction *SplitPos = I->getNextNode();
1634 
1635  if (auto *II = dyn_cast<InvokeInst>(I)) {
1636  // If we keep the invoke the split position is at the beginning of the
1637  // normal desitination block (it invokes a noreturn function after all).
1638  BasicBlock *NormalDestBB = II->getNormalDest();
1639  SplitPos = &NormalDestBB->front();
1640 
1641  /// Invoke is replaced with a call and unreachable is placed after it if
1642  /// the callee is nounwind and noreturn. Otherwise, we keep the invoke
1643  /// and only place an unreachable in the normal successor.
1644  if (Invoke2CallAllowed) {
1645  if (II->getCalledFunction()) {
1646  const IRPosition &IPos = IRPosition::callsite_function(*II);
1647  const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos);
1648  if (AANoUnw.isAssumedNoUnwind()) {
1649  LLVM_DEBUG(dbgs()
1650  << "[AAIsDead] Replace invoke with call inst\n");
1651  // We do not need an invoke (II) but instead want a call followed
1652  // by an unreachable. However, we do not remove II as other
1653  // abstract attributes might have it cached as part of their
1654  // results. Given that we modify the CFG anyway, we simply keep II
1655  // around but in a new dead block. To avoid II being live through
1656  // a different edge we have to ensure the block we place it in is
1657  // only reached from the current block of II and then not reached
1658  // at all when we insert the unreachable.
1659  SplitBlockPredecessors(NormalDestBB, {BB}, ".i2c");
1661  CI->insertBefore(II);
1662  CI->takeName(II);
1663  II->replaceAllUsesWith(CI);
1664  SplitPos = CI->getNextNode();
1665  }
1666  }
1667  }
1668  }
1669 
1670  BB = SplitPos->getParent();
1671  SplitBlock(BB, SplitPos);
1672  changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1673  HasChanged = ChangeStatus::CHANGED;
1674  }
1675 
1676  return HasChanged;
1677  }
1678 
1679  /// See AbstractAttribute::updateImpl(...).
1680  ChangeStatus updateImpl(Attributor &A) override;
1681 
1682  /// See AAIsDead::isAssumedDead(BasicBlock *).
1683  bool isAssumedDead(const BasicBlock *BB) const override {
1684  assert(BB->getParent() == getAssociatedFunction() &&
1685  "BB must be in the same anchor scope function.");
1686 
1687  if (!getAssumed())
1688  return false;
1689  return !AssumedLiveBlocks.count(BB);
1690  }
1691 
1692  /// See AAIsDead::isKnownDead(BasicBlock *).
1693  bool isKnownDead(const BasicBlock *BB) const override {
1694  return getKnown() && isAssumedDead(BB);
1695  }
1696 
1697  /// See AAIsDead::isAssumed(Instruction *I).
1698  bool isAssumedDead(const Instruction *I) const override {
1699  assert(I->getParent()->getParent() == getAssociatedFunction() &&
1700  "Instruction must be in the same anchor scope function.");
1701 
1702  if (!getAssumed())
1703  return false;
1704 
1705  // If it is not in AssumedLiveBlocks then it for sure dead.
1706  // Otherwise, it can still be after noreturn call in a live block.
1707  if (!AssumedLiveBlocks.count(I->getParent()))
1708  return true;
1709 
1710  // If it is not after a noreturn call, than it is live.
1711  return isAfterNoReturn(I);
1712  }
1713 
1714  /// See AAIsDead::isKnownDead(Instruction *I).
1715  bool isKnownDead(const Instruction *I) const override {
1716  return getKnown() && isAssumedDead(I);
1717  }
1718 
1719  /// Check if instruction is after noreturn call, in other words, assumed dead.
1720  bool isAfterNoReturn(const Instruction *I) const;
1721 
1722  /// Determine if \p F might catch asynchronous exceptions.
1724  return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
1725  }
1726 
1727  /// Collection of to be explored paths.
1729 
1730  /// Collection of all assumed live BasicBlocks.
1732 
1733  /// Collection of calls with noreturn attribute, assumed or knwon.
1735 };
1736 
1737 struct AAIsDeadFunction final : public AAIsDeadImpl {
1739 
1740  /// See AbstractAttribute::trackStatistics()
1741  void trackStatistics() const override {
1742  STATS_DECL(DeadInternalFunction, Function,
1743  "Number of internal functions classified as dead (no live callsite)");
1744  BUILD_STAT_NAME(DeadInternalFunction, Function) +=
1745  (getAssociatedFunction()->hasInternalLinkage() &&
1746  AssumedLiveBlocks.empty())
1747  ? 1
1748  : 0;
1749  STATS_DECL(DeadBlocks, Function,
1750  "Number of basic blocks classified as dead");
1751  BUILD_STAT_NAME(DeadBlocks, Function) +=
1752  getAssociatedFunction()->size() - AssumedLiveBlocks.size();
1753  STATS_DECL(PartiallyDeadBlocks, Function,
1754  "Number of basic blocks classified as partially dead");
1755  BUILD_STAT_NAME(PartiallyDeadBlocks, Function) += NoReturnCalls.size();
1756  }
1757 };
1758 
1760  const Instruction *PrevI = I->getPrevNode();
1761  while (PrevI) {
1762  if (NoReturnCalls.count(PrevI))
1763  return true;
1764  PrevI = PrevI->getPrevNode();
1765  }
1766  return false;
1767 }
1768 
1770  const Instruction *I) {
1771  const BasicBlock *BB = I->getParent();
1772  const Function &F = *BB->getParent();
1773 
1774  // Flag to determine if we can change an invoke to a call assuming the callee
1775  // is nounwind. This is not possible if the personality of the function allows
1776  // to catch asynchronous exceptions.
1777  bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
1778 
1779  // TODO: We should have a function that determines if an "edge" is dead.
1780  // Edges could be from an instruction to the next or from a terminator
1781  // to the successor. For now, we need to special case the unwind block
1782  // of InvokeInst below.
1783 
1784  while (I) {
1785  ImmutableCallSite ICS(I);
1786 
1787  if (ICS) {
1788  const IRPosition &IPos = IRPosition::callsite_function(ICS);
1789  // Regarless of the no-return property of an invoke instruction we only
1790  // learn that the regular successor is not reachable through this
1791  // instruction but the unwind block might still be.
1792  if (auto *Invoke = dyn_cast<InvokeInst>(I)) {
1793  // Use nounwind to justify the unwind block is dead as well.
1794  const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos);
1795  if (!Invoke2CallAllowed || !AANoUnw.isAssumedNoUnwind()) {
1796  AssumedLiveBlocks.insert(Invoke->getUnwindDest());
1797  ToBeExploredPaths.insert(&Invoke->getUnwindDest()->front());
1798  }
1799  }
1800 
1801  const auto &NoReturnAA = A.getAAFor<AANoReturn>(*this, IPos);
1802  if (NoReturnAA.isAssumedNoReturn())
1803  return I;
1804  }
1805 
1806  I = I->getNextNode();
1807  }
1808 
1809  // get new paths (reachable blocks).
1810  for (const BasicBlock *SuccBB : successors(BB)) {
1811  AssumedLiveBlocks.insert(SuccBB);
1812  ToBeExploredPaths.insert(&SuccBB->front());
1813  }
1814 
1815  // No noreturn instruction found.
1816  return nullptr;
1817 }
1818 
1820  const Function *F = getAssociatedFunction();
1822 
1823  if (F->hasInternalLinkage() && AssumedLiveBlocks.empty()) {
1824  auto CallSiteCheck = [&](CallSite) { return false; };
1825 
1826  // All callsites of F are dead.
1827  if (A.checkForAllCallSites(CallSiteCheck, *this, true))
1828  return ChangeStatus::UNCHANGED;
1829 
1830  // There exists at least one live call site, so we explore the function.
1831  Status = ChangeStatus::CHANGED;
1832 
1833  exploreFromEntry(A, F);
1834  }
1835 
1836  // Temporary collection to iterate over existing noreturn instructions. This
1837  // will alow easier modification of NoReturnCalls collection
1838  SmallVector<const Instruction *, 8> NoReturnChanged;
1839 
1840  for (const Instruction *I : NoReturnCalls)
1841  NoReturnChanged.push_back(I);
1842 
1843  for (const Instruction *I : NoReturnChanged) {
1844  size_t Size = ToBeExploredPaths.size();
1845 
1846  const Instruction *NextNoReturnI = findNextNoReturn(A, I);
1847  if (NextNoReturnI != I) {
1848  Status = ChangeStatus::CHANGED;
1849  NoReturnCalls.remove(I);
1850  if (NextNoReturnI)
1851  NoReturnCalls.insert(NextNoReturnI);
1852  }
1853 
1854  // Explore new paths.
1855  while (Size != ToBeExploredPaths.size()) {
1856  Status = ChangeStatus::CHANGED;
1857  if (const Instruction *NextNoReturnI =
1858  findNextNoReturn(A, ToBeExploredPaths[Size++]))
1859  NoReturnCalls.insert(NextNoReturnI);
1860  }
1861  }
1862 
1863  LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: "
1864  << AssumedLiveBlocks.size() << " Total number of blocks: "
1865  << getAssociatedFunction()->size() << "\n");
1866 
1867  // If we know everything is live there is no need to query for liveness.
1868  if (NoReturnCalls.empty() &&
1869  getAssociatedFunction()->size() == AssumedLiveBlocks.size()) {
1870  // Indicating a pessimistic fixpoint will cause the state to be "invalid"
1871  // which will cause the Attributor to not return the AAIsDead on request,
1872  // which will prevent us from querying isAssumedDead().
1873  indicatePessimisticFixpoint();
1874  assert(!isValidState() && "Expected an invalid state!");
1875  }
1876 
1877  return Status;
1878 }
1879 
1880 /// Liveness information for a call sites.
1881 //
1882 // TODO: Once we have call site specific value information we can provide call
1883 // site specific liveness liveness information and then it makes sense to
1884 // specialize attributes for call sites instead of redirecting requests to
1885 // the callee.
1887 
1888 /// -------------------- Dereferenceable Argument Attribute --------------------
1889 
1891 
1892  /// State representing for dereferenceable bytes.
1894 
1895  /// State representing that whether the value is globaly dereferenceable.
1897 
1898  /// See AbstractState::isValidState()
1899  bool isValidState() const override { return DerefBytesState.isValidState(); }
1900 
1901  /// See AbstractState::isAtFixpoint()
1902  bool isAtFixpoint() const override {
1903  return !isValidState() ||
1904  (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
1905  }
1906 
1907  /// See AbstractState::indicateOptimisticFixpoint(...)
1909  DerefBytesState.indicateOptimisticFixpoint();
1910  GlobalState.indicateOptimisticFixpoint();
1911  return ChangeStatus::UNCHANGED;
1912  }
1913 
1914  /// See AbstractState::indicatePessimisticFixpoint(...)
1916  DerefBytesState.indicatePessimisticFixpoint();
1917  GlobalState.indicatePessimisticFixpoint();
1918  return ChangeStatus::CHANGED;
1919  }
1920 
1921  /// Update known dereferenceable bytes.
1922  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1923  DerefBytesState.takeKnownMaximum(Bytes);
1924  }
1925 
1926  /// Update assumed dereferenceable bytes.
1927  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1928  DerefBytesState.takeAssumedMinimum(Bytes);
1929  }
1930 
1931  /// Equality for DerefState.
1932  bool operator==(const DerefState &R) {
1933  return this->DerefBytesState == R.DerefBytesState &&
1934  this->GlobalState == R.GlobalState;
1935  }
1936 
1937  /// Inequality for IntegerState.
1938  bool operator!=(const DerefState &R) { return !(*this == R); }
1939 
1940  /// See IntegerState::operator^=
1942  DerefBytesState ^= R.DerefBytesState;
1943  GlobalState ^= R.GlobalState;
1944  return *this;
1945  }
1946 
1947  /// See IntegerState::operator&=
1949  DerefBytesState &= R.DerefBytesState;
1950  GlobalState &= R.GlobalState;
1951  return *this;
1952  }
1953 
1954  /// See IntegerState::operator|=
1956  DerefBytesState |= R.DerefBytesState;
1957  GlobalState |= R.GlobalState;
1958  return *this;
1959  }
1960 };
1961 
1962 template <>
1964  const DerefState &R) {
1966  S.DerefBytesState, R.DerefBytesState);
1967  ChangeStatus CS1 =
1968  clampStateAndIndicateChange<IntegerState>(S.GlobalState, R.GlobalState);
1969  return CS0 | CS1;
1970 }
1971 
1974  using StateType = DerefState;
1975 
1976  void initialize(Attributor &A) override {
1978  getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
1979  Attrs);
1980  for (const Attribute &Attr : Attrs)
1981  takeKnownDerefBytesMaximum(Attr.getValueAsInt());
1982 
1983  NonNullAA = &A.getAAFor<AANonNull>(*this, getIRPosition());
1984  }
1985 
1986  /// See AbstractAttribute::getState()
1987  /// {
1988  StateType &getState() override { return *this; }
1989  const StateType &getState() const override { return *this; }
1990  /// }
1991 
1992  /// See AADereferenceable::getAssumedDereferenceableBytes().
1994  return DerefBytesState.getAssumed();
1995  }
1996 
1997  /// See AADereferenceable::getKnownDereferenceableBytes().
1999  return DerefBytesState.getKnown();
2000  }
2001 
2002  /// See AADereferenceable::isAssumedGlobal().
2003  bool isAssumedGlobal() const override { return GlobalState.getAssumed(); }
2004 
2005  /// See AADereferenceable::isKnownGlobal().
2006  bool isKnownGlobal() const override { return GlobalState.getKnown(); }
2007 
2008  bool isAssumedNonNull() const override {
2009  return NonNullAA && NonNullAA->isAssumedNonNull();
2010  }
2011 
2013  SmallVectorImpl<Attribute> &Attrs) const override {
2014  // TODO: Add *_globally support
2015  if (isAssumedNonNull())
2017  Ctx, getAssumedDereferenceableBytes()));
2018  else
2020  Ctx, getAssumedDereferenceableBytes()));
2021  }
2022 
2023  /// See AbstractAttribute::getAsStr().
2024  const std::string getAsStr() const override {
2025  if (!getAssumedDereferenceableBytes())
2026  return "unknown-dereferenceable";
2027  return std::string("dereferenceable") +
2028  (isAssumedNonNull() ? "" : "_or_null") +
2029  (isAssumedGlobal() ? "_globally" : "") + "<" +
2030  std::to_string(getKnownDereferenceableBytes()) + "-" +
2031  std::to_string(getAssumedDereferenceableBytes()) + ">";
2032  }
2033 
2034 private:
2035  const AANonNull *NonNullAA = nullptr;
2036 };
2037 
2038 /// Dereferenceable attribute for a floating value.
2041  : AADereferenceableImpl(IRP) {}
2042 
2043  /// See AbstractAttribute::updateImpl(...).
2045  const DataLayout &DL = A.getDataLayout();
2046 
2047  auto VisitValueCB = [&](Value &V, DerefState &T, bool Stripped) -> bool {
2048  unsigned IdxWidth =
2050  APInt Offset(IdxWidth, 0);
2051  const Value *Base =
2053 
2054  const auto &AA =
2055  A.getAAFor<AADereferenceable>(*this, IRPosition::value(*Base));
2056  int64_t DerefBytes = 0;
2057  if (!Stripped && this == &AA) {
2058  // Use IR information if we did not strip anything.
2059  // TODO: track globally.
2060  bool CanBeNull;
2061  DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
2062  T.GlobalState.indicatePessimisticFixpoint();
2063  } else {
2064  const DerefState &DS = static_cast<const DerefState &>(AA.getState());
2065  DerefBytes = DS.DerefBytesState.getAssumed();
2066  T.GlobalState &= DS.GlobalState;
2067  }
2068 
2069  T.takeAssumedDerefBytesMinimum(
2070  std::max(int64_t(0), DerefBytes - Offset.getSExtValue()));
2071 
2072  if (!Stripped && this == &AA) {
2073  T.takeKnownDerefBytesMaximum(
2074  std::max(int64_t(0), DerefBytes - Offset.getSExtValue()));
2076  }
2077 
2078  return T.isValidState();
2079  };
2080 
2081  DerefState T;
2082  if (!genericValueTraversal<AADereferenceable, DerefState>(
2083  A, getIRPosition(), *this, T, VisitValueCB))
2084  return indicatePessimisticFixpoint();
2085 
2087  }
2088 
2089  /// See AbstractAttribute::trackStatistics()
2090  void trackStatistics() const override {
2091  STATS_DECLTRACK_FLOATING_ATTR(dereferenceable)
2092  }
2093 };
2094 
2095 /// Dereferenceable attribute for a return value.
2097  : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl,
2098  DerefState> {
2101  DerefState>(IRP) {}
2102 
2103  /// See AbstractAttribute::trackStatistics()
2104  void trackStatistics() const override {
2105  STATS_DECLTRACK_FNRET_ATTR(dereferenceable)
2106  }
2107 };
2108 
2109 /// Dereferenceable attribute for an argument
2111  : AAArgumentFromCallSiteArguments<AADereferenceable, AADereferenceableImpl,
2112  DerefState> {
2116  IRP) {}
2117 
2118  /// See AbstractAttribute::trackStatistics()
2119  void trackStatistics() const override{
2120  STATS_DECLTRACK_ARG_ATTR(dereferenceable)
2121  }
2122 };
2123 
2124 /// Dereferenceable attribute for a call site argument.
2127  : AADereferenceableFloating(IRP) {}
2128 
2129  /// See AbstractAttribute::trackStatistics()
2130  void trackStatistics() const override {
2131  STATS_DECLTRACK_CSARG_ATTR(dereferenceable)
2132  }
2133 };
2134 
2135 /// Dereferenceable attribute deduction for a call site return value.
2137 
2138 // ------------------------ Align Argument Attribute ------------------------
2139 
2141  AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {}
2142 
2143  // Max alignemnt value allowed in IR
2144  static const unsigned MAX_ALIGN = 1U << 29;
2145 
2146  /// See AbstractAttribute::initialize(...).
2147  void initialize(Attributor &A) override {
2148  takeAssumedMinimum(MAX_ALIGN);
2149 
2151  getAttrs({Attribute::Alignment}, Attrs);
2152  for (const Attribute &Attr : Attrs)
2153  takeKnownMaximum(Attr.getValueAsInt());
2154  }
2155 
2156  /// See AbstractAttribute::getDeducedAttributes
2157  virtual void
2159  SmallVectorImpl<Attribute> &Attrs) const override {
2160  if (getAssumedAlign() > 1)
2161  Attrs.emplace_back(Attribute::getWithAlignment(Ctx, getAssumedAlign()));
2162  }
2163 
2164  /// See AbstractAttribute::getAsStr().
2165  const std::string getAsStr() const override {
2166  return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) +
2167  "-" + std::to_string(getAssumedAlign()) + ">")
2168  : "unknown-align";
2169  }
2170 };
2171 
2172 /// Align attribute for a floating value.
2175 
2176  /// See AbstractAttribute::updateImpl(...).
2178  const DataLayout &DL = A.getDataLayout();
2179 
2180  auto VisitValueCB = [&](Value &V, AAAlign::StateType &T,
2181  bool Stripped) -> bool {
2182  const auto &AA = A.getAAFor<AAAlign>(*this, IRPosition::value(V));
2183  if (!Stripped && this == &AA) {
2184  // Use only IR information if we did not strip anything.
2187  } else {
2188  // Use abstract attribute information.
2189  const AAAlign::StateType &DS =
2190  static_cast<const AAAlign::StateType &>(AA.getState());
2191  T ^= DS;
2192  }
2193  return T.isValidState();
2194  };
2195 
2196  StateType T;
2197  if (!genericValueTraversal<AAAlign, StateType>(A, getIRPosition(), *this, T,
2198  VisitValueCB))
2199  return indicatePessimisticFixpoint();
2200 
2201  // TODO: If we know we visited all incoming values, thus no are assumed
2202  // dead, we can take the known information from the state T.
2204  }
2205 
2206  /// See AbstractAttribute::trackStatistics()
2207  void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(align) }
2208 };
2209 
2210 /// Align attribute for function return value.
2211 struct AAAlignReturned final
2212  : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> {
2215 
2216  /// See AbstractAttribute::trackStatistics()
2218 };
2219 
2220 /// Align attribute for function argument.
2221 struct AAAlignArgument final
2222  : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl> {
2225 
2226  /// See AbstractAttribute::trackStatistics()
2228 };
2229 
2232 
2233  /// See AbstractAttribute::trackStatistics()
2235 };
2236 
2237 /// Align attribute deduction for a call site return value.
2239 
2240 /// ------------------ Function No-Return Attribute ----------------------------
2241 struct AANoReturnImpl : public AANoReturn {
2242  AANoReturnImpl(const IRPosition &IRP) : AANoReturn(IRP) {}
2243 
2244  /// See AbstractAttribute::getAsStr().
2245  const std::string getAsStr() const override {
2246  return getAssumed() ? "noreturn" : "may-return";
2247  }
2248 
2249  /// See AbstractAttribute::initialize(...).
2250  void initialize(Attributor &A) override {
2251  if (hasAttr({getAttrKind()}))
2252  indicateOptimisticFixpoint();
2253  }
2254 
2255  /// See AbstractAttribute::updateImpl(Attributor &A).
2256  virtual ChangeStatus updateImpl(Attributor &A) override {
2257  auto CheckForNoReturn = [](Instruction &) { return false; };
2258  if (!A.checkForAllInstructions(CheckForNoReturn, *this,
2259  {(unsigned)Instruction::Ret}))
2260  return indicatePessimisticFixpoint();
2261  return ChangeStatus::UNCHANGED;
2262  }
2263 };
2264 
2267 
2268  /// See AbstractAttribute::trackStatistics()
2269  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(noreturn) }
2270 };
2271 
2272 /// NoReturn attribute deduction for a call sites.
2274 
2275 /// ----------------------------------------------------------------------------
2276 /// Attributor
2277 /// ----------------------------------------------------------------------------
2278 
2280  const AAIsDead *LivenessAA) {
2281  const Instruction *CtxI = AA.getIRPosition().getCtxI();
2282  if (!CtxI)
2283  return false;
2284 
2285  if (!LivenessAA)
2286  LivenessAA =
2287  &getAAFor<AAIsDead>(AA, IRPosition::function(*CtxI->getFunction()));
2288 
2289  // Don't check liveness for AAIsDead.
2290  if (&AA == LivenessAA)
2291  return false;
2292 
2293  if (!LivenessAA->isAssumedDead(CtxI))
2294  return false;
2295 
2296  // TODO: Do not track dependences automatically but add it here as only a
2297  // "is-assumed-dead" result causes a dependence.
2298  return true;
2299 }
2300 
2302  const AbstractAttribute &QueryingAA,
2303  bool RequireAllCallSites) {
2304  // We can try to determine information from
2305  // the call sites. However, this is only possible all call sites are known,
2306  // hence the function has internal linkage.
2307  const IRPosition &IRP = QueryingAA.getIRPosition();
2308  const Function *AssociatedFunction = IRP.getAssociatedFunction();
2309  if (!AssociatedFunction)
2310  return false;
2311 
2312  if (RequireAllCallSites && !AssociatedFunction->hasInternalLinkage()) {
2313  LLVM_DEBUG(
2314  dbgs()
2315  << "[Attributor] Function " << AssociatedFunction->getName()
2316  << " has no internal linkage, hence not all call sites are known\n");
2317  return false;
2318  }
2319 
2320  for (const Use &U : AssociatedFunction->uses()) {
2321  Instruction *I = cast<Instruction>(U.getUser());
2322  Function *Caller = I->getFunction();
2323 
2324  const auto &LivenessAA =
2325  getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*Caller));
2326 
2327  // Skip dead calls.
2328  if (LivenessAA.isAssumedDead(I))
2329  continue;
2330 
2331  CallSite CS(U.getUser());
2332  if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
2333  if (!RequireAllCallSites)
2334  continue;
2335 
2336  LLVM_DEBUG(dbgs() << "[Attributor] User " << *U.getUser()
2337  << " is an invalid use of "
2338  << AssociatedFunction->getName() << "\n");
2339  return false;
2340  }
2341 
2342  if (Pred(CS))
2343  continue;
2344 
2345  LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for "
2346  << *CS.getInstruction() << "\n");
2347  return false;
2348  }
2349 
2350  return true;
2351 }
2352 
2354  const function_ref<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)>
2355  &Pred,
2356  const AbstractAttribute &QueryingAA) {
2357 
2358  const IRPosition &IRP = QueryingAA.getIRPosition();
2359  // Since we need to provide return instructions we have to have an exact
2360  // definition.
2361  const Function *AssociatedFunction = IRP.getAssociatedFunction();
2362  if (!AssociatedFunction || !AssociatedFunction->hasExactDefinition())
2363  return false;
2364 
2365  // If this is a call site query we use the call site specific return values
2366  // and liveness information.
2367  const IRPosition &QueryIRP = IRPosition::function_scope(IRP);
2368  const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP);
2369  if (!AARetVal.getState().isValidState())
2370  return false;
2371 
2372  return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred);
2373 }
2374 
2376  const function_ref<bool(Value &)> &Pred,
2377  const AbstractAttribute &QueryingAA) {
2378 
2379  const IRPosition &IRP = QueryingAA.getIRPosition();
2380  const Function *AssociatedFunction = IRP.getAssociatedFunction();
2381  if (!AssociatedFunction || !AssociatedFunction->hasExactDefinition())
2382  return false;
2383 
2384  const IRPosition &QueryIRP = IRPosition::function_scope(IRP);
2385  const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP);
2386  if (!AARetVal.getState().isValidState())
2387  return false;
2388 
2389  return AARetVal.checkForAllReturnedValuesAndReturnInsts(
2390  [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &) {
2391  return Pred(RV);
2392  });
2393 }
2394 
2396  const llvm::function_ref<bool(Instruction &)> &Pred,
2397  const AbstractAttribute &QueryingAA, const ArrayRef<unsigned> &Opcodes) {
2398 
2399  const IRPosition &IRP = QueryingAA.getIRPosition();
2400  // Since we need to provide instructions we have to have an exact definition.
2401  const Function *AssociatedFunction = IRP.getAssociatedFunction();
2402  if (!AssociatedFunction || !AssociatedFunction->hasExactDefinition())
2403  return false;
2404 
2405  const IRPosition &QueryIRP = IRPosition::function_scope(IRP);
2406  const auto &LivenessAA = getAAFor<AAIsDead>(QueryingAA, QueryIRP);
2407 
2408  auto &OpcodeInstMap =
2409  InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
2410  for (unsigned Opcode : Opcodes) {
2411  for (Instruction *I : OpcodeInstMap[Opcode]) {
2412  // Skip dead instructions.
2413  if (LivenessAA.isAssumedDead(I))
2414  continue;
2415 
2416  if (!Pred(*I))
2417  return false;
2418  }
2419  }
2420 
2421  return true;
2422 }
2423 
2425  const llvm::function_ref<bool(Instruction &)> &Pred,
2426  AbstractAttribute &QueryingAA) {
2427 
2428  const Function *AssociatedFunction =
2429  QueryingAA.getIRPosition().getAssociatedFunction();
2430  if (!AssociatedFunction)
2431  return false;
2432 
2433  const auto &LivenessAA =
2434  getAAFor<AAIsDead>(QueryingAA, QueryingAA.getIRPosition());
2435 
2436  for (Instruction *I :
2437  InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) {
2438  // Skip dead instructions.
2439  if (LivenessAA.isAssumedDead(I))
2440  continue;
2441 
2442  if (!Pred(*I))
2443  return false;
2444  }
2445 
2446  return true;
2447 }
2448 
2450  // Initialize all abstract attributes, allow new ones to be created.
2451  for (unsigned u = 0; u < AllAbstractAttributes.size(); u++)
2452  AllAbstractAttributes[u]->initialize(*this);
2453 
2454  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
2455  << AllAbstractAttributes.size()
2456  << " abstract attributes.\n");
2457 
2458  // Now that all abstract attributes are collected and initialized we start
2459  // the abstract analysis.
2460 
2461  unsigned IterationCounter = 1;
2462 
2465  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
2466 
2467  do {
2468  // Remember the size to determine new attributes.
2469  size_t NumAAs = AllAbstractAttributes.size();
2470  LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
2471  << ", Worklist size: " << Worklist.size() << "\n");
2472 
2473  // Add all abstract attributes that are potentially dependent on one that
2474  // changed to the work list.
2475  for (AbstractAttribute *ChangedAA : ChangedAAs) {
2476  auto &QuerriedAAs = QueryMap[ChangedAA];
2477  Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
2478  }
2479 
2480  // Reset the changed set.
2481  ChangedAAs.clear();
2482 
2483  // Update all abstract attribute in the work list and record the ones that
2484  // changed.
2485  for (AbstractAttribute *AA : Worklist)
2486  if (!isAssumedDead(*AA, nullptr))
2487  if (AA->update(*this) == ChangeStatus::CHANGED)
2488  ChangedAAs.push_back(AA);
2489 
2490  // Reset the work list and repopulate with the changed abstract attributes.
2491  // Note that dependent ones are added above.
2492  Worklist.clear();
2493  Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
2494 
2495  // Add attributes to the worklist that have been created in the last
2496  // iteration.
2497  Worklist.insert(AllAbstractAttributes.begin() + NumAAs,
2498  AllAbstractAttributes.end());
2499 
2500  } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
2501 
2502  size_t NumFinalAAs = AllAbstractAttributes.size();
2503 
2504  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
2505  << IterationCounter << "/" << MaxFixpointIterations
2506  << " iterations\n");
2507 
2508  bool FinishedAtFixpoint = Worklist.empty();
2509 
2510  // Reset abstract arguments not settled in a sound fixpoint by now. This
2511  // happens when we stopped the fixpoint iteration early. Note that only the
2512  // ones marked as "changed" *and* the ones transitively depending on them
2513  // need to be reverted to a pessimistic state. Others might not be in a
2514  // fixpoint state but we can use the optimistic results for them anyway.
2516  for (unsigned u = 0; u < ChangedAAs.size(); u++) {
2517  AbstractAttribute *ChangedAA = ChangedAAs[u];
2518  if (!Visited.insert(ChangedAA).second)
2519  continue;
2520 
2521  AbstractState &State = ChangedAA->getState();
2522  if (!State.isAtFixpoint()) {
2524 
2525  NumAttributesTimedOut++;
2526  }
2527 
2528  auto &QuerriedAAs = QueryMap[ChangedAA];
2529  ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
2530  }
2531 
2532  LLVM_DEBUG({
2533  if (!Visited.empty())
2534  dbgs() << "\n[Attributor] Finalized " << Visited.size()
2535  << " abstract attributes.\n";
2536  });
2537 
2538  unsigned NumManifested = 0;
2539  unsigned NumAtFixpoint = 0;
2540  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
2541  for (AbstractAttribute *AA : AllAbstractAttributes) {
2542  AbstractState &State = AA->getState();
2543 
2544  // If there is not already a fixpoint reached, we can now take the
2545  // optimistic state. This is correct because we enforced a pessimistic one
2546  // on abstract attributes that were transitively dependent on a changed one
2547  // already above.
2548  if (!State.isAtFixpoint())
2550 
2551  // If the state is invalid, we do not try to manifest it.
2552  if (!State.isValidState())
2553  continue;
2554 
2555  // Skip dead code.
2556  if (isAssumedDead(*AA, nullptr))
2557  continue;
2558  // Manifest the state and record if we changed the IR.
2559  ChangeStatus LocalChange = AA->manifest(*this);
2560  if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
2561  AA->trackStatistics();
2562 
2563  ManifestChange = ManifestChange | LocalChange;
2564 
2565  NumAtFixpoint++;
2566  NumManifested += (LocalChange == ChangeStatus::CHANGED);
2567  }
2568 
2569  (void)NumManifested;
2570  (void)NumAtFixpoint;
2571  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
2572  << " arguments while " << NumAtFixpoint
2573  << " were in a valid fixpoint state\n");
2574 
2575  // If verification is requested, we finished this run at a fixpoint, and the
2576  // IR was changed, we re-run the whole fixpoint analysis, starting at
2577  // re-initialization of the arguments. This re-run should not result in an IR
2578  // change. Though, the (virtual) state of attributes at the end of the re-run
2579  // might be more optimistic than the known state or the IR state if the better
2580  // state cannot be manifested.
2581  if (VerifyAttributor && FinishedAtFixpoint &&
2582  ManifestChange == ChangeStatus::CHANGED) {
2583  VerifyAttributor = false;
2584  ChangeStatus VerifyStatus = run();
2585  if (VerifyStatus != ChangeStatus::UNCHANGED)
2587  "Attributor verification failed, re-run did result in an IR change "
2588  "even after a fixpoint was reached in the original run. (False "
2589  "positives possible!)");
2590  VerifyAttributor = true;
2591  }
2592 
2593  NumAttributesManifested += NumManifested;
2594  NumAttributesValidFixpoint += NumAtFixpoint;
2595 
2596  (void)NumFinalAAs;
2597  assert(
2598  NumFinalAAs == AllAbstractAttributes.size() &&
2599  "Expected the final number of abstract attributes to remain unchanged!");
2600  return ManifestChange;
2601 }
2602 
2603 /// Helper function that checks if an abstract attribute of type \p AAType
2604 /// should be created for IR position \p IRP and if so creates and registers it
2605 /// with the Attributor \p A.
2606 ///
2607 /// This method will look at the provided whitelist. If one is given and the
2608 /// kind \p AAType::ID is not contained, no abstract attribute is created.
2609 ///
2610 /// \returns The created abstract argument, or nullptr if none was created.
2611 template <typename AAType>
2612 static const AAType *checkAndRegisterAA(const IRPosition &IRP, Attributor &A,
2613  DenseSet<const char *> *Whitelist) {
2614  if (Whitelist && !Whitelist->count(&AAType::ID))
2615  return nullptr;
2616 
2617  return &A.registerAA<AAType>(*new AAType(IRP));
2618 }
2619 
2621  Function &F, DenseSet<const char *> *Whitelist) {
2622 
2623  IRPosition FPos = IRPosition::function(F);
2624 
2625  // Check for dead BasicBlocks in every function.
2626  // We need dead instruction detection because we do not want to deal with
2627  // broken IR in which SSA rules do not apply.
2628  checkAndRegisterAA<AAIsDeadFunction>(FPos, *this, /* Whitelist */ nullptr);
2629 
2630  // Every function might be "will-return".
2631  checkAndRegisterAA<AAWillReturnFunction>(FPos, *this, Whitelist);
2632 
2633  // Every function can be nounwind.
2634  checkAndRegisterAA<AANoUnwindFunction>(FPos, *this, Whitelist);
2635 
2636  // Every function might be marked "nosync"
2637  checkAndRegisterAA<AANoSyncFunction>(FPos, *this, Whitelist);
2638 
2639  // Every function might be "no-free".
2640  checkAndRegisterAA<AANoFreeFunction>(FPos, *this, Whitelist);
2641 
2642  // Every function might be "no-return".
2643  checkAndRegisterAA<AANoReturnFunction>(FPos, *this, Whitelist);
2644 
2645  // Return attributes are only appropriate if the return type is non void.
2646  Type *ReturnType = F.getReturnType();
2647  if (!ReturnType->isVoidTy()) {
2648  // Argument attribute "returned" --- Create only one per function even
2649  // though it is an argument attribute.
2650  checkAndRegisterAA<AAReturnedValuesFunction>(FPos, *this, Whitelist);
2651 
2652  if (ReturnType->isPointerTy()) {
2653  IRPosition RetPos = IRPosition::returned(F);
2654 
2655  // Every function with pointer return type might be marked align.
2656  checkAndRegisterAA<AAAlignReturned>(RetPos, *this, Whitelist);
2657 
2658  // Every function with pointer return type might be marked nonnull.
2659  checkAndRegisterAA<AANonNullReturned>(RetPos, *this, Whitelist);
2660 
2661  // Every function with pointer return type might be marked noalias.
2662  checkAndRegisterAA<AANoAliasReturned>(RetPos, *this, Whitelist);
2663 
2664  // Every function with pointer return type might be marked
2665  // dereferenceable.
2666  checkAndRegisterAA<AADereferenceableReturned>(RetPos, *this, Whitelist);
2667  }
2668  }
2669 
2670  for (Argument &Arg : F.args()) {
2671  if (Arg.getType()->isPointerTy()) {
2673  // Every argument with pointer type might be marked nonnull.
2674  checkAndRegisterAA<AANonNullArgument>(ArgPos, *this, Whitelist);
2675 
2676  // Every argument with pointer type might be marked dereferenceable.
2677  checkAndRegisterAA<AADereferenceableArgument>(ArgPos, *this, Whitelist);
2678 
2679  // Every argument with pointer type might be marked align.
2680  checkAndRegisterAA<AAAlignArgument>(ArgPos, *this, Whitelist);
2681  }
2682  }
2683 
2684  // Walk all instructions to find more attribute opportunities and also
2685  // interesting instructions that might be queried by abstract attributes
2686  // during their initialization or update.
2687  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
2688  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
2689 
2690  for (Instruction &I : instructions(&F)) {
2691  bool IsInterestingOpcode = false;
2692 
2693  // To allow easy access to all instructions in a function with a given
2694  // opcode we store them in the InfoCache. As not all opcodes are interesting
2695  // to concrete attributes we only cache the ones that are as identified in
2696  // the following switch.
2697  // Note: There are no concrete attributes now so this is initially empty.
2698  switch (I.getOpcode()) {
2699  default:
2700  assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
2701  "New call site/base instruction type needs to be known int the "
2702  "attributor.");
2703  break;
2704  case Instruction::Call:
2705  case Instruction::CallBr:
2706  case Instruction::Invoke:
2707  case Instruction::CleanupRet:
2708  case Instruction::CatchSwitch:
2709  case Instruction::Resume:
2710  case Instruction::Ret:
2711  IsInterestingOpcode = true;
2712  }
2713  if (IsInterestingOpcode)
2714  InstOpcodeMap[I.getOpcode()].push_back(&I);
2715  if (I.mayReadOrWriteMemory())
2716  ReadOrWriteInsts.push_back(&I);
2717 
2718  CallSite CS(&I);
2719  if (CS && CS.getCalledFunction()) {
2720  for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
2721  if (!CS.getArgument(i)->getType()->isPointerTy())
2722  continue;
2723  IRPosition CSArgPos = IRPosition::callsite_argument(CS, i);
2724 
2725  // Call site argument attribute "non-null".
2726  checkAndRegisterAA<AANonNullCallSiteArgument>(CSArgPos, *this,
2727  Whitelist);
2728 
2729  // Call site argument attribute "dereferenceable".
2730  checkAndRegisterAA<AADereferenceableCallSiteArgument>(CSArgPos, *this,
2731  Whitelist);
2732 
2733  // Call site argument attribute "align".
2734  checkAndRegisterAA<AAAlignCallSiteArgument>(CSArgPos, *this, Whitelist);
2735  }
2736  }
2737  }
2738 }
2739 
2740 /// Helpers to ease debugging through output streams and print calls.
2741 ///
2742 ///{
2744  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2745 }
2746 
2748  switch (AP) {
2750  return OS << "inv";
2751  case IRPosition::IRP_FLOAT:
2752  return OS << "flt";
2754  return OS << "fn_ret";
2756  return OS << "cs_ret";
2758  return OS << "fn";
2760  return OS << "cs";
2762  return OS << "arg";
2764  return OS << "cs_arg";
2765  }
2766  llvm_unreachable("Unknown attribute position!");
2767 }
2768 
2770  const Value &AV = Pos.getAssociatedValue();
2771  return OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
2772  << Pos.getAnchorValue().getName() << "@" << Pos.getArgNo() << "]}";
2773 }
2774 
2776  return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")"
2777  << static_cast<const AbstractState &>(S);
2778 }
2779 
2781  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2782 }
2783 
2785  AA.print(OS);
2786  return OS;
2787 }
2788 
2790  OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState()
2791  << "]";
2792 }
2793 ///}
2794 
2795 /// ----------------------------------------------------------------------------
2796 /// Pass (Manager) Boilerplate
2797 /// ----------------------------------------------------------------------------
2798 
2800  if (DisableAttributor)
2801  return false;
2802 
2803  LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
2804  << " functions.\n");
2805 
2806  // Create an Attributor and initially empty information cache that is filled
2807  // while we identify default attribute opportunities.
2808  InformationCache InfoCache(M.getDataLayout());
2809  Attributor A(InfoCache);
2810 
2811  for (Function &F : M) {
2812  // TODO: Not all attributes require an exact definition. Find a way to
2813  // enable deduction for some but not all attributes in case the
2814  // definition might be changed at runtime, see also
2815  // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
2816  // TODO: We could always determine abstract attributes and if sufficient
2817  // information was found we could duplicate the functions that do not
2818  // have an exact definition.
2819  if (!F.hasExactDefinition()) {
2820  NumFnWithoutExactDefinition++;
2821  continue;
2822  }
2823 
2824  // For now we ignore naked and optnone functions.
2825  if (F.hasFnAttribute(Attribute::Naked) ||
2826  F.hasFnAttribute(Attribute::OptimizeNone))
2827  continue;
2828 
2829  NumFnWithExactDefinition++;
2830 
2831  // Populate the Attributor with abstract attribute opportunities in the
2832  // function and the information cache with IR information.
2833  A.identifyDefaultAbstractAttributes(F);
2834  }
2835 
2836  return A.run() == ChangeStatus::CHANGED;
2837 }
2838 
2840  if (runAttributorOnModule(M)) {
2841  // FIXME: Think about passes we will preserve and add them here.
2842  return PreservedAnalyses::none();
2843  }
2844  return PreservedAnalyses::all();
2845 }
2846 
2847 namespace {
2848 
2849 struct AttributorLegacyPass : public ModulePass {
2850  static char ID;
2851 
2852  AttributorLegacyPass() : ModulePass(ID) {
2854  }
2855 
2856  bool runOnModule(Module &M) override {
2857  if (skipModule(M))
2858  return false;
2859  return runAttributorOnModule(M);
2860  }
2861 
2862  void getAnalysisUsage(AnalysisUsage &AU) const override {
2863  // FIXME: Think about passes we will preserve and add them here.
2864  AU.setPreservesCFG();
2865  }
2866 };
2867 
2868 } // end anonymous namespace
2869 
2870 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
2871 
2872 char AttributorLegacyPass::ID = 0;
2873 
2874 const char AAReturnedValues::ID = 0;
2875 const char AANoUnwind::ID = 0;
2876 const char AANoSync::ID = 0;
2877 const char AANoFree::ID = 0;
2878 const char AANonNull::ID = 0;
2879 const char AANoRecurse::ID = 0;
2880 const char AAWillReturn::ID = 0;
2881 const char AANoAlias::ID = 0;
2882 const char AANoReturn::ID = 0;
2883 const char AAIsDead::ID = 0;
2884 const char AADereferenceable::ID = 0;
2885 const char AAAlign::ID = 0;
2886 
2887 // Macro magic to create the static generator function for attributes that
2888 // follow the naming scheme.
2889 
2890 #define SWITCH_PK_INV(CLASS, PK, POS_NAME) \
2891  case IRPosition::PK: \
2892  llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
2893 
2894 #define SWITCH_PK_CREATE(CLASS, IRP, PK, SUFFIX) \
2895  case IRPosition::PK: \
2896  AA = new CLASS##SUFFIX(IRP); \
2897  break;
2898 
2899 #define CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \
2900  CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \
2901  CLASS *AA = nullptr; \
2902  switch (IRP.getPositionKind()) { \
2903  SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \
2904  SWITCH_PK_INV(CLASS, IRP_FLOAT, "floating") \
2905  SWITCH_PK_INV(CLASS, IRP_ARGUMENT, "argument") \
2906  SWITCH_PK_INV(CLASS, IRP_RETURNED, "returned") \
2907  SWITCH_PK_INV(CLASS, IRP_CALL_SITE_RETURNED, "call site returned") \
2908  SWITCH_PK_INV(CLASS, IRP_CALL_SITE_ARGUMENT, "call site argument") \
2909  SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function) \
2910  SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite) \
2911  } \
2912  AA->initialize(A); \
2913  return *AA; \
2914  }
2915 
2916 #define CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \
2917  CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \
2918  CLASS *AA = nullptr; \
2919  switch (IRP.getPositionKind()) { \
2920  SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \
2921  SWITCH_PK_INV(CLASS, IRP_FUNCTION, "function") \
2922  SWITCH_PK_INV(CLASS, IRP_CALL_SITE, "call site") \
2923  SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating) \
2924  SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument) \
2925  SWITCH_PK_CREATE(CLASS, IRP, IRP_RETURNED, Returned) \
2926  SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned) \
2927  SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument) \
2928  } \
2929  AA->initialize(A); \
2930  return *AA; \
2931  }
2932 
2941 
2946 
2947 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION
2948 #undef CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION
2949 #undef SWITCH_PK_CREATE
2950 #undef SWITCH_PK_INV
2951 
2952 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
2953  "Deduce and propagate attributes", false, false)
2954 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
2955  "Deduce and propagate attributes", false, false)
An attribute for a call site return value.
Definition: Attributor.h:145
ChangeStatus clampStateAndIndicateChange< IntegerState >(IntegerState &S, const IntegerState &R)
Definition: Attributor.cpp:467
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Definition: Attributor.h:821
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
OpcodeInstMapTy & getOpcodeInstMapForFunction(const Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F...
Definition: Attributor.h:508
uint64_t CallInst * C
AAIsDeadImpl(const IRPosition &IRP)
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Return a value (possibly void), from a function.
StateType & getState() override
See AbstractAttribute::getState() {.
void initialize(Attributor &A) override
Initialize the state with the information in the Attributor A.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
iterator_range< use_iterator > uses()
Definition: Value.h:374
StringRef getKindAsString() const
Return the attribute&#39;s kind as a string.
Definition: Attributes.cpp:216
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:399
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old)
Return true if New is equal or worse than Old.
Definition: Attributor.cpp:219
Helper class for generic deduction: return value -> returned position.
Definition: Attributor.cpp:527
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
AANoRecurseImpl(const IRPosition &IRP)
---------------— Function No-Return Attribute -------------------------—
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
Align attribute for a floating value.
static bool isNoSyncIntrinsic(Instruction *I)
Helper function uset to check if intrinsic is volatile (memcpy, memmove, memset). ...
static ChangeStatus manifestAttrs(Attributor &A, IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs)
Definition: Attributor.cpp:277
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
BooleanState GlobalState
State representing that whether the value is globaly dereferenceable.
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.
SubsumingPositionIterator(const IRPosition &IRP)
Definition: Attributor.cpp:337
---------------------— No-Free Attributes -------------------------—
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
bool isValidState() const override
See AbstractState::isValidState()
AANonNullImpl(const IRPosition &IRP)
static Attribute getWithAlignment(LLVMContext &Context, uint64_t Align)
Return a uniquified Attribute object that has the specific alignment set.
Definition: Attributes.cpp:145
NonNull attribute for a call site return position.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static Attribute getWithDereferenceableBytes(LLVMContext &Context, uint64_t Bytes)
Definition: Attributes.cpp:158
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.
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:142
AANoAliasFloating(const IRPosition &IRP)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
Dereferenceable attribute for an argument.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1285
This class represents a function call, abstracting a target machine&#39;s calling convention.
Abstract Attribute Classes
Definition: Attributor.h:1119
AAAlignCallSiteArgument(const IRPosition &IRP)
AANoRecurseFunction(const IRPosition &IRP)
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:116
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
base_t getAssumed() const
Return the assumed state encoding.
Definition: Attributor.h:836
AANoSyncImpl(const IRPosition &IRP)
An attribute for a call site argument.
Definition: Attributor.h:149
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:745
virtual const IRPosition & getIRPosition() const =0
Return an IR position, see struct IRPosition.
IntegerState & takeAssumedMinimum(base_t Value)
Take minimum of assumed and Value.
Definition: Attributor.h:871
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
bool isAssumedNoRecurse() const
Return true if "norecurse" is assumed.
Definition: Attributor.h:1219
An abstract attribute for willreturn.
Definition: Attributor.h:1232
STATISTIC(NumFunctions, "Total number of functions")
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1985
Value & getAssociatedValue()
}
Definition: Attributor.h:313
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool isValidState() const override
See AbstractState::isValidState() NOTE: For now we simply pretend that the worst possible state is in...
Definition: Attributor.h:815
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:580
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
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:624
Kind
The positions we distinguish in the IR.
Definition: Attributor.h:140
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
NoAlias attribute for function return value.
NoAlias attribute for an argument.
virtual ChangeStatus indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
const std::string getAsStr() const override
See AbstractAttribute::getAsStr()
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
Instruction * getCtxI()
}
Definition: Attributor.h:293
AANonNullArgument(const IRPosition &IRP)
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
unsigned getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
Definition: Value.cpp:678
AANonNullFloating(const IRPosition &IRP)
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.cpp:628
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
AANoReturnFunction(const IRPosition &IRP)
static bool runAttributorOnModule(Module &M)
}
const std::string getAsStr() const override
See AbstractAttribute::getAsStr()
void takeKnownDerefBytesMaximum(uint64_t Bytes)
Update known dereferenceable bytes.
static const IRPosition function_scope(const IRPosition &IRP)
Create a position with function scope matching the "context" of IRP.
Definition: Attributor.h:218
---------------------— No-Recurse Attributes -------------------------—
Align attribute for function return value.
bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA)
Return true if AA (or its context instruction) is assumed dead.
bool isAssumedDead(const BasicBlock *BB) const override
See AAIsDead::isAssumedDead(BasicBlock *).
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
An AbstractAttribute for noreturn.
Definition: Attributor.h:1289
uint64_t getValueAsInt() const
Return the attribute&#39;s value as an integer.
Definition: Attributes.cpp:209
A visitor class for IR positions.
Definition: Attributor.h:478
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:194
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1398
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
An abstract attribute for norecurse.
Definition: Attributor.h:1213
static Attribute getWithDereferenceableOrNullBytes(LLVMContext &Context, uint64_t Bytes)
Definition: Attributes.cpp:164
#define STATS_DECLTRACK_ARG_ATTR(NAME)
Definition: Attributor.cpp:80
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
This file contains the simple types necessary to represent the attributes associated with functions a...
bool isAssumedNoUnwind() const
Returns true if nounwind is assumed.
Definition: Attributor.h:1163
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
#define STATS_DECLTRACK_CSARG_ATTR(NAME)
Definition: Attributor.cpp:82
bool canSimplifyInvokeNoUnwind(const Function *F)
llvm::iterator_range< iterator > returned_values() override
Definition: Attributor.cpp:739
static cl::opt< unsigned > MaxFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32))
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1228
AAReturnedValuesImpl(const IRPosition &IRP)
}
Definition: Attributor.cpp:696
SmallSetVector< const Instruction *, 8 > ToBeExploredPaths
Collection of to be explored paths.
An abstract interface for all noalias attributes.
Definition: Attributor.h:1251
bool checkForAllReadWriteInstructions(const llvm::function_ref< bool(Instruction &)> &Pred, AbstractAttribute &QueryingAA)
Check Pred on all Read/Write instructions.
AAAlignFloating(const IRPosition &IRP)
AtomicOrdering
Atomic ordering for LLVM&#39;s memory model.
uint32_t getKnownDereferenceableBytes() const override
See AADereferenceable::getKnownDereferenceableBytes().
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
AttributeList getAttributes(LLVMContext &C, ID id)
Return the attributes for an intrinsic.
An attribute for the function return value.
Definition: Attributor.h:144
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
Definition: Attributor.h:827
----------------—AAIsDead Function Attribute--------------------—
NoAlias attribute for a floating value.
attributor
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1581
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
int getArgNo() const
}
Definition: Attributor.h:328
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
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:1308
AAAlignReturned(const IRPosition &IRP)
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
Definition: Attributor.cpp:699
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
AAArgumentFromCallSiteArguments(const IRPosition &IRP)
Definition: Attributor.cpp:585
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
bool isAssumedNoFree() const
Return true if "nofree" is assumed.
Definition: Attributor.h:1276
void initializeAttributorLegacyPassPass(PassRegistry &)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool isKnownDead(const Instruction *I) const override
See AAIsDead::isKnownDead(Instruction *I).
void initialize(Attributor &A) override
Initialize the state with the information in the Attributor A.
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:223
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
Definition: Value.h:602
const AAType & getAAFor(const AbstractAttribute &QueryingAA, const IRPosition &IRP)
Lookup an abstract attribute of type AAType at position IRP.
Definition: Attributor.h:595
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:732
AANoSyncFunction(const IRPosition &IRP)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
An abstract interface for all nonnull attributes.
Definition: Attributor.h:1194
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
bool isKnownGlobal() const override
See AADereferenceable::isKnownGlobal().
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.h:959
AANoAliasArgument(const IRPosition &IRP)
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:261
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
IntegerState & takeKnownMaximum(base_t Value)
Take maximum of known and Value.
Definition: Attributor.h:878
unsigned getAttrIdx() const
Return the index in the attribute list for this position.
Definition: Attributor.h:331
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...
AAAlignImpl(const IRPosition &IRP)
---------------------— NoSync Function Attribute ----------------------—
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
Optional< Value * > getAssumedUniqueReturnValue(Attributor &A) const
Return an assumed unique return value if a single candidate is found.
Definition: Attributor.cpp:823
bool isValidState() const override
See AbstractState::isValidState().
Definition: Attributor.cpp:773
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1266
#define BUILD_STAT_NAME(NAME, TYPE)
Definition: Attributor.cpp:72
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
AbstractState StateType
Definition: Attributor.h:1026
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:168
base_t getKnown() const
Return the known state encoding.
Definition: Attributor.h:833
AADereferenceableReturned(const IRPosition &IRP)
#define STATS_DECLTRACK_FN_ATTR(NAME)
Definition: Attributor.cpp:85
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
bool checkForAllCallLikeInstructions(const function_ref< bool(Instruction &)> &Pred, const AbstractAttribute &QueryingAA)
Check Pred on all call-like instructions (=CallBased derived).
Definition: Attributor.h:701
AANoAliasCallSiteArgument(const IRPosition &IRP)
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
AADereferenceableCallSiteArgument(const IRPosition &IRP)
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
virtual ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(Attributor &A).
bool checkForAllReturnedValuesAndReturnInsts(const function_ref< bool(Value &, const SmallPtrSetImpl< ReturnInst *> &)> &Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by F.
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1247
NonNull attribute for a floating value.
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
Definition: Attributor.cpp:667
An abstract interface for all dereferenceable attribute.
Definition: Attributor.h:1353
AAType & registerAA(AAType &AA)
Introduce a new abstract attribute into the fixpoint analysis.
Definition: Attributor.h:628
This is an important base class in LLVM.
Definition: Constant.h:41
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, StateType &S)
Clamp the information known at all call sites for a given argument (identified by QueryingAA) into S...
Definition: Attributor.cpp:543
bool operator==(const DerefState &R)
Equality for DerefState.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
const Instruction & front() const
Definition: BasicBlock.h:280
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
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
static bool containsPossiblyEndlessLoop(Function *F)
void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl< Attribute > &Attrs) const override
Return the deduced attributes in Attrs.
Value & getAnchorValue()
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:240
Represent the analysis usage information of a pass.
static const IRPosition returned(const Function &F)
Create a position describing the returned value of F.
Definition: Attributor.h:172
An attribute for a function (scope).
Definition: Attributor.h:146
virtual void initialize(Attributor &A)
Initialize the state with the information in the Attributor A.
Definition: Attributor.h:1039
IntegerState DerefBytesState
State representing for dereferenceable bytes.
bool hasInternalLinkage() const
Definition: GlobalValue.h:443
Dereferenceable attribute for a call site argument.
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
AANoUnwindFunction(const IRPosition &IRP)
Definition: Attributor.cpp:664
Attribute::AttrKind getKindAsEnum() const
Return the attribute&#39;s kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:202
An attribute for a function argument.
Definition: Attributor.h:148
bool isEnumAttribute() const
Return true if the attribute is an Attribute::AttrKind type.
Definition: Attributes.cpp:186
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
The fixpoint analysis framework that orchestrates the attribute deduction.
Definition: Attributor.h:569
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:728
AANoUnwindImpl(const IRPosition &IRP)
Definition: Attributor.cpp:625
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:588
Argument * getArg(unsigned i) const
Definition: Function.h:713
---------------—— Function Return Values -------------------------——
Definition: Attributor.cpp:680
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
DerefState operator^=(const DerefState &R)
See IntegerState::operator^=.
#define STATS_DECL(NAME, TYPE, MSG)
Definition: Attributor.cpp:73
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
IntegerState StateType
Provide static access to the type of the state.
Definition: Attributor.h:943
const DataLayout & getDataLayout() const
Return the data layout associated with the anchor scope.
Definition: Attributor.h:719
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
void trackStatistics() const override
Hook to enable custom statistic tracking, called after manifest that resulted in a change if statisti...
Simple state with integers encoding.
Definition: Attributor.h:803
void getAttrs(ArrayRef< Attribute::AttrKind > AKs, SmallVectorImpl< Attribute > &Attrs) const
Return the attributes of any kind in AKs existing in the IR at a position that will affect this one...
Definition: Attributor.cpp:398
#define CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS)
bool hasAttr(ArrayRef< Attribute::AttrKind > AKs) const
TODO: Figure out if the attribute related helper functions should live here or somewhere else...
Definition: Attributor.cpp:390
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:531
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1433
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
Definition: Value.cpp:531
AAReturnedFromReturnedValues(const IRPosition &IRP)
Definition: Attributor.cpp:528
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.
AAAlignArgument(const IRPosition &IRP)
llvm::iterator_range< const_iterator > returned_values() const override
Definition: Attributor.cpp:743
size_t size() const
Definition: SmallVector.h:52
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:1025
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1349
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.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1172
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...).
Definition: Attributor.cpp:776
const AbstractState & getState() const override
See AbstractAttribute::getState(...).
Definition: Attributor.cpp:734
const StateType & getState() const override
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
void exploreFromEntry(Attributor &A, const Function *F)
size_type size() const
Definition: SmallPtrSet.h:92
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
virtual StateType & getState()=0
Return the internal abstract state for inspection.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1154
An AbstractAttribute for nofree.
Definition: Attributor.h:1270
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
Definition: Attributor.cpp:633
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
bool isKnownDead(const BasicBlock *BB) const override
See AAIsDead::isKnownDead(BasicBlock *).
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
const std::string getAsStr() const override
Pretty print the attribute similar to the IR representation.
Definition: Attributor.cpp:816
Dereferenceable attribute for a return value.
virtual ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
static const AAType * checkAndRegisterAA(const IRPosition &IRP, Attributor &A, DenseSet< const char *> *Whitelist)
Helper function that checks if an abstract attribute of type AAType should be created for IR position...
ChangeStatus indicatePessimisticFixpoint() override
See AbstractState::indicatePessimisticFixpoint(...)
AANonNullCallSiteReturned(const IRPosition &IRP)
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:500
bool isConvergent() const
Determine if the call is convergent.
Definition: CallSite.h:534
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
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))
AADereferenceableFloating(const IRPosition &IRP)
AAIsDeadFunction(const IRPosition &IRP)
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull) const
Returns the number of bytes known to be dereferenceable for the pointer value.
Definition: Value.cpp:612
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
void initialize(Attributor &A) override
See AbstractAttribute::initialize(...).
AANoFreeFunction(const IRPosition &IRP)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
ChangeStatus indicateOptimisticFixpoint() override
See AbstractState::indicateOptimisticFixpoint(...)
Helper class for generic deduction: call site argument -> argument position.
Definition: Attributor.cpp:584
DenseSet< const BasicBlock * > AssumedLiveBlocks
Collection of all assumed live BasicBlocks.
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:226
#define STATS_DECLTRACK(NAME, TYPE, MSG)
Definition: Attributor.cpp:75
static bool containsCycle(Function &F)
---------------------— Will-Return Attributes -------------------------—
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool checkForAllCallSites(const function_ref< bool(CallSite)> &Pred, const AbstractAttribute &QueryingAA, bool RequireAllCallSites)
Check Pred on all function call sites.
void takeAssumedDerefBytesMinimum(uint64_t Bytes)
Update assumed dereferenceable bytes.
static const IRPosition callsite_returned(const CallBase &CB)
Create a position describing the returned value of CB.
Definition: Attributor.h:187
A range adaptor for a pair of iterators.
static bool isVolatile(Instruction *I)
Helper function used to determine whether an instruction is volatile.
Class for arbitrary precision integers.
Definition: APInt.h:69
#define STATS_DECLTRACK_CSRET_ATTR(NAME)
Definition: Attributor.cpp:92
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:877
amdgpu Simplify well known AMD library false FunctionCallee Callee
#define STATS_DECLTRACK_FNRET_ATTR(NAME)
Definition: Attributor.cpp:89
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1190
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.
size_t getNumReturnValues() const override
Return the number of potential return values, -1 if unknown.
Definition: Attributor.cpp:752
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1304
bool checkForAllReturnedValues(const function_ref< bool(Value &)> &Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by the function associated with QueryingAA.
AANoFreeImpl(const IRPosition &IRP)
AANoReturnImpl(const IRPosition &IRP)
static const IRPosition value(const Value &V)
Create a position describing the value of V.
Definition: Attributor.h:158
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
const std::string getAsStr() const override
See AbstractAttribute::getAsStr().
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
AANonNullReturned(const IRPosition &IRP)
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
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:765
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:638
AANonNullCallSiteArgument(const IRPosition &IRP)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isNonRelaxedAtomic(Instruction *I)
Helper function used to determine whether an instruction is non-relaxed atomic.
bool hasValue() const
Definition: Optional.h:259
Function * getAssociatedFunction()
}
Definition: Attributor.h:253
bool checkForAllInstructions(const function_ref< bool(Instruction &)> &Pred, const AbstractAttribute &QueryingAA, const ArrayRef< unsigned > &Opcodes)
Check Pred on all instructions with an opcode present in Opcodes.
An abstract interface for all align attributes.
Definition: Attributor.h:1383
LLVM_NODISCARD AttributeList addAttribute(LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const
Add an attribute to the attribute set at the given index.
static const IRPosition argument(const Argument &Arg)
Create a position describing the argument Arg.
Definition: Attributor.h:177
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information...
Definition: Local.cpp:1936
bool isAssumedGlobal() const override
See AADereferenceable::isAssumedGlobal().
Pass * createAttributorLegacyPass()
bool genericValueTraversal(Attributor &A, IRPosition IRP, const AAType &QueryingAA, StateTy &State, const function_ref< bool(Value &, StateTy &, bool)> &VisitValueCB, int MaxValues=8)
}
Definition: Attributor.cpp:142
---------------------— NoAlias Argument Attribute ---------------------—
InformationCache & getInfoCache()
Return the internal information cache.
Definition: Attributor.h:641
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Align attribute for function argument.
NonNull attribute for function return value.
ChangeStatus indicatePessimisticFixpoint() override
Indicate that the abstract state should converge to the pessimistic state.
Definition: Attributor.cpp:782
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
LLVM_NODISCARD AttributeList removeAttribute(LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const
Remove the specified attribute at the specified index from this attribute list.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
bool isAssumedNonNull() const override
Return true if we assume that the underlying value is nonnull.
AAReturnedValuesFunction(const IRPosition &IRP)
ChangeStatus clampStateAndIndicateChange< DerefState >(DerefState &S, const DerefState &R)
AANoAliasImpl(const IRPosition &IRP)
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
static bool mayCatchAsynchronousExceptions(const Function &F)
Determine if F might catch asynchronous exceptions.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1209
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
DerefState operator|=(const DerefState &R)
See IntegerState::operator|=.
---------------------— NonNull Argument Attribute ---------------------—
AADereferenceableImpl(const IRPosition &IRP)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
Definition: Attributor.h:182
uint32_t Size
Definition: Profile.cpp:46
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
ChangeStatus clampStateAndIndicateChange< BooleanState >(BooleanState &S, const BooleanState &R)
Definition: Attributor.cpp:476
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
An attribute for a call site (function scope).
Definition: Attributor.h:147
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
static const char ID
Unique ID (due to the unique address)
Definition: Attributor.h:1379
bool isAfterNoReturn(const Instruction *I) const
Check if instruction is after noreturn call, in other words, assumed dead.
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, AttributeList &Attrs, int AttrIdx)
Return true if the information provided by Attr was added to the attribute list Attrs.
Definition: Attributor.cpp:229
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
uint32_t getAssumedDereferenceableBytes() const override
}
ChangeStatus manifest(Attributor &A) override
See AbstractAttribute::manifest(...).
Definition: Attributor.cpp:789
AACallSiteReturnedFromReturned(const IRPosition &IRP)
Definition: Attributor.cpp:600
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
iterator_range< df_iterator< T > > depth_first(const T &G)
static const IRPosition EmptyKey
Special DenseMap key values.
Definition: Attributor.h:414
Deduce and propagate attributes
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Helper class for generic replication: function returned -> cs returned.
Definition: Attributor.cpp:599
AADereferenceableArgument(const IRPosition &IRP)
static const IRPosition TombstoneKey
Definition: Attributor.h:415
bool operator!=(const DerefState &R)
Inequality for IntegerState.
LLVM Value Representation.
Definition: Value.h:73
AANoAliasReturned(const IRPosition &IRP)
E & operator &=(E &LHS, E RHS)
Definition: BitmaskEnum.h:133
Function * getAnchorScope()
}
Definition: Attributor.h:275
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.h:1073
static cl::opt< bool > DisableAttributor("attributor-disable", cl::Hidden, cl::desc("Disable the attributor inter-procedural deduction pass."), cl::init(true))
#define CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS)
A vector that has set insertion semantics.
Definition: SetVector.h:40
succ_range successors(Instruction *I)
Definition: CFG.h:259
Synchronized with respect to signal handlers executing in the same thread.
Definition: LLVMContext.h:51
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
An invalid position.
Definition: Attributor.h:141
bool checkForAllReturnedValuesAndReturnInsts(const function_ref< bool(Value &, const SmallPtrSetImpl< ReturnInst *> &)> &Pred) const override
See AbstractState::checkForAllReturnedValues(...).
Definition: Attributor.cpp:854
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
NonNull attribute for function argument.
AAWillReturnImpl(const IRPosition &IRP)
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint()
Definition: Attributor.h:818
const SmallPtrSetImpl< CallBase * > & getUnresolvedCalls() const override
Definition: Attributor.cpp:747
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
Definition: Attributor.h:192
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
const Instruction * findNextNoReturn(Attributor &A, const Instruction *I)
Find the next assumed noreturn instruction in the block of I starting from, thus including, I.
A container for analyses that lazily runs them and caches their results.
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
void identifyDefaultAbstractAttributes(Function &F, DenseSet< const char *> *Whitelist=nullptr)
Determine opportunities to derive &#39;default&#39; attributes in F and create abstract attribute objects for...
static bool isVolatile(Instruction *Inst)
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2005
virtual ChangeStatus updateImpl(Attributor &A)=0
The actual update/transfer function which has to be implemented by the derived classes.
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
Definition: Attributor.cpp:603
Dereferenceable attribute for a floating value.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
virtual ChangeStatus indicateOptimisticFixpoint()=0
Indicate that the abstract state should converge to the optimistic state.
virtual bool isAssumedDead(const BasicBlock *BB) const =0
Returns true if BB is assumed dead.
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
SmallSetVector< const Instruction *, 4 > NoReturnCalls
Collection of calls with noreturn attribute, assumed or knwon.
const std::string getAsStr() const override
This function should return the "summarized" assumed state as string.
bool isAtFixpoint() const override
See AbstractState::isAtFixpoint().
Definition: Attributor.cpp:770
void trackStatistics() const override
See AbstractAttribute::trackStatistics()
ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R)
Helper functions to clamp a state S of type StateType with the information in R and indicate/return i...
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:1893
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:133
static const IRPosition function(const Function &F)
Create a position describing the function scope of F.
Definition: Attributor.h:167
virtual void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl< Attribute > &Attrs) const override
See AbstractAttribute::getDeducedAttributes.
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:277
Kind getPositionKind() const
Return the associated position kind.
Definition: Attributor.h:351
ValTy * getArgOperand(unsigned i) const
Definition: CallSite.h:307
iterator_range< arg_iterator > args()
Definition: Function.h:719
static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA, StateType &S)
}
Definition: Attributor.cpp:485
AbstractState & getState() override
See AbstractAttribute::getState(...).
Definition: Attributor.cpp:731
const BasicBlock * getParent() const
Definition: Instruction.h:66
AAWillReturnFunction(const IRPosition &IRP)
Simple wrapper for a single bit (boolean) state.
Definition: Attributor.h:928
-----------------— Dereferenceable Argument Attribute -----------------—
ChangeStatus updateImpl(Attributor &A) override
See AbstractAttribute::updateImpl(...).
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:70
bool isAssumedDead(const Instruction *I) const override
See AAIsDead::isAssumed(Instruction *I).
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...
#define STATS_DECLTRACK_FLOATING_ATTR(NAME)
Definition: Attributor.cpp:95