LLVM  12.0.0git
AttributorAttributes.cpp
Go to the documentation of this file.
1 //===- AttributorAttributes.cpp - Attributes for Attributor 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 // See the Attributor.h file comment and the class descriptions in that file for
10 // more information.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/Statistic.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/NoFolder.h"
30 
31 #include <cassert>
32 
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "attributor"
36 
38  "attributor-manifest-internal", cl::Hidden,
39  cl::desc("Manifest Attributor internal string attributes."),
40  cl::init(false));
41 
42 static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128),
43  cl::Hidden);
44 
45 STATISTIC(NumAAs, "Number of abstract attributes created");
46 
47 // Some helper macros to deal with statistics tracking.
48 //
49 // Usage:
50 // For simple IR attribute tracking overload trackStatistics in the abstract
51 // attribute and choose the right STATS_DECLTRACK_********* macro,
52 // e.g.,:
53 // void trackStatistics() const override {
54 // STATS_DECLTRACK_ARG_ATTR(returned)
55 // }
56 // If there is a single "increment" side one can use the macro
57 // STATS_DECLTRACK with a custom message. If there are multiple increment
58 // sides, STATS_DECL and STATS_TRACK can also be used separately.
59 //
60 #define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME) \
61  ("Number of " #TYPE " marked '" #NAME "'")
62 #define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME
63 #define STATS_DECL_(NAME, MSG) STATISTIC(NAME, MSG);
64 #define STATS_DECL(NAME, TYPE, MSG) \
65  STATS_DECL_(BUILD_STAT_NAME(NAME, TYPE), MSG);
66 #define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE));
67 #define STATS_DECLTRACK(NAME, TYPE, MSG) \
68  { \
69  STATS_DECL(NAME, TYPE, MSG) \
70  STATS_TRACK(NAME, TYPE) \
71  }
72 #define STATS_DECLTRACK_ARG_ATTR(NAME) \
73  STATS_DECLTRACK(NAME, Arguments, BUILD_STAT_MSG_IR_ATTR(arguments, NAME))
74 #define STATS_DECLTRACK_CSARG_ATTR(NAME) \
75  STATS_DECLTRACK(NAME, CSArguments, \
76  BUILD_STAT_MSG_IR_ATTR(call site arguments, NAME))
77 #define STATS_DECLTRACK_FN_ATTR(NAME) \
78  STATS_DECLTRACK(NAME, Function, BUILD_STAT_MSG_IR_ATTR(functions, NAME))
79 #define STATS_DECLTRACK_CS_ATTR(NAME) \
80  STATS_DECLTRACK(NAME, CS, BUILD_STAT_MSG_IR_ATTR(call site, NAME))
81 #define STATS_DECLTRACK_FNRET_ATTR(NAME) \
82  STATS_DECLTRACK(NAME, FunctionReturn, \
83  BUILD_STAT_MSG_IR_ATTR(function returns, NAME))
84 #define STATS_DECLTRACK_CSRET_ATTR(NAME) \
85  STATS_DECLTRACK(NAME, CSReturn, \
86  BUILD_STAT_MSG_IR_ATTR(call site returns, NAME))
87 #define STATS_DECLTRACK_FLOATING_ATTR(NAME) \
88  STATS_DECLTRACK(NAME, Floating, \
89  ("Number of floating values known to be '" #NAME "'"))
90 
91 // Specialization of the operator<< for abstract attributes subclasses. This
92 // disambiguates situations where multiple operators are applicable.
93 namespace llvm {
94 #define PIPE_OPERATOR(CLASS) \
95  raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) { \
96  return OS << static_cast<const AbstractAttribute &>(AA); \
97  }
98 
120 
121 #undef PIPE_OPERATOR
122 } // namespace llvm
123 
124 namespace {
125 
127 getAssumedConstantInt(Attributor &A, const Value &V,
128  const AbstractAttribute &AA,
129  bool &UsedAssumedInformation) {
130  Optional<Constant *> C = A.getAssumedConstant(V, AA, UsedAssumedInformation);
131  if (C.hasValue())
132  return dyn_cast_or_null<ConstantInt>(C.getValue());
133  return llvm::None;
134 }
135 
136 /// Get pointer operand of memory accessing instruction. If \p I is
137 /// not a memory accessing instruction, return nullptr. If \p AllowVolatile,
138 /// is set to false and the instruction is volatile, return nullptr.
139 static const Value *getPointerOperand(const Instruction *I,
140  bool AllowVolatile) {
141  if (auto *LI = dyn_cast<LoadInst>(I)) {
142  if (!AllowVolatile && LI->isVolatile())
143  return nullptr;
144  return LI->getPointerOperand();
145  }
146 
147  if (auto *SI = dyn_cast<StoreInst>(I)) {
148  if (!AllowVolatile && SI->isVolatile())
149  return nullptr;
150  return SI->getPointerOperand();
151  }
152 
153  if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) {
154  if (!AllowVolatile && CXI->isVolatile())
155  return nullptr;
156  return CXI->getPointerOperand();
157  }
158 
159  if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) {
160  if (!AllowVolatile && RMWI->isVolatile())
161  return nullptr;
162  return RMWI->getPointerOperand();
163  }
164 
165  return nullptr;
166 }
167 
168 /// Helper function to create a pointer of type \p ResTy, based on \p Ptr, and
169 /// advanced by \p Offset bytes. To aid later analysis the method tries to build
170 /// getelement pointer instructions that traverse the natural type of \p Ptr if
171 /// possible. If that fails, the remaining offset is adjusted byte-wise, hence
172 /// through a cast to i8*.
173 ///
174 /// TODO: This could probably live somewhere more prominantly if it doesn't
175 /// already exist.
176 static Value *constructPointer(Type *ResTy, Value *Ptr, int64_t Offset,
177  IRBuilder<NoFolder> &IRB, const DataLayout &DL) {
178  assert(Offset >= 0 && "Negative offset not supported yet!");
179  LLVM_DEBUG(dbgs() << "Construct pointer: " << *Ptr << " + " << Offset
180  << "-bytes as " << *ResTy << "\n");
181 
182  // The initial type we are trying to traverse to get nice GEPs.
183  Type *Ty = Ptr->getType();
184 
185  SmallVector<Value *, 4> Indices;
186  std::string GEPName = Ptr->getName().str();
187  while (Offset) {
188  uint64_t Idx, Rem;
189 
190  if (auto *STy = dyn_cast<StructType>(Ty)) {
191  const StructLayout *SL = DL.getStructLayout(STy);
192  if (int64_t(SL->getSizeInBytes()) < Offset)
193  break;
194  Idx = SL->getElementContainingOffset(Offset);
195  assert(Idx < STy->getNumElements() && "Offset calculation error!");
196  Rem = Offset - SL->getElementOffset(Idx);
197  Ty = STy->getElementType(Idx);
198  } else if (auto *PTy = dyn_cast<PointerType>(Ty)) {
199  Ty = PTy->getElementType();
200  if (!Ty->isSized())
201  break;
202  uint64_t ElementSize = DL.getTypeAllocSize(Ty);
203  assert(ElementSize && "Expected type with size!");
204  Idx = Offset / ElementSize;
205  Rem = Offset % ElementSize;
206  } else {
207  // Non-aggregate type, we cast and make byte-wise progress now.
208  break;
209  }
210 
211  LLVM_DEBUG(errs() << "Ty: " << *Ty << " Offset: " << Offset
212  << " Idx: " << Idx << " Rem: " << Rem << "\n");
213 
214  GEPName += "." + std::to_string(Idx);
215  Indices.push_back(ConstantInt::get(IRB.getInt32Ty(), Idx));
216  Offset = Rem;
217  }
218 
219  // Create a GEP if we collected indices above.
220  if (Indices.size())
221  Ptr = IRB.CreateGEP(Ptr, Indices, GEPName);
222 
223  // If an offset is left we use byte-wise adjustment.
224  if (Offset) {
225  Ptr = IRB.CreateBitCast(Ptr, IRB.getInt8PtrTy());
226  Ptr = IRB.CreateGEP(Ptr, IRB.getInt32(Offset),
227  GEPName + ".b" + Twine(Offset));
228  }
229 
230  // Ensure the result has the requested type.
231  Ptr = IRB.CreateBitOrPointerCast(Ptr, ResTy, Ptr->getName() + ".cast");
232 
233  LLVM_DEBUG(dbgs() << "Constructed pointer: " << *Ptr << "\n");
234  return Ptr;
235 }
236 
237 /// Recursively visit all values that might become \p IRP at some point. This
238 /// will be done by looking through cast instructions, selects, phis, and calls
239 /// with the "returned" attribute. Once we cannot look through the value any
240 /// further, the callback \p VisitValueCB is invoked and passed the current
241 /// value, the \p State, and a flag to indicate if we stripped anything.
242 /// Stripped means that we unpacked the value associated with \p IRP at least
243 /// once. Note that the value used for the callback may still be the value
244 /// associated with \p IRP (due to PHIs). To limit how much effort is invested,
245 /// we will never visit more values than specified by \p MaxValues.
246 template <typename AAType, typename StateTy>
247 static bool genericValueTraversal(
248  Attributor &A, IRPosition IRP, const AAType &QueryingAA, StateTy &State,
249  function_ref<bool(Value &, const Instruction *, StateTy &, bool)>
250  VisitValueCB,
251  const Instruction *CtxI, bool UseValueSimplify = true, int MaxValues = 16,
252  function_ref<Value *(Value *)> StripCB = nullptr) {
253 
254  const AAIsDead *LivenessAA = nullptr;
255  if (IRP.getAnchorScope())
256  LivenessAA = &A.getAAFor<AAIsDead>(
257  QueryingAA, IRPosition::function(*IRP.getAnchorScope()),
258  /* TrackDependence */ false);
259  bool AnyDead = false;
260 
261  using Item = std::pair<Value *, const Instruction *>;
262  SmallSet<Item, 16> Visited;
263  SmallVector<Item, 16> Worklist;
264  Worklist.push_back({&IRP.getAssociatedValue(), CtxI});
265 
266  int Iteration = 0;
267  do {
268  Item I = Worklist.pop_back_val();
269  Value *V = I.first;
270  CtxI = I.second;
271  if (StripCB)
272  V = StripCB(V);
273 
274  // Check if we should process the current value. To prevent endless
275  // recursion keep a record of the values we followed!
276  if (!Visited.insert(I).second)
277  continue;
278 
279  // Make sure we limit the compile time for complex expressions.
280  if (Iteration++ >= MaxValues)
281  return false;
282 
283  // Explicitly look through calls with a "returned" attribute if we do
284  // not have a pointer as stripPointerCasts only works on them.
285  Value *NewV = nullptr;
286  if (V->getType()->isPointerTy()) {
287  NewV = V->stripPointerCasts();
288  } else {
289  auto *CB = dyn_cast<CallBase>(V);
290  if (CB && CB->getCalledFunction()) {
291  for (Argument &Arg : CB->getCalledFunction()->args())
292  if (Arg.hasReturnedAttr()) {
293  NewV = CB->getArgOperand(Arg.getArgNo());
294  break;
295  }
296  }
297  }
298  if (NewV && NewV != V) {
299  Worklist.push_back({NewV, CtxI});
300  continue;
301  }
302 
303  // Look through select instructions, visit both potential values.
304  if (auto *SI = dyn_cast<SelectInst>(V)) {
305  Worklist.push_back({SI->getTrueValue(), CtxI});
306  Worklist.push_back({SI->getFalseValue(), CtxI});
307  continue;
308  }
309 
310  // Look through phi nodes, visit all live operands.
311  if (auto *PHI = dyn_cast<PHINode>(V)) {
312  assert(LivenessAA &&
313  "Expected liveness in the presence of instructions!");
314  for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
315  BasicBlock *IncomingBB = PHI->getIncomingBlock(u);
316  if (A.isAssumedDead(*IncomingBB->getTerminator(), &QueryingAA,
317  LivenessAA,
318  /* CheckBBLivenessOnly */ true)) {
319  AnyDead = true;
320  continue;
321  }
322  Worklist.push_back(
323  {PHI->getIncomingValue(u), IncomingBB->getTerminator()});
324  }
325  continue;
326  }
327 
328  if (UseValueSimplify && !isa<Constant>(V)) {
329  bool UsedAssumedInformation = false;
331  A.getAssumedConstant(*V, QueryingAA, UsedAssumedInformation);
332  if (!C.hasValue())
333  continue;
334  if (Value *NewV = C.getValue()) {
335  Worklist.push_back({NewV, CtxI});
336  continue;
337  }
338  }
339 
340  // Once a leaf is reached we inform the user through the callback.
341  if (!VisitValueCB(*V, CtxI, State, Iteration > 1))
342  return false;
343  } while (!Worklist.empty());
344 
345  // If we actually used liveness information so we have to record a dependence.
346  if (AnyDead)
347  A.recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL);
348 
349  // All values have been visited.
350  return true;
351 }
352 
353 const Value *stripAndAccumulateMinimalOffsets(
354  Attributor &A, const AbstractAttribute &QueryingAA, const Value *Val,
355  const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
356  bool UseAssumed = false) {
357 
358  auto AttributorAnalysis = [&](Value &V, APInt &ROffset) -> bool {
359  const IRPosition &Pos = IRPosition::value(V);
360  // Only track dependence if we are going to use the assumed info.
361  const AAValueConstantRange &ValueConstantRangeAA =
362  A.getAAFor<AAValueConstantRange>(QueryingAA, Pos,
363  /* TrackDependence */ UseAssumed);
364  ConstantRange Range = UseAssumed ? ValueConstantRangeAA.getAssumed()
365  : ValueConstantRangeAA.getKnown();
366  // We can only use the lower part of the range because the upper part can
367  // be higher than what the value can really be.
368  ROffset = Range.getSignedMin();
369  return true;
370  };
371 
372  return Val->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds,
373  AttributorAnalysis);
374 }
375 
376 static const Value *getMinimalBaseOfAccsesPointerOperand(
377  Attributor &A, const AbstractAttribute &QueryingAA, const Instruction *I,
378  int64_t &BytesOffset, const DataLayout &DL, bool AllowNonInbounds = false) {
379  const Value *Ptr = getPointerOperand(I, /* AllowVolatile */ false);
380  if (!Ptr)
381  return nullptr;
382  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
383  const Value *Base = stripAndAccumulateMinimalOffsets(
384  A, QueryingAA, Ptr, DL, OffsetAPInt, AllowNonInbounds);
385 
386  BytesOffset = OffsetAPInt.getSExtValue();
387  return Base;
388 }
389 
390 static const Value *
391 getBasePointerOfAccessPointerOperand(const Instruction *I, int64_t &BytesOffset,
392  const DataLayout &DL,
393  bool AllowNonInbounds = false) {
394  const Value *Ptr = getPointerOperand(I, /* AllowVolatile */ false);
395  if (!Ptr)
396  return nullptr;
397 
398  return GetPointerBaseWithConstantOffset(Ptr, BytesOffset, DL,
399  AllowNonInbounds);
400 }
401 
402 /// Helper function to clamp a state \p S of type \p StateType with the
403 /// information in \p R and indicate/return if \p S did change (as-in update is
404 /// required to be run again).
405 template <typename StateType>
406 ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) {
407  auto Assumed = S.getAssumed();
408  S ^= R;
409  return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
411 }
412 
413 /// Clamp the information known for all returned values of a function
414 /// (identified by \p QueryingAA) into \p S.
415 template <typename AAType, typename StateType = typename AAType::StateType>
416 static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA,
417  StateType &S) {
418  LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for "
419  << QueryingAA << " into " << S << "\n");
420 
421  assert((QueryingAA.getIRPosition().getPositionKind() ==
423  QueryingAA.getIRPosition().getPositionKind() ==
425  "Can only clamp returned value states for a function returned or call "
426  "site returned position!");
427 
428  // Use an optional state as there might not be any return values and we want
429  // to join (IntegerState::operator&) the state of all there are.
431 
432  // Callback for each possibly returned value.
433  auto CheckReturnValue = [&](Value &RV) -> bool {
434  const IRPosition &RVPos = IRPosition::value(RV);
435  const AAType &AA = A.getAAFor<AAType>(QueryingAA, RVPos);
436  LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr()
437  << " @ " << RVPos << "\n");
438  const StateType &AAS = static_cast<const StateType &>(AA.getState());
439  if (T.hasValue())
440  *T &= AAS;
441  else
442  T = AAS;
443  LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T
444  << "\n");
445  return T->isValidState();
446  };
447 
448  if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA))
449  S.indicatePessimisticFixpoint();
450  else if (T.hasValue())
451  S ^= *T;
452 }
453 
454 /// Helper class for generic deduction: return value -> returned position.
455 template <typename AAType, typename BaseType,
456  typename StateType = typename BaseType::StateType>
457 struct AAReturnedFromReturnedValues : public BaseType {
458  AAReturnedFromReturnedValues(const IRPosition &IRP, Attributor &A)
459  : BaseType(IRP, A) {}
460 
461  /// See AbstractAttribute::updateImpl(...).
462  ChangeStatus updateImpl(Attributor &A) override {
463  StateType S(StateType::getBestState(this->getState()));
464  clampReturnedValueStates<AAType, StateType>(A, *this, S);
465  // TODO: If we know we visited all returned values, thus no are assumed
466  // dead, we can take the known information from the state T.
467  return clampStateAndIndicateChange<StateType>(this->getState(), S);
468  }
469 };
470 
471 /// Clamp the information known at all call sites for a given argument
472 /// (identified by \p QueryingAA) into \p S.
473 template <typename AAType, typename StateType = typename AAType::StateType>
474 static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA,
475  StateType &S) {
476  LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for "
477  << QueryingAA << " into " << S << "\n");
478 
479  assert(QueryingAA.getIRPosition().getPositionKind() ==
481  "Can only clamp call site argument states for an argument position!");
482 
483  // Use an optional state as there might not be any return values and we want
484  // to join (IntegerState::operator&) the state of all there are.
486 
487  // The argument number which is also the call site argument number.
488  unsigned ArgNo = QueryingAA.getIRPosition().getArgNo();
489 
490  auto CallSiteCheck = [&](AbstractCallSite ACS) {
491  const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo);
492  // Check if a coresponding argument was found or if it is on not associated
493  // (which can happen for callback calls).
494  if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
495  return false;
496 
497  const AAType &AA = A.getAAFor<AAType>(QueryingAA, ACSArgPos);
498  LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction()
499  << " AA: " << AA.getAsStr() << " @" << ACSArgPos << "\n");
500  const StateType &AAS = static_cast<const StateType &>(AA.getState());
501  if (T.hasValue())
502  *T &= AAS;
503  else
504  T = AAS;
505  LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T
506  << "\n");
507  return T->isValidState();
508  };
509 
510  bool AllCallSitesKnown;
511  if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true,
512  AllCallSitesKnown))
513  S.indicatePessimisticFixpoint();
514  else if (T.hasValue())
515  S ^= *T;
516 }
517 
518 /// Helper class for generic deduction: call site argument -> argument position.
519 template <typename AAType, typename BaseType,
520  typename StateType = typename AAType::StateType>
521 struct AAArgumentFromCallSiteArguments : public BaseType {
522  AAArgumentFromCallSiteArguments(const IRPosition &IRP, Attributor &A)
523  : BaseType(IRP, A) {}
524 
525  /// See AbstractAttribute::updateImpl(...).
526  ChangeStatus updateImpl(Attributor &A) override {
527  StateType S(StateType::getBestState(this->getState()));
528  clampCallSiteArgumentStates<AAType, StateType>(A, *this, S);
529  // TODO: If we know we visited all incoming values, thus no are assumed
530  // dead, we can take the known information from the state T.
531  return clampStateAndIndicateChange<StateType>(this->getState(), S);
532  }
533 };
534 
535 /// Helper class for generic replication: function returned -> cs returned.
536 template <typename AAType, typename BaseType,
537  typename StateType = typename BaseType::StateType>
538 struct AACallSiteReturnedFromReturned : public BaseType {
539  AACallSiteReturnedFromReturned(const IRPosition &IRP, Attributor &A)
540  : BaseType(IRP, A) {}
541 
542  /// See AbstractAttribute::updateImpl(...).
543  ChangeStatus updateImpl(Attributor &A) override {
544  assert(this->getIRPosition().getPositionKind() ==
546  "Can only wrap function returned positions for call site returned "
547  "positions!");
548  auto &S = this->getState();
549 
550  const Function *AssociatedFunction =
551  this->getIRPosition().getAssociatedFunction();
552  if (!AssociatedFunction)
553  return S.indicatePessimisticFixpoint();
554 
555  IRPosition FnPos = IRPosition::returned(*AssociatedFunction);
556  const AAType &AA = A.getAAFor<AAType>(*this, FnPos);
557  return clampStateAndIndicateChange(
558  S, static_cast<const StateType &>(AA.getState()));
559  }
560 };
561 
562 /// Helper function to accumulate uses.
563 template <class AAType, typename StateType = typename AAType::StateType>
564 static void followUsesInContext(AAType &AA, Attributor &A,
566  const Instruction *CtxI,
568  StateType &State) {
569  auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
570  for (unsigned u = 0; u < Uses.size(); ++u) {
571  const Use *U = Uses[u];
572  if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
573  bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
574  if (Found && AA.followUseInMBEC(A, U, UserI, State))
575  for (const Use &Us : UserI->uses())
576  Uses.insert(&Us);
577  }
578  }
579 }
580 
581 /// Use the must-be-executed-context around \p I to add information into \p S.
582 /// The AAType class is required to have `followUseInMBEC` method with the
583 /// following signature and behaviour:
584 ///
585 /// bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I)
586 /// U - Underlying use.
587 /// I - The user of the \p U.
588 /// Returns true if the value should be tracked transitively.
589 ///
590 template <class AAType, typename StateType = typename AAType::StateType>
591 static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S,
592  Instruction &CtxI) {
593 
594  // Container for (transitive) uses of the associated value.
596  for (const Use &U : AA.getIRPosition().getAssociatedValue().uses())
597  Uses.insert(&U);
598 
601 
602  followUsesInContext<AAType>(AA, A, Explorer, &CtxI, Uses, S);
603 
604  if (S.isAtFixpoint())
605  return;
606 
608  auto Pred = [&](const Instruction *I) {
609  if (const BranchInst *Br = dyn_cast<BranchInst>(I))
610  if (Br->isConditional())
611  BrInsts.push_back(Br);
612  return true;
613  };
614 
615  // Here, accumulate conditional branch instructions in the context. We
616  // explore the child paths and collect the known states. The disjunction of
617  // those states can be merged to its own state. Let ParentState_i be a state
618  // to indicate the known information for an i-th branch instruction in the
619  // context. ChildStates are created for its successors respectively.
620  //
621  // ParentS_1 = ChildS_{1, 1} /\ ChildS_{1, 2} /\ ... /\ ChildS_{1, n_1}
622  // ParentS_2 = ChildS_{2, 1} /\ ChildS_{2, 2} /\ ... /\ ChildS_{2, n_2}
623  // ...
624  // ParentS_m = ChildS_{m, 1} /\ ChildS_{m, 2} /\ ... /\ ChildS_{m, n_m}
625  //
626  // Known State |= ParentS_1 \/ ParentS_2 \/... \/ ParentS_m
627  //
628  // FIXME: Currently, recursive branches are not handled. For example, we
629  // can't deduce that ptr must be dereferenced in below function.
630  //
631  // void f(int a, int c, int *ptr) {
632  // if(a)
633  // if (b) {
634  // *ptr = 0;
635  // } else {
636  // *ptr = 1;
637  // }
638  // else {
639  // if (b) {
640  // *ptr = 0;
641  // } else {
642  // *ptr = 1;
643  // }
644  // }
645  // }
646 
647  Explorer.checkForAllContext(&CtxI, Pred);
648  for (const BranchInst *Br : BrInsts) {
649  StateType ParentState;
650 
651  // The known state of the parent state is a conjunction of children's
652  // known states so it is initialized with a best state.
653  ParentState.indicateOptimisticFixpoint();
654 
655  for (const BasicBlock *BB : Br->successors()) {
656  StateType ChildState;
657 
658  size_t BeforeSize = Uses.size();
659  followUsesInContext(AA, A, Explorer, &BB->front(), Uses, ChildState);
660 
661  // Erase uses which only appear in the child.
662  for (auto It = Uses.begin() + BeforeSize; It != Uses.end();)
663  It = Uses.erase(It);
664 
665  ParentState &= ChildState;
666  }
667 
668  // Use only known state.
669  S += ParentState;
670  }
671 }
672 
673 /// -----------------------NoUnwind Function Attribute--------------------------
674 
675 struct AANoUnwindImpl : AANoUnwind {
676  AANoUnwindImpl(const IRPosition &IRP, Attributor &A) : AANoUnwind(IRP, A) {}
677 
678  const std::string getAsStr() const override {
679  return getAssumed() ? "nounwind" : "may-unwind";
680  }
681 
682  /// See AbstractAttribute::updateImpl(...).
683  ChangeStatus updateImpl(Attributor &A) override {
684  auto Opcodes = {
685  (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
686  (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
687  (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
688 
689  auto CheckForNoUnwind = [&](Instruction &I) {
690  if (!I.mayThrow())
691  return true;
692 
693  if (const auto *CB = dyn_cast<CallBase>(&I)) {
694  const auto &NoUnwindAA =
696  return NoUnwindAA.isAssumedNoUnwind();
697  }
698  return false;
699  };
700 
701  if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes))
702  return indicatePessimisticFixpoint();
703 
705  }
706 };
707 
708 struct AANoUnwindFunction final : public AANoUnwindImpl {
709  AANoUnwindFunction(const IRPosition &IRP, Attributor &A)
710  : AANoUnwindImpl(IRP, A) {}
711 
712  /// See AbstractAttribute::trackStatistics()
713  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) }
714 };
715 
716 /// NoUnwind attribute deduction for a call sites.
717 struct AANoUnwindCallSite final : AANoUnwindImpl {
718  AANoUnwindCallSite(const IRPosition &IRP, Attributor &A)
719  : AANoUnwindImpl(IRP, A) {}
720 
721  /// See AbstractAttribute::initialize(...).
722  void initialize(Attributor &A) override {
724  Function *F = getAssociatedFunction();
725  if (!F)
726  indicatePessimisticFixpoint();
727  }
728 
729  /// See AbstractAttribute::updateImpl(...).
730  ChangeStatus updateImpl(Attributor &A) override {
731  // TODO: Once we have call site specific value information we can provide
732  // call site specific liveness information and then it makes
733  // sense to specialize attributes for call sites arguments instead of
734  // redirecting requests to the callee argument.
735  Function *F = getAssociatedFunction();
736  const IRPosition &FnPos = IRPosition::function(*F);
737  auto &FnAA = A.getAAFor<AANoUnwind>(*this, FnPos);
738  return clampStateAndIndicateChange(
739  getState(),
740  static_cast<const AANoUnwind::StateType &>(FnAA.getState()));
741  }
742 
743  /// See AbstractAttribute::trackStatistics()
744  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); }
745 };
746 
747 /// --------------------- Function Return Values -------------------------------
748 
749 /// "Attribute" that collects all potential returned values and the return
750 /// instructions that they arise from.
751 ///
752 /// If there is a unique returned value R, the manifest method will:
753 /// - mark R with the "returned" attribute, if R is an argument.
754 class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState {
755 
756  /// Mapping of values potentially returned by the associated function to the
757  /// return instructions that might return them.
759 
760  /// Mapping to remember the number of returned values for a call site such
761  /// that we can avoid updates if nothing changed.
762  DenseMap<const CallBase *, unsigned> NumReturnedValuesPerKnownAA;
763 
764  /// Set of unresolved calls returned by the associated function.
765  SmallSetVector<CallBase *, 4> UnresolvedCalls;
766 
767  /// State flags
768  ///
769  ///{
770  bool IsFixed = false;
771  bool IsValidState = true;
772  ///}
773 
774 public:
775  AAReturnedValuesImpl(const IRPosition &IRP, Attributor &A)
776  : AAReturnedValues(IRP, A) {}
777 
778  /// See AbstractAttribute::initialize(...).
779  void initialize(Attributor &A) override {
780  // Reset the state.
781  IsFixed = false;
782  IsValidState = true;
783  ReturnedValues.clear();
784 
785  Function *F = getAssociatedFunction();
786  if (!F) {
787  indicatePessimisticFixpoint();
788  return;
789  }
790  assert(!F->getReturnType()->isVoidTy() &&
791  "Did not expect a void return type!");
792 
793  // The map from instruction opcodes to those instructions in the function.
794  auto &OpcodeInstMap = A.getInfoCache().getOpcodeInstMapForFunction(*F);
795 
796  // Look through all arguments, if one is marked as returned we are done.
797  for (Argument &Arg : F->args()) {
798  if (Arg.hasReturnedAttr()) {
799  auto &ReturnInstSet = ReturnedValues[&Arg];
800  if (auto *Insts = OpcodeInstMap.lookup(Instruction::Ret))
801  for (Instruction *RI : *Insts)
802  ReturnInstSet.insert(cast<ReturnInst>(RI));
803 
804  indicateOptimisticFixpoint();
805  return;
806  }
807  }
808 
809  if (!A.isFunctionIPOAmendable(*F))
810  indicatePessimisticFixpoint();
811  }
812 
813  /// See AbstractAttribute::manifest(...).
814  ChangeStatus manifest(Attributor &A) override;
815 
816  /// See AbstractAttribute::getState(...).
817  AbstractState &getState() override { return *this; }
818 
819  /// See AbstractAttribute::getState(...).
820  const AbstractState &getState() const override { return *this; }
821 
822  /// See AbstractAttribute::updateImpl(Attributor &A).
823  ChangeStatus updateImpl(Attributor &A) override;
824 
825  llvm::iterator_range<iterator> returned_values() override {
826  return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
827  }
828 
829  llvm::iterator_range<const_iterator> returned_values() const override {
830  return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
831  }
832 
833  const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const override {
834  return UnresolvedCalls;
835  }
836 
837  /// Return the number of potential return values, -1 if unknown.
838  size_t getNumReturnValues() const override {
839  return isValidState() ? ReturnedValues.size() : -1;
840  }
841 
842  /// Return an assumed unique return value if a single candidate is found. If
843  /// there cannot be one, return a nullptr. If it is not clear yet, return the
844  /// Optional::NoneType.
845  Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
846 
847  /// See AbstractState::checkForAllReturnedValues(...).
848  bool checkForAllReturnedValuesAndReturnInsts(
849  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
850  const override;
851 
852  /// Pretty print the attribute similar to the IR representation.
853  const std::string getAsStr() const override;
854 
855  /// See AbstractState::isAtFixpoint().
856  bool isAtFixpoint() const override { return IsFixed; }
857 
858  /// See AbstractState::isValidState().
859  bool isValidState() const override { return IsValidState; }
860 
861  /// See AbstractState::indicateOptimisticFixpoint(...).
862  ChangeStatus indicateOptimisticFixpoint() override {
863  IsFixed = true;
865  }
866 
867  ChangeStatus indicatePessimisticFixpoint() override {
868  IsFixed = true;
869  IsValidState = false;
870  return ChangeStatus::CHANGED;
871  }
872 };
873 
874 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
876 
877  // Bookkeeping.
878  assert(isValidState());
879  STATS_DECLTRACK(KnownReturnValues, FunctionReturn,
880  "Number of function with known return values");
881 
882  // Check if we have an assumed unique return value that we could manifest.
883  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue(A);
884 
885  if (!UniqueRV.hasValue() || !UniqueRV.getValue())
886  return Changed;
887 
888  // Bookkeeping.
889  STATS_DECLTRACK(UniqueReturnValue, FunctionReturn,
890  "Number of function with unique return");
891 
892  // Callback to replace the uses of CB with the constant C.
893  auto ReplaceCallSiteUsersWith = [&A](CallBase &CB, Constant &C) {
894  if (CB.use_empty())
896  if (A.changeValueAfterManifest(CB, C))
897  return ChangeStatus::CHANGED;
899  };
900 
901  // If the assumed unique return value is an argument, annotate it.
902  if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
903  if (UniqueRVArg->getType()->canLosslesslyBitCastTo(
904  getAssociatedFunction()->getReturnType())) {
905  getIRPosition() = IRPosition::argument(*UniqueRVArg);
906  Changed = IRAttribute::manifest(A);
907  }
908  } else if (auto *RVC = dyn_cast<Constant>(UniqueRV.getValue())) {
909  // We can replace the returned value with the unique returned constant.
910  Value &AnchorValue = getAnchorValue();
911  if (Function *F = dyn_cast<Function>(&AnchorValue)) {
912  for (const Use &U : F->uses())
913  if (CallBase *CB = dyn_cast<CallBase>(U.getUser()))
914  if (CB->isCallee(&U)) {
915  Constant *RVCCast =
916  CB->getType() == RVC->getType()
917  ? RVC
919  Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed;
920  }
921  } else {
922  assert(isa<CallBase>(AnchorValue) &&
923  "Expcected a function or call base anchor!");
924  Constant *RVCCast =
925  AnchorValue.getType() == RVC->getType()
926  ? RVC
927  : ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType());
928  Changed = ReplaceCallSiteUsersWith(cast<CallBase>(AnchorValue), *RVCCast);
929  }
930  if (Changed == ChangeStatus::CHANGED)
931  STATS_DECLTRACK(UniqueConstantReturnValue, FunctionReturn,
932  "Number of function returns replaced by constant return");
933  }
934 
935  return Changed;
936 }
937 
938 const std::string AAReturnedValuesImpl::getAsStr() const {
939  return (isAtFixpoint() ? "returns(#" : "may-return(#") +
940  (isValidState() ? std::to_string(getNumReturnValues()) : "?") +
941  ")[#UC: " + std::to_string(UnresolvedCalls.size()) + "]";
942 }
943 
945 AAReturnedValuesImpl::getAssumedUniqueReturnValue(Attributor &A) const {
946  // If checkForAllReturnedValues provides a unique value, ignoring potential
947  // undef values that can also be present, it is assumed to be the actual
948  // return value and forwarded to the caller of this method. If there are
949  // multiple, a nullptr is returned indicating there cannot be a unique
950  // returned value.
951  Optional<Value *> UniqueRV;
952 
953  auto Pred = [&](Value &RV) -> bool {
954  // If we found a second returned value and neither the current nor the saved
955  // one is an undef, there is no unique returned value. Undefs are special
956  // since we can pretend they have any value.
957  if (UniqueRV.hasValue() && UniqueRV != &RV &&
958  !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
959  UniqueRV = nullptr;
960  return false;
961  }
962 
963  // Do not overwrite a value with an undef.
964  if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
965  UniqueRV = &RV;
966 
967  return true;
968  };
969 
970  if (!A.checkForAllReturnedValues(Pred, *this))
971  UniqueRV = nullptr;
972 
973  return UniqueRV;
974 }
975 
976 bool AAReturnedValuesImpl::checkForAllReturnedValuesAndReturnInsts(
977  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
978  const {
979  if (!isValidState())
980  return false;
981 
982  // Check all returned values but ignore call sites as long as we have not
983  // encountered an overdefined one during an update.
984  for (auto &It : ReturnedValues) {
985  Value *RV = It.first;
986 
987  CallBase *CB = dyn_cast<CallBase>(RV);
988  if (CB && !UnresolvedCalls.count(CB))
989  continue;
990 
991  if (!Pred(*RV, It.second))
992  return false;
993  }
994 
995  return true;
996 }
997 
998 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
999  size_t NumUnresolvedCalls = UnresolvedCalls.size();
1000  bool Changed = false;
1001 
1002  // State used in the value traversals starting in returned values.
1003  struct RVState {
1004  // The map in which we collect return values -> return instrs.
1005  decltype(ReturnedValues) &RetValsMap;
1006  // The flag to indicate a change.
1007  bool &Changed;
1008  // The return instrs we come from.
1010  };
1011 
1012  // Callback for a leaf value returned by the associated function.
1013  auto VisitValueCB = [](Value &Val, const Instruction *, RVState &RVS,
1014  bool) -> bool {
1015  auto Size = RVS.RetValsMap[&Val].size();
1016  RVS.RetValsMap[&Val].insert(RVS.RetInsts.begin(), RVS.RetInsts.end());
1017  bool Inserted = RVS.RetValsMap[&Val].size() != Size;
1018  RVS.Changed |= Inserted;
1019  LLVM_DEBUG({
1020  if (Inserted)
1021  dbgs() << "[AAReturnedValues] 1 Add new returned value " << Val
1022  << " => " << RVS.RetInsts.size() << "\n";
1023  });
1024  return true;
1025  };
1026 
1027  // Helper method to invoke the generic value traversal.
1028  auto VisitReturnedValue = [&](Value &RV, RVState &RVS,
1029  const Instruction *CtxI) {
1030  IRPosition RetValPos = IRPosition::value(RV);
1031  return genericValueTraversal<AAReturnedValues, RVState>(
1032  A, RetValPos, *this, RVS, VisitValueCB, CtxI,
1033  /* UseValueSimplify */ false);
1034  };
1035 
1036  // Callback for all "return intructions" live in the associated function.
1037  auto CheckReturnInst = [this, &VisitReturnedValue, &Changed](Instruction &I) {
1038  ReturnInst &Ret = cast<ReturnInst>(I);
1039  RVState RVS({ReturnedValues, Changed, {}});
1040  RVS.RetInsts.insert(&Ret);
1041  return VisitReturnedValue(*Ret.getReturnValue(), RVS, &I);
1042  };
1043 
1044  // Start by discovering returned values from all live returned instructions in
1045  // the associated function.
1046  if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}))
1047  return indicatePessimisticFixpoint();
1048 
1049  // Once returned values "directly" present in the code are handled we try to
1050  // resolve returned calls. To avoid modifications to the ReturnedValues map
1051  // while we iterate over it we kept record of potential new entries in a copy
1052  // map, NewRVsMap.
1053  decltype(ReturnedValues) NewRVsMap;
1054 
1055  auto HandleReturnValue = [&](Value *RV, SmallSetVector<ReturnInst *, 4> &RIs) {
1056  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV
1057  << " by #" << RIs.size() << " RIs\n");
1058  CallBase *CB = dyn_cast<CallBase>(RV);
1059  if (!CB || UnresolvedCalls.count(CB))
1060  return;
1061 
1062  if (!CB->getCalledFunction()) {
1063  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB
1064  << "\n");
1065  UnresolvedCalls.insert(CB);
1066  return;
1067  }
1068 
1069  // TODO: use the function scope once we have call site AAReturnedValues.
1070  const auto &RetValAA = A.getAAFor<AAReturnedValues>(
1071  *this, IRPosition::function(*CB->getCalledFunction()));
1072  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Found another AAReturnedValues: "
1073  << RetValAA << "\n");
1074 
1075  // Skip dead ends, thus if we do not know anything about the returned
1076  // call we mark it as unresolved and it will stay that way.
1077  if (!RetValAA.getState().isValidState()) {
1078  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB
1079  << "\n");
1080  UnresolvedCalls.insert(CB);
1081  return;
1082  }
1083 
1084  // Do not try to learn partial information. If the callee has unresolved
1085  // return values we will treat the call as unresolved/opaque.
1086  auto &RetValAAUnresolvedCalls = RetValAA.getUnresolvedCalls();
1087  if (!RetValAAUnresolvedCalls.empty()) {
1088  UnresolvedCalls.insert(CB);
1089  return;
1090  }
1091 
1092  // Now check if we can track transitively returned values. If possible, thus
1093  // if all return value can be represented in the current scope, do so.
1094  bool Unresolved = false;
1095  for (auto &RetValAAIt : RetValAA.returned_values()) {
1096  Value *RetVal = RetValAAIt.first;
1097  if (isa<Argument>(RetVal) || isa<CallBase>(RetVal) ||
1098  isa<Constant>(RetVal))
1099  continue;
1100  // Anything that did not fit in the above categories cannot be resolved,
1101  // mark the call as unresolved.
1102  LLVM_DEBUG(dbgs() << "[AAReturnedValues] transitively returned value "
1103  "cannot be translated: "
1104  << *RetVal << "\n");
1105  UnresolvedCalls.insert(CB);
1106  Unresolved = true;
1107  break;
1108  }
1109 
1110  if (Unresolved)
1111  return;
1112 
1113  // Now track transitively returned values.
1114  unsigned &NumRetAA = NumReturnedValuesPerKnownAA[CB];
1115  if (NumRetAA == RetValAA.getNumReturnValues()) {
1116  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Skip call as it has not "
1117  "changed since it was seen last\n");
1118  return;
1119  }
1120  NumRetAA = RetValAA.getNumReturnValues();
1121 
1122  for (auto &RetValAAIt : RetValAA.returned_values()) {
1123  Value *RetVal = RetValAAIt.first;
1124  if (Argument *Arg = dyn_cast<Argument>(RetVal)) {
1125  // Arguments are mapped to call site operands and we begin the traversal
1126  // again.
1127  bool Unused = false;
1128  RVState RVS({NewRVsMap, Unused, RetValAAIt.second});
1129  VisitReturnedValue(*CB->getArgOperand(Arg->getArgNo()), RVS, CB);
1130  continue;
1131  } else if (isa<CallBase>(RetVal)) {
1132  // Call sites are resolved by the callee attribute over time, no need to
1133  // do anything for us.
1134  continue;
1135  } else if (isa<Constant>(RetVal)) {
1136  // Constants are valid everywhere, we can simply take them.
1137  NewRVsMap[RetVal].insert(RIs.begin(), RIs.end());
1138  continue;
1139  }
1140  }
1141  };
1142 
1143  for (auto &It : ReturnedValues)
1144  HandleReturnValue(It.first, It.second);
1145 
1146  // Because processing the new information can again lead to new return values
1147  // we have to be careful and iterate until this iteration is complete. The
1148  // idea is that we are in a stable state at the end of an update. All return
1149  // values have been handled and properly categorized. We might not update
1150  // again if we have not requested a non-fix attribute so we cannot "wait" for
1151  // the next update to analyze a new return value.
1152  while (!NewRVsMap.empty()) {
1153  auto It = std::move(NewRVsMap.back());
1154  NewRVsMap.pop_back();
1155 
1156  assert(!It.second.empty() && "Entry does not add anything.");
1157  auto &ReturnInsts = ReturnedValues[It.first];
1158  for (ReturnInst *RI : It.second)
1159  if (ReturnInsts.insert(RI)) {
1160  LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
1161  << *It.first << " => " << *RI << "\n");
1162  HandleReturnValue(It.first, ReturnInsts);
1163  Changed = true;
1164  }
1165  }
1166 
1167  Changed |= (NumUnresolvedCalls != UnresolvedCalls.size());
1169 }
1170 
1171 struct AAReturnedValuesFunction final : public AAReturnedValuesImpl {
1172  AAReturnedValuesFunction(const IRPosition &IRP, Attributor &A)
1173  : AAReturnedValuesImpl(IRP, A) {}
1174 
1175  /// See AbstractAttribute::trackStatistics()
1176  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(returned) }
1177 };
1178 
1179 /// Returned values information for a call sites.
1180 struct AAReturnedValuesCallSite final : AAReturnedValuesImpl {
1181  AAReturnedValuesCallSite(const IRPosition &IRP, Attributor &A)
1182  : AAReturnedValuesImpl(IRP, A) {}
1183 
1184  /// See AbstractAttribute::initialize(...).
1185  void initialize(Attributor &A) override {
1186  // TODO: Once we have call site specific value information we can provide
1187  // call site specific liveness information and then it makes
1188  // sense to specialize attributes for call sites instead of
1189  // redirecting requests to the callee.
1190  llvm_unreachable("Abstract attributes for returned values are not "
1191  "supported for call sites yet!");
1192  }
1193 
1194  /// See AbstractAttribute::updateImpl(...).
1195  ChangeStatus updateImpl(Attributor &A) override {
1196  return indicatePessimisticFixpoint();
1197  }
1198 
1199  /// See AbstractAttribute::trackStatistics()
1200  void trackStatistics() const override {}
1201 };
1202 
1203 /// ------------------------ NoSync Function Attribute -------------------------
1204 
1205 struct AANoSyncImpl : AANoSync {
1206  AANoSyncImpl(const IRPosition &IRP, Attributor &A) : AANoSync(IRP, A) {}
1207 
1208  const std::string getAsStr() const override {
1209  return getAssumed() ? "nosync" : "may-sync";
1210  }
1211 
1212  /// See AbstractAttribute::updateImpl(...).
1213  ChangeStatus updateImpl(Attributor &A) override;
1214 
1215  /// Helper function used to determine whether an instruction is non-relaxed
1216  /// atomic. In other words, if an atomic instruction does not have unordered
1217  /// or monotonic ordering
1218  static bool isNonRelaxedAtomic(Instruction *I);
1219 
1220  /// Helper function used to determine whether an instruction is volatile.
1221  static bool isVolatile(Instruction *I);
1222 
1223  /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
1224  /// memset).
1225  static bool isNoSyncIntrinsic(Instruction *I);
1226 };
1227 
1228 bool AANoSyncImpl::isNonRelaxedAtomic(Instruction *I) {
1229  if (!I->isAtomic())
1230  return false;
1231 
1232  AtomicOrdering Ordering;
1233  switch (I->getOpcode()) {
1234  case Instruction::AtomicRMW:
1235  Ordering = cast<AtomicRMWInst>(I)->getOrdering();
1236  break;
1237  case Instruction::Store:
1238  Ordering = cast<StoreInst>(I)->getOrdering();
1239  break;
1240  case Instruction::Load:
1241  Ordering = cast<LoadInst>(I)->getOrdering();
1242  break;
1243  case Instruction::Fence: {
1244  auto *FI = cast<FenceInst>(I);
1245  if (FI->getSyncScopeID() == SyncScope::SingleThread)
1246  return false;
1247  Ordering = FI->getOrdering();
1248  break;
1249  }
1250  case Instruction::AtomicCmpXchg: {
1251  AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
1252  AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
1253  // Only if both are relaxed, than it can be treated as relaxed.
1254  // Otherwise it is non-relaxed.
1255  if (Success != AtomicOrdering::Unordered &&
1256  Success != AtomicOrdering::Monotonic)
1257  return true;
1258  if (Failure != AtomicOrdering::Unordered &&
1259  Failure != AtomicOrdering::Monotonic)
1260  return true;
1261  return false;
1262  }
1263  default:
1265  "New atomic operations need to be known in the attributor.");
1266  }
1267 
1268  // Relaxed.
1269  if (Ordering == AtomicOrdering::Unordered ||
1270  Ordering == AtomicOrdering::Monotonic)
1271  return false;
1272  return true;
1273 }
1274 
1275 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
1276 /// FIXME: We should ipmrove the handling of intrinsics.
1277 bool AANoSyncImpl::isNoSyncIntrinsic(Instruction *I) {
1278  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1279  switch (II->getIntrinsicID()) {
1280  /// Element wise atomic memory intrinsics are can only be unordered,
1281  /// therefore nosync.
1282  case Intrinsic::memset_element_unordered_atomic:
1283  case Intrinsic::memmove_element_unordered_atomic:
1284  case Intrinsic::memcpy_element_unordered_atomic:
1285  return true;
1286  case Intrinsic::memset:
1287  case Intrinsic::memmove:
1288  case Intrinsic::memcpy:
1289  if (!cast<MemIntrinsic>(II)->isVolatile())
1290  return true;
1291  return false;
1292  default:
1293  return false;
1294  }
1295  }
1296  return false;
1297 }
1298 
1300  assert(!isa<CallBase>(I) && "Calls should not be checked here");
1301 
1302  switch (I->getOpcode()) {
1303  case Instruction::AtomicRMW:
1304  return cast<AtomicRMWInst>(I)->isVolatile();
1305  case Instruction::Store:
1306  return cast<StoreInst>(I)->isVolatile();
1307  case Instruction::Load:
1308  return cast<LoadInst>(I)->isVolatile();
1309  case Instruction::AtomicCmpXchg:
1310  return cast<AtomicCmpXchgInst>(I)->isVolatile();
1311  default:
1312  return false;
1313  }
1314 }
1315 
1316 ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) {
1317 
1318  auto CheckRWInstForNoSync = [&](Instruction &I) {
1319  /// We are looking for volatile instructions or Non-Relaxed atomics.
1320  /// FIXME: We should improve the handling of intrinsics.
1321 
1322  if (isa<IntrinsicInst>(&I) && isNoSyncIntrinsic(&I))
1323  return true;
1324 
1325  if (const auto *CB = dyn_cast<CallBase>(&I)) {
1326  if (CB->hasFnAttr(Attribute::NoSync))
1327  return true;
1328 
1329  const auto &NoSyncAA =
1331  if (NoSyncAA.isAssumedNoSync())
1332  return true;
1333  return false;
1334  }
1335 
1336  if (!isVolatile(&I) && !isNonRelaxedAtomic(&I))
1337  return true;
1338 
1339  return false;
1340  };
1341 
1342  auto CheckForNoSync = [&](Instruction &I) {
1343  // At this point we handled all read/write effects and they are all
1344  // nosync, so they can be skipped.
1345  if (I.mayReadOrWriteMemory())
1346  return true;
1347 
1348  // non-convergent and readnone imply nosync.
1349  return !cast<CallBase>(I).isConvergent();
1350  };
1351 
1352  if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this) ||
1353  !A.checkForAllCallLikeInstructions(CheckForNoSync, *this))
1354  return indicatePessimisticFixpoint();
1355 
1356  return ChangeStatus::UNCHANGED;
1357 }
1358 
1359 struct AANoSyncFunction final : public AANoSyncImpl {
1360  AANoSyncFunction(const IRPosition &IRP, Attributor &A)
1361  : AANoSyncImpl(IRP, A) {}
1362 
1363  /// See AbstractAttribute::trackStatistics()
1364  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) }
1365 };
1366 
1367 /// NoSync attribute deduction for a call sites.
1368 struct AANoSyncCallSite final : AANoSyncImpl {
1369  AANoSyncCallSite(const IRPosition &IRP, Attributor &A)
1370  : AANoSyncImpl(IRP, A) {}
1371 
1372  /// See AbstractAttribute::initialize(...).
1373  void initialize(Attributor &A) override {
1375  Function *F = getAssociatedFunction();
1376  if (!F)
1377  indicatePessimisticFixpoint();
1378  }
1379 
1380  /// See AbstractAttribute::updateImpl(...).
1381  ChangeStatus updateImpl(Attributor &A) override {
1382  // TODO: Once we have call site specific value information we can provide
1383  // call site specific liveness information and then it makes
1384  // sense to specialize attributes for call sites arguments instead of
1385  // redirecting requests to the callee argument.
1386  Function *F = getAssociatedFunction();
1387  const IRPosition &FnPos = IRPosition::function(*F);
1388  auto &FnAA = A.getAAFor<AANoSync>(*this, FnPos);
1389  return clampStateAndIndicateChange(
1390  getState(), static_cast<const AANoSync::StateType &>(FnAA.getState()));
1391  }
1392 
1393  /// See AbstractAttribute::trackStatistics()
1394  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nosync); }
1395 };
1396 
1397 /// ------------------------ No-Free Attributes ----------------------------
1398 
1399 struct AANoFreeImpl : public AANoFree {
1400  AANoFreeImpl(const IRPosition &IRP, Attributor &A) : AANoFree(IRP, A) {}
1401 
1402  /// See AbstractAttribute::updateImpl(...).
1403  ChangeStatus updateImpl(Attributor &A) override {
1404  auto CheckForNoFree = [&](Instruction &I) {
1405  const auto &CB = cast<CallBase>(I);
1406  if (CB.hasFnAttr(Attribute::NoFree))
1407  return true;
1408 
1409  const auto &NoFreeAA =
1411  return NoFreeAA.isAssumedNoFree();
1412  };
1413 
1414  if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this))
1415  return indicatePessimisticFixpoint();
1416  return ChangeStatus::UNCHANGED;
1417  }
1418 
1419  /// See AbstractAttribute::getAsStr().
1420  const std::string getAsStr() const override {
1421  return getAssumed() ? "nofree" : "may-free";
1422  }
1423 };
1424 
1425 struct AANoFreeFunction final : public AANoFreeImpl {
1426  AANoFreeFunction(const IRPosition &IRP, Attributor &A)
1427  : AANoFreeImpl(IRP, A) {}
1428 
1429  /// See AbstractAttribute::trackStatistics()
1430  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
1431 };
1432 
1433 /// NoFree attribute deduction for a call sites.
1434 struct AANoFreeCallSite final : AANoFreeImpl {
1435  AANoFreeCallSite(const IRPosition &IRP, Attributor &A)
1436  : AANoFreeImpl(IRP, A) {}
1437 
1438  /// See AbstractAttribute::initialize(...).
1439  void initialize(Attributor &A) override {
1441  Function *F = getAssociatedFunction();
1442  if (!F)
1443  indicatePessimisticFixpoint();
1444  }
1445 
1446  /// See AbstractAttribute::updateImpl(...).
1447  ChangeStatus updateImpl(Attributor &A) override {
1448  // TODO: Once we have call site specific value information we can provide
1449  // call site specific liveness information and then it makes
1450  // sense to specialize attributes for call sites arguments instead of
1451  // redirecting requests to the callee argument.
1452  Function *F = getAssociatedFunction();
1453  const IRPosition &FnPos = IRPosition::function(*F);
1454  auto &FnAA = A.getAAFor<AANoFree>(*this, FnPos);
1455  return clampStateAndIndicateChange(
1456  getState(), static_cast<const AANoFree::StateType &>(FnAA.getState()));
1457  }
1458 
1459  /// See AbstractAttribute::trackStatistics()
1460  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); }
1461 };
1462 
1463 /// NoFree attribute for floating values.
1464 struct AANoFreeFloating : AANoFreeImpl {
1465  AANoFreeFloating(const IRPosition &IRP, Attributor &A)
1466  : AANoFreeImpl(IRP, A) {}
1467 
1468  /// See AbstractAttribute::trackStatistics()
1469  void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)}
1470 
1471  /// See Abstract Attribute::updateImpl(...).
1472  ChangeStatus updateImpl(Attributor &A) override {
1473  const IRPosition &IRP = getIRPosition();
1474 
1475  const auto &NoFreeAA =
1477  if (NoFreeAA.isAssumedNoFree())
1478  return ChangeStatus::UNCHANGED;
1479 
1480  Value &AssociatedValue = getIRPosition().getAssociatedValue();
1481  auto Pred = [&](const Use &U, bool &Follow) -> bool {
1482  Instruction *UserI = cast<Instruction>(U.getUser());
1483  if (auto *CB = dyn_cast<CallBase>(UserI)) {
1484  if (CB->isBundleOperand(&U))
1485  return false;
1486  if (!CB->isArgOperand(&U))
1487  return true;
1488  unsigned ArgNo = CB->getArgOperandNo(&U);
1489 
1490  const auto &NoFreeArg = A.getAAFor<AANoFree>(
1491  *this, IRPosition::callsite_argument(*CB, ArgNo));
1492  return NoFreeArg.isAssumedNoFree();
1493  }
1494 
1495  if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) ||
1496  isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
1497  Follow = true;
1498  return true;
1499  }
1500  if (isa<ReturnInst>(UserI))
1501  return true;
1502 
1503  // Unknown user.
1504  return false;
1505  };
1506  if (!A.checkForAllUses(Pred, *this, AssociatedValue))
1507  return indicatePessimisticFixpoint();
1508 
1509  return ChangeStatus::UNCHANGED;
1510  }
1511 };
1512 
1513 /// NoFree attribute for a call site argument.
1514 struct AANoFreeArgument final : AANoFreeFloating {
1515  AANoFreeArgument(const IRPosition &IRP, Attributor &A)
1516  : AANoFreeFloating(IRP, A) {}
1517 
1518  /// See AbstractAttribute::trackStatistics()
1519  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) }
1520 };
1521 
1522 /// NoFree attribute for call site arguments.
1523 struct AANoFreeCallSiteArgument final : AANoFreeFloating {
1524  AANoFreeCallSiteArgument(const IRPosition &IRP, Attributor &A)
1525  : AANoFreeFloating(IRP, A) {}
1526 
1527  /// See AbstractAttribute::updateImpl(...).
1528  ChangeStatus updateImpl(Attributor &A) override {
1529  // TODO: Once we have call site specific value information we can provide
1530  // call site specific liveness information and then it makes
1531  // sense to specialize attributes for call sites arguments instead of
1532  // redirecting requests to the callee argument.
1533  Argument *Arg = getAssociatedArgument();
1534  if (!Arg)
1535  return indicatePessimisticFixpoint();
1536  const IRPosition &ArgPos = IRPosition::argument(*Arg);
1537  auto &ArgAA = A.getAAFor<AANoFree>(*this, ArgPos);
1538  return clampStateAndIndicateChange(
1539  getState(), static_cast<const AANoFree::StateType &>(ArgAA.getState()));
1540  }
1541 
1542  /// See AbstractAttribute::trackStatistics()
1543  void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)};
1544 };
1545 
1546 /// NoFree attribute for function return value.
1547 struct AANoFreeReturned final : AANoFreeFloating {
1548  AANoFreeReturned(const IRPosition &IRP, Attributor &A)
1549  : AANoFreeFloating(IRP, A) {
1550  llvm_unreachable("NoFree is not applicable to function returns!");
1551  }
1552 
1553  /// See AbstractAttribute::initialize(...).
1554  void initialize(Attributor &A) override {
1555  llvm_unreachable("NoFree is not applicable to function returns!");
1556  }
1557 
1558  /// See AbstractAttribute::updateImpl(...).
1559  ChangeStatus updateImpl(Attributor &A) override {
1560  llvm_unreachable("NoFree is not applicable to function returns!");
1561  }
1562 
1563  /// See AbstractAttribute::trackStatistics()
1564  void trackStatistics() const override {}
1565 };
1566 
1567 /// NoFree attribute deduction for a call site return value.
1568 struct AANoFreeCallSiteReturned final : AANoFreeFloating {
1569  AANoFreeCallSiteReturned(const IRPosition &IRP, Attributor &A)
1570  : AANoFreeFloating(IRP, A) {}
1571 
1572  ChangeStatus manifest(Attributor &A) override {
1573  return ChangeStatus::UNCHANGED;
1574  }
1575  /// See AbstractAttribute::trackStatistics()
1576  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) }
1577 };
1578 
1579 /// ------------------------ NonNull Argument Attribute ------------------------
1580 static int64_t getKnownNonNullAndDerefBytesForUse(
1581  Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue,
1582  const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
1583  TrackUse = false;
1584 
1585  const Value *UseV = U->get();
1586  if (!UseV->getType()->isPointerTy())
1587  return 0;
1588 
1589  Type *PtrTy = UseV->getType();
1590  const Function *F = I->getFunction();
1591  bool NullPointerIsDefined =
1592  F ? llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace()) : true;
1593  const DataLayout &DL = A.getInfoCache().getDL();
1594  if (const auto *CB = dyn_cast<CallBase>(I)) {
1595  if (CB->isBundleOperand(U)) {
1597  U, {Attribute::NonNull, Attribute::Dereferenceable})) {
1598  IsNonNull |=
1599  (RK.AttrKind == Attribute::NonNull || !NullPointerIsDefined);
1600  return RK.ArgValue;
1601  }
1602  return 0;
1603  }
1604 
1605  if (CB->isCallee(U)) {
1606  IsNonNull |= !NullPointerIsDefined;
1607  return 0;
1608  }
1609 
1610  unsigned ArgNo = CB->getArgOperandNo(U);
1611  IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
1612  // As long as we only use known information there is no need to track
1613  // dependences here.
1614  auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP,
1615  /* TrackDependence */ false);
1616  IsNonNull |= DerefAA.isKnownNonNull();
1617  return DerefAA.getKnownDereferenceableBytes();
1618  }
1619 
1620  // We need to follow common pointer manipulation uses to the accesses they
1621  // feed into. We can try to be smart to avoid looking through things we do not
1622  // like for now, e.g., non-inbounds GEPs.
1623  if (isa<CastInst>(I)) {
1624  TrackUse = true;
1625  return 0;
1626  }
1627 
1628  if (isa<GetElementPtrInst>(I)) {
1629  TrackUse = true;
1630  return 0;
1631  }
1632 
1633  int64_t Offset;
1634  const Value *Base =
1635  getMinimalBaseOfAccsesPointerOperand(A, QueryingAA, I, Offset, DL);
1636  if (Base) {
1637  if (Base == &AssociatedValue &&
1638  getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
1639  int64_t DerefBytes =
1640  (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()) + Offset;
1641 
1642  IsNonNull |= !NullPointerIsDefined;
1643  return std::max(int64_t(0), DerefBytes);
1644  }
1645  }
1646 
1647  /// Corner case when an offset is 0.
1648  Base = getBasePointerOfAccessPointerOperand(I, Offset, DL,
1649  /*AllowNonInbounds*/ true);
1650  if (Base) {
1651  if (Offset == 0 && Base == &AssociatedValue &&
1652  getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
1653  int64_t DerefBytes =
1654  (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType());
1655  IsNonNull |= !NullPointerIsDefined;
1656  return std::max(int64_t(0), DerefBytes);
1657  }
1658  }
1659 
1660  return 0;
1661 }
1662 
1663 struct AANonNullImpl : AANonNull {
1664  AANonNullImpl(const IRPosition &IRP, Attributor &A)
1665  : AANonNull(IRP, A),
1666  NullIsDefined(NullPointerIsDefined(
1667  getAnchorScope(),
1668  getAssociatedValue().getType()->getPointerAddressSpace())) {}
1669 
1670  /// See AbstractAttribute::initialize(...).
1671  void initialize(Attributor &A) override {
1672  Value &V = getAssociatedValue();
1673  if (!NullIsDefined &&
1674  hasAttr({Attribute::NonNull, Attribute::Dereferenceable},
1675  /* IgnoreSubsumingPositions */ false, &A))
1676  indicateOptimisticFixpoint();
1677  else if (isa<ConstantPointerNull>(V))
1678  indicatePessimisticFixpoint();
1679  else
1681 
1682  bool CanBeNull = true;
1683  if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull))
1684  if (!CanBeNull)
1685  indicateOptimisticFixpoint();
1686 
1687  if (!getState().isAtFixpoint())
1688  if (Instruction *CtxI = getCtxI())
1689  followUsesInMBEC(*this, A, getState(), *CtxI);
1690  }
1691 
1692  /// See followUsesInMBEC
1693  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
1694  AANonNull::StateType &State) {
1695  bool IsNonNull = false;
1696  bool TrackUse = false;
1697  getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
1698  IsNonNull, TrackUse);
1699  State.setKnown(IsNonNull);
1700  return TrackUse;
1701  }
1702 
1703  /// See AbstractAttribute::getAsStr().
1704  const std::string getAsStr() const override {
1705  return getAssumed() ? "nonnull" : "may-null";
1706  }
1707 
1708  /// Flag to determine if the underlying value can be null and still allow
1709  /// valid accesses.
1710  const bool NullIsDefined;
1711 };
1712 
1713 /// NonNull attribute for a floating value.
1714 struct AANonNullFloating : public AANonNullImpl {
1715  AANonNullFloating(const IRPosition &IRP, Attributor &A)
1716  : AANonNullImpl(IRP, A) {}
1717 
1718  /// See AbstractAttribute::updateImpl(...).
1719  ChangeStatus updateImpl(Attributor &A) override {
1720  if (!NullIsDefined) {
1721  const auto &DerefAA =
1722  A.getAAFor<AADereferenceable>(*this, getIRPosition());
1723  if (DerefAA.getAssumedDereferenceableBytes())
1724  return ChangeStatus::UNCHANGED;
1725  }
1726 
1727  const DataLayout &DL = A.getDataLayout();
1728 
1729  DominatorTree *DT = nullptr;
1730  AssumptionCache *AC = nullptr;
1731  InformationCache &InfoCache = A.getInfoCache();
1732  if (const Function *Fn = getAnchorScope()) {
1734  AC = InfoCache.getAnalysisResultForFunction<AssumptionAnalysis>(*Fn);
1735  }
1736 
1737  auto VisitValueCB = [&](Value &V, const Instruction *CtxI,
1738  AANonNull::StateType &T, bool Stripped) -> bool {
1739  const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V));
1740  if (!Stripped && this == &AA) {
1741  if (!isKnownNonZero(&V, DL, 0, AC, CtxI, DT))
1743  } else {
1744  // Use abstract attribute information.
1745  const AANonNull::StateType &NS =
1746  static_cast<const AANonNull::StateType &>(AA.getState());
1747  T ^= NS;
1748  }
1749  return T.isValidState();
1750  };
1751 
1752  StateType T;
1753  if (!genericValueTraversal<AANonNull, StateType>(
1754  A, getIRPosition(), *this, T, VisitValueCB, getCtxI()))
1755  return indicatePessimisticFixpoint();
1756 
1757  return clampStateAndIndicateChange(getState(), T);
1758  }
1759 
1760  /// See AbstractAttribute::trackStatistics()
1761  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
1762 };
1763 
1764 /// NonNull attribute for function return value.
1765 struct AANonNullReturned final
1766  : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl> {
1767  AANonNullReturned(const IRPosition &IRP, Attributor &A)
1768  : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl>(IRP, A) {}
1769 
1770  /// See AbstractAttribute::trackStatistics()
1771  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
1772 };
1773 
1774 /// NonNull attribute for function argument.
1775 struct AANonNullArgument final
1776  : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
1777  AANonNullArgument(const IRPosition &IRP, Attributor &A)
1778  : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP, A) {}
1779 
1780  /// See AbstractAttribute::trackStatistics()
1781  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
1782 };
1783 
1784 struct AANonNullCallSiteArgument final : AANonNullFloating {
1785  AANonNullCallSiteArgument(const IRPosition &IRP, Attributor &A)
1786  : AANonNullFloating(IRP, A) {}
1787 
1788  /// See AbstractAttribute::trackStatistics()
1789  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) }
1790 };
1791 
1792 /// NonNull attribute for a call site return position.
1793 struct AANonNullCallSiteReturned final
1794  : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl> {
1795  AANonNullCallSiteReturned(const IRPosition &IRP, Attributor &A)
1796  : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl>(IRP, A) {}
1797 
1798  /// See AbstractAttribute::trackStatistics()
1799  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
1800 };
1801 
1802 /// ------------------------ No-Recurse Attributes ----------------------------
1803 
1804 struct AANoRecurseImpl : public AANoRecurse {
1805  AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
1806 
1807  /// See AbstractAttribute::getAsStr()
1808  const std::string getAsStr() const override {
1809  return getAssumed() ? "norecurse" : "may-recurse";
1810  }
1811 };
1812 
1813 struct AANoRecurseFunction final : AANoRecurseImpl {
1814  AANoRecurseFunction(const IRPosition &IRP, Attributor &A)
1815  : AANoRecurseImpl(IRP, A) {}
1816 
1817  /// See AbstractAttribute::initialize(...).
1818  void initialize(Attributor &A) override {
1820  if (const Function *F = getAnchorScope())
1821  if (A.getInfoCache().getSccSize(*F) != 1)
1822  indicatePessimisticFixpoint();
1823  }
1824 
1825  /// See AbstractAttribute::updateImpl(...).
1826  ChangeStatus updateImpl(Attributor &A) override {
1827 
1828  // If all live call sites are known to be no-recurse, we are as well.
1829  auto CallSitePred = [&](AbstractCallSite ACS) {
1830  const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
1831  *this, IRPosition::function(*ACS.getInstruction()->getFunction()),
1832  /* TrackDependence */ false, DepClassTy::OPTIONAL);
1833  return NoRecurseAA.isKnownNoRecurse();
1834  };
1835  bool AllCallSitesKnown;
1836  if (A.checkForAllCallSites(CallSitePred, *this, true, AllCallSitesKnown)) {
1837  // If we know all call sites and all are known no-recurse, we are done.
1838  // If all known call sites, which might not be all that exist, are known
1839  // to be no-recurse, we are not done but we can continue to assume
1840  // no-recurse. If one of the call sites we have not visited will become
1841  // live, another update is triggered.
1842  if (AllCallSitesKnown)
1843  indicateOptimisticFixpoint();
1844  return ChangeStatus::UNCHANGED;
1845  }
1846 
1847  // If the above check does not hold anymore we look at the calls.
1848  auto CheckForNoRecurse = [&](Instruction &I) {
1849  const auto &CB = cast<CallBase>(I);
1850  if (CB.hasFnAttr(Attribute::NoRecurse))
1851  return true;
1852 
1853  const auto &NoRecurseAA =
1855  if (!NoRecurseAA.isAssumedNoRecurse())
1856  return false;
1857 
1858  // Recursion to the same function
1859  if (CB.getCalledFunction() == getAnchorScope())
1860  return false;
1861 
1862  return true;
1863  };
1864 
1865  if (!A.checkForAllCallLikeInstructions(CheckForNoRecurse, *this))
1866  return indicatePessimisticFixpoint();
1867  return ChangeStatus::UNCHANGED;
1868  }
1869 
1870  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
1871 };
1872 
1873 /// NoRecurse attribute deduction for a call sites.
1874 struct AANoRecurseCallSite final : AANoRecurseImpl {
1875  AANoRecurseCallSite(const IRPosition &IRP, Attributor &A)
1876  : AANoRecurseImpl(IRP, A) {}
1877 
1878  /// See AbstractAttribute::initialize(...).
1879  void initialize(Attributor &A) override {
1881  Function *F = getAssociatedFunction();
1882  if (!F)
1883  indicatePessimisticFixpoint();
1884  }
1885 
1886  /// See AbstractAttribute::updateImpl(...).
1887  ChangeStatus updateImpl(Attributor &A) override {
1888  // TODO: Once we have call site specific value information we can provide
1889  // call site specific liveness information and then it makes
1890  // sense to specialize attributes for call sites arguments instead of
1891  // redirecting requests to the callee argument.
1892  Function *F = getAssociatedFunction();
1893  const IRPosition &FnPos = IRPosition::function(*F);
1894  auto &FnAA = A.getAAFor<AANoRecurse>(*this, FnPos);
1895  return clampStateAndIndicateChange(
1896  getState(),
1897  static_cast<const AANoRecurse::StateType &>(FnAA.getState()));
1898  }
1899 
1900  /// See AbstractAttribute::trackStatistics()
1901  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); }
1902 };
1903 
1904 /// -------------------- Undefined-Behavior Attributes ------------------------
1905 
1906 struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior {
1907  AAUndefinedBehaviorImpl(const IRPosition &IRP, Attributor &A)
1908  : AAUndefinedBehavior(IRP, A) {}
1909 
1910  /// See AbstractAttribute::updateImpl(...).
1911  // through a pointer (i.e. also branches etc.)
1912  ChangeStatus updateImpl(Attributor &A) override {
1913  const size_t UBPrevSize = KnownUBInsts.size();
1914  const size_t NoUBPrevSize = AssumedNoUBInsts.size();
1915 
1916  auto InspectMemAccessInstForUB = [&](Instruction &I) {
1917  // Skip instructions that are already saved.
1918  if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
1919  return true;
1920 
1921  // If we reach here, we know we have an instruction
1922  // that accesses memory through a pointer operand,
1923  // for which getPointerOperand() should give it to us.
1924  const Value *PtrOp = getPointerOperand(&I, /* AllowVolatile */ true);
1925  assert(PtrOp &&
1926  "Expected pointer operand of memory accessing instruction");
1927 
1928  // Either we stopped and the appropriate action was taken,
1929  // or we got back a simplified value to continue.
1930  Optional<Value *> SimplifiedPtrOp = stopOnUndefOrAssumed(A, PtrOp, &I);
1931  if (!SimplifiedPtrOp.hasValue())
1932  return true;
1933  const Value *PtrOpVal = SimplifiedPtrOp.getValue();
1934 
1935  // A memory access through a pointer is considered UB
1936  // only if the pointer has constant null value.
1937  // TODO: Expand it to not only check constant values.
1938  if (!isa<ConstantPointerNull>(PtrOpVal)) {
1939  AssumedNoUBInsts.insert(&I);
1940  return true;
1941  }
1942  const Type *PtrTy = PtrOpVal->getType();
1943 
1944  // Because we only consider instructions inside functions,
1945  // assume that a parent function exists.
1946  const Function *F = I.getFunction();
1947 
1948  // A memory access using constant null pointer is only considered UB
1949  // if null pointer is _not_ defined for the target platform.
1951  AssumedNoUBInsts.insert(&I);
1952  else
1953  KnownUBInsts.insert(&I);
1954  return true;
1955  };
1956 
1957  auto InspectBrInstForUB = [&](Instruction &I) {
1958  // A conditional branch instruction is considered UB if it has `undef`
1959  // condition.
1960 
1961  // Skip instructions that are already saved.
1962  if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
1963  return true;
1964 
1965  // We know we have a branch instruction.
1966  auto BrInst = cast<BranchInst>(&I);
1967 
1968  // Unconditional branches are never considered UB.
1969  if (BrInst->isUnconditional())
1970  return true;
1971 
1972  // Either we stopped and the appropriate action was taken,
1973  // or we got back a simplified value to continue.
1974  Optional<Value *> SimplifiedCond =
1975  stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst);
1976  if (!SimplifiedCond.hasValue())
1977  return true;
1978  AssumedNoUBInsts.insert(&I);
1979  return true;
1980  };
1981 
1982  A.checkForAllInstructions(InspectMemAccessInstForUB, *this,
1984  Instruction::AtomicCmpXchg,
1985  Instruction::AtomicRMW},
1986  /* CheckBBLivenessOnly */ true);
1987  A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br},
1988  /* CheckBBLivenessOnly */ true);
1989  if (NoUBPrevSize != AssumedNoUBInsts.size() ||
1990  UBPrevSize != KnownUBInsts.size())
1991  return ChangeStatus::CHANGED;
1992  return ChangeStatus::UNCHANGED;
1993  }
1994 
1995  bool isKnownToCauseUB(Instruction *I) const override {
1996  return KnownUBInsts.count(I);
1997  }
1998 
1999  bool isAssumedToCauseUB(Instruction *I) const override {
2000  // In simple words, if an instruction is not in the assumed to _not_
2001  // cause UB, then it is assumed UB (that includes those
2002  // in the KnownUBInsts set). The rest is boilerplate
2003  // is to ensure that it is one of the instructions we test
2004  // for UB.
2005 
2006  switch (I->getOpcode()) {
2007  case Instruction::Load:
2008  case Instruction::Store:
2009  case Instruction::AtomicCmpXchg:
2010  case Instruction::AtomicRMW:
2011  return !AssumedNoUBInsts.count(I);
2012  case Instruction::Br: {
2013  auto BrInst = cast<BranchInst>(I);
2014  if (BrInst->isUnconditional())
2015  return false;
2016  return !AssumedNoUBInsts.count(I);
2017  } break;
2018  default:
2019  return false;
2020  }
2021  return false;
2022  }
2023 
2024  ChangeStatus manifest(Attributor &A) override {
2025  if (KnownUBInsts.empty())
2026  return ChangeStatus::UNCHANGED;
2027  for (Instruction *I : KnownUBInsts)
2029  return ChangeStatus::CHANGED;
2030  }
2031 
2032  /// See AbstractAttribute::getAsStr()
2033  const std::string getAsStr() const override {
2034  return getAssumed() ? "undefined-behavior" : "no-ub";
2035  }
2036 
2037  /// Note: The correctness of this analysis depends on the fact that the
2038  /// following 2 sets will stop changing after some point.
2039  /// "Change" here means that their size changes.
2040  /// The size of each set is monotonically increasing
2041  /// (we only add items to them) and it is upper bounded by the number of
2042  /// instructions in the processed function (we can never save more
2043  /// elements in either set than this number). Hence, at some point,
2044  /// they will stop increasing.
2045  /// Consequently, at some point, both sets will have stopped
2046  /// changing, effectively making the analysis reach a fixpoint.
2047 
2048  /// Note: These 2 sets are disjoint and an instruction can be considered
2049  /// one of 3 things:
2050  /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in
2051  /// the KnownUBInsts set.
2052  /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior
2053  /// has a reason to assume it).
2054  /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior
2055  /// could not find a reason to assume or prove that it can cause UB,
2056  /// hence it assumes it doesn't. We have a set for these instructions
2057  /// so that we don't reprocess them in every update.
2058  /// Note however that instructions in this set may cause UB.
2059 
2060 protected:
2061  /// A set of all live instructions _known_ to cause UB.
2062  SmallPtrSet<Instruction *, 8> KnownUBInsts;
2063 
2064 private:
2065  /// A set of all the (live) instructions that are assumed to _not_ cause UB.
2066  SmallPtrSet<Instruction *, 8> AssumedNoUBInsts;
2067 
2068  // Should be called on updates in which if we're processing an instruction
2069  // \p I that depends on a value \p V, one of the following has to happen:
2070  // - If the value is assumed, then stop.
2071  // - If the value is known but undef, then consider it UB.
2072  // - Otherwise, do specific processing with the simplified value.
2073  // We return None in the first 2 cases to signify that an appropriate
2074  // action was taken and the caller should stop.
2075  // Otherwise, we return the simplified value that the caller should
2076  // use for specific processing.
2077  Optional<Value *> stopOnUndefOrAssumed(Attributor &A, const Value *V,
2078  Instruction *I) {
2079  const auto &ValueSimplifyAA =
2081  Optional<Value *> SimplifiedV =
2082  ValueSimplifyAA.getAssumedSimplifiedValue(A);
2083  if (!ValueSimplifyAA.isKnown()) {
2084  // Don't depend on assumed values.
2085  return llvm::None;
2086  }
2087  if (!SimplifiedV.hasValue()) {
2088  // If it is known (which we tested above) but it doesn't have a value,
2089  // then we can assume `undef` and hence the instruction is UB.
2090  KnownUBInsts.insert(I);
2091  return llvm::None;
2092  }
2093  Value *Val = SimplifiedV.getValue();
2094  if (isa<UndefValue>(Val)) {
2095  KnownUBInsts.insert(I);
2096  return llvm::None;
2097  }
2098  return Val;
2099  }
2100 };
2101 
2102 struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl {
2103  AAUndefinedBehaviorFunction(const IRPosition &IRP, Attributor &A)
2104  : AAUndefinedBehaviorImpl(IRP, A) {}
2105 
2106  /// See AbstractAttribute::trackStatistics()
2107  void trackStatistics() const override {
2108  STATS_DECL(UndefinedBehaviorInstruction, Instruction,
2109  "Number of instructions known to have UB");
2110  BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) +=
2111  KnownUBInsts.size();
2112  }
2113 };
2114 
2115 /// ------------------------ Will-Return Attributes ----------------------------
2116 
2117 // Helper function that checks whether a function has any cycle which we don't
2118 // know if it is bounded or not.
2119 // Loops with maximum trip count are considered bounded, any other cycle not.
2120 static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
2121  ScalarEvolution *SE =
2124  // If either SCEV or LoopInfo is not available for the function then we assume
2125  // any cycle to be unbounded cycle.
2126  // We use scc_iterator which uses Tarjan algorithm to find all the maximal
2127  // SCCs.To detect if there's a cycle, we only need to find the maximal ones.
2128  if (!SE || !LI) {
2129  for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
2130  if (SCCI.hasCycle())
2131  return true;
2132  return false;
2133  }
2134 
2135  // If there's irreducible control, the function may contain non-loop cycles.
2136  if (mayContainIrreducibleControl(F, LI))
2137  return true;
2138 
2139  // Any loop that does not have a max trip count is considered unbounded cycle.
2140  for (auto *L : LI->getLoopsInPreorder()) {
2141  if (!SE->getSmallConstantMaxTripCount(L))
2142  return true;
2143  }
2144  return false;
2145 }
2146 
2147 struct AAWillReturnImpl : public AAWillReturn {
2148  AAWillReturnImpl(const IRPosition &IRP, Attributor &A)
2149  : AAWillReturn(IRP, A) {}
2150 
2151  /// See AbstractAttribute::initialize(...).
2152  void initialize(Attributor &A) override {
2154 
2155  Function *F = getAnchorScope();
2156  if (!F || !A.isFunctionIPOAmendable(*F) || mayContainUnboundedCycle(*F, A))
2157  indicatePessimisticFixpoint();
2158  }
2159 
2160  /// See AbstractAttribute::updateImpl(...).
2161  ChangeStatus updateImpl(Attributor &A) override {
2162  auto CheckForWillReturn = [&](Instruction &I) {
2163  IRPosition IPos = IRPosition::callsite_function(cast<CallBase>(I));
2164  const auto &WillReturnAA = A.getAAFor<AAWillReturn>(*this, IPos);
2165  if (WillReturnAA.isKnownWillReturn())
2166  return true;
2167  if (!WillReturnAA.isAssumedWillReturn())
2168  return false;
2169  const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(*this, IPos);
2170  return NoRecurseAA.isAssumedNoRecurse();
2171  };
2172 
2173  if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this))
2174  return indicatePessimisticFixpoint();
2175 
2176  return ChangeStatus::UNCHANGED;
2177  }
2178 
2179  /// See AbstractAttribute::getAsStr()
2180  const std::string getAsStr() const override {
2181  return getAssumed() ? "willreturn" : "may-noreturn";
2182  }
2183 };
2184 
2185 struct AAWillReturnFunction final : AAWillReturnImpl {
2186  AAWillReturnFunction(const IRPosition &IRP, Attributor &A)
2187  : AAWillReturnImpl(IRP, A) {}
2188 
2189  /// See AbstractAttribute::trackStatistics()
2190  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
2191 };
2192 
2193 /// WillReturn attribute deduction for a call sites.
2194 struct AAWillReturnCallSite final : AAWillReturnImpl {
2195  AAWillReturnCallSite(const IRPosition &IRP, Attributor &A)
2196  : AAWillReturnImpl(IRP, A) {}
2197 
2198  /// See AbstractAttribute::initialize(...).
2199  void initialize(Attributor &A) override {
2201  Function *F = getAssociatedFunction();
2202  if (!F)
2203  indicatePessimisticFixpoint();
2204  }
2205 
2206  /// See AbstractAttribute::updateImpl(...).
2207  ChangeStatus updateImpl(Attributor &A) override {
2208  // TODO: Once we have call site specific value information we can provide
2209  // call site specific liveness information and then it makes
2210  // sense to specialize attributes for call sites arguments instead of
2211  // redirecting requests to the callee argument.
2212  Function *F = getAssociatedFunction();
2213  const IRPosition &FnPos = IRPosition::function(*F);
2214  auto &FnAA = A.getAAFor<AAWillReturn>(*this, FnPos);
2215  return clampStateAndIndicateChange(
2216  getState(),
2217  static_cast<const AAWillReturn::StateType &>(FnAA.getState()));
2218  }
2219 
2220  /// See AbstractAttribute::trackStatistics()
2221  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
2222 };
2223 
2224 /// -------------------AAReachability Attribute--------------------------
2225 
2226 struct AAReachabilityImpl : AAReachability {
2227  AAReachabilityImpl(const IRPosition &IRP, Attributor &A)
2228  : AAReachability(IRP, A) {}
2229 
2230  const std::string getAsStr() const override {
2231  // TODO: Return the number of reachable queries.
2232  return "reachable";
2233  }
2234 
2235  /// See AbstractAttribute::initialize(...).
2236  void initialize(Attributor &A) override { indicatePessimisticFixpoint(); }
2237 
2238  /// See AbstractAttribute::updateImpl(...).
2239  ChangeStatus updateImpl(Attributor &A) override {
2240  return indicatePessimisticFixpoint();
2241  }
2242 };
2243 
2244 struct AAReachabilityFunction final : public AAReachabilityImpl {
2245  AAReachabilityFunction(const IRPosition &IRP, Attributor &A)
2246  : AAReachabilityImpl(IRP, A) {}
2247 
2248  /// See AbstractAttribute::trackStatistics()
2249  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); }
2250 };
2251 
2252 /// ------------------------ NoAlias Argument Attribute ------------------------
2253 
2254 struct AANoAliasImpl : AANoAlias {
2255  AANoAliasImpl(const IRPosition &IRP, Attributor &A) : AANoAlias(IRP, A) {
2256  assert(getAssociatedType()->isPointerTy() &&
2257  "Noalias is a pointer attribute");
2258  }
2259 
2260  const std::string getAsStr() const override {
2261  return getAssumed() ? "noalias" : "may-alias";
2262  }
2263 };
2264 
2265 /// NoAlias attribute for a floating value.
2266 struct AANoAliasFloating final : AANoAliasImpl {
2267  AANoAliasFloating(const IRPosition &IRP, Attributor &A)
2268  : AANoAliasImpl(IRP, A) {}
2269 
2270  /// See AbstractAttribute::initialize(...).
2271  void initialize(Attributor &A) override {
2273  Value *Val = &getAssociatedValue();
2274  do {
2275  CastInst *CI = dyn_cast<CastInst>(Val);
2276  if (!CI)
2277  break;
2278  Value *Base = CI->getOperand(0);
2279  if (!Base->hasOneUse())
2280  break;
2281  Val = Base;
2282  } while (true);
2283 
2284  if (!Val->getType()->isPointerTy()) {
2285  indicatePessimisticFixpoint();
2286  return;
2287  }
2288 
2289  if (isa<AllocaInst>(Val))
2290  indicateOptimisticFixpoint();
2291  else if (isa<ConstantPointerNull>(Val) &&
2292  !NullPointerIsDefined(getAnchorScope(),
2293  Val->getType()->getPointerAddressSpace()))
2294  indicateOptimisticFixpoint();
2295  else if (Val != &getAssociatedValue()) {
2296  const auto &ValNoAliasAA =
2297  A.getAAFor<AANoAlias>(*this, IRPosition::value(*Val));
2298  if (ValNoAliasAA.isKnownNoAlias())
2299  indicateOptimisticFixpoint();
2300  }
2301  }
2302 
2303  /// See AbstractAttribute::updateImpl(...).
2304  ChangeStatus updateImpl(Attributor &A) override {
2305  // TODO: Implement this.
2306  return indicatePessimisticFixpoint();
2307  }
2308 
2309  /// See AbstractAttribute::trackStatistics()
2310  void trackStatistics() const override {
2312  }
2313 };
2314 
2315 /// NoAlias attribute for an argument.
2316 struct AANoAliasArgument final
2317  : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> {
2318  using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>;
2319  AANoAliasArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
2320 
2321  /// See AbstractAttribute::initialize(...).
2322  void initialize(Attributor &A) override {
2323  Base::initialize(A);
2324  // See callsite argument attribute and callee argument attribute.
2325  if (hasAttr({Attribute::ByVal}))
2326  indicateOptimisticFixpoint();
2327  }
2328 
2329  /// See AbstractAttribute::update(...).
2330  ChangeStatus updateImpl(Attributor &A) override {
2331  // We have to make sure no-alias on the argument does not break
2332  // synchronization when this is a callback argument, see also [1] below.
2333  // If synchronization cannot be affected, we delegate to the base updateImpl
2334  // function, otherwise we give up for now.
2335 
2336  // If the function is no-sync, no-alias cannot break synchronization.
2337  const auto &NoSyncAA = A.getAAFor<AANoSync>(
2338  *this, IRPosition::function_scope(getIRPosition()));
2339  if (NoSyncAA.isAssumedNoSync())
2340  return Base::updateImpl(A);
2341 
2342  // If the argument is read-only, no-alias cannot break synchronization.
2343  const auto &MemBehaviorAA =
2344  A.getAAFor<AAMemoryBehavior>(*this, getIRPosition());
2345  if (MemBehaviorAA.isAssumedReadOnly())
2346  return Base::updateImpl(A);
2347 
2348  // If the argument is never passed through callbacks, no-alias cannot break
2349  // synchronization.
2350  bool AllCallSitesKnown;
2351  if (A.checkForAllCallSites(
2352  [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this,
2353  true, AllCallSitesKnown))
2354  return Base::updateImpl(A);
2355 
2356  // TODO: add no-alias but make sure it doesn't break synchronization by
2357  // introducing fake uses. See:
2358  // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel,
2359  // International Workshop on OpenMP 2018,
2360  // http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
2361 
2362  return indicatePessimisticFixpoint();
2363  }
2364 
2365  /// See AbstractAttribute::trackStatistics()
2366  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
2367 };
2368 
2369 struct AANoAliasCallSiteArgument final : AANoAliasImpl {
2370  AANoAliasCallSiteArgument(const IRPosition &IRP, Attributor &A)
2371  : AANoAliasImpl(IRP, A) {}
2372 
2373  /// See AbstractAttribute::initialize(...).
2374  void initialize(Attributor &A) override {
2375  // See callsite argument attribute and callee argument attribute.
2376  const auto &CB = cast<CallBase>(getAnchorValue());
2377  if (CB.paramHasAttr(getArgNo(), Attribute::NoAlias))
2378  indicateOptimisticFixpoint();
2379  Value &Val = getAssociatedValue();
2380  if (isa<ConstantPointerNull>(Val) &&
2381  !NullPointerIsDefined(getAnchorScope(),
2382  Val.getType()->getPointerAddressSpace()))
2383  indicateOptimisticFixpoint();
2384  }
2385 
2386  /// Determine if the underlying value may alias with the call site argument
2387  /// \p OtherArgNo of \p ICS (= the underlying call site).
2388  bool mayAliasWithArgument(Attributor &A, AAResults *&AAR,
2389  const AAMemoryBehavior &MemBehaviorAA,
2390  const CallBase &CB, unsigned OtherArgNo) {
2391  // We do not need to worry about aliasing with the underlying IRP.
2392  if (this->getArgNo() == (int)OtherArgNo)
2393  return false;
2394 
2395  // If it is not a pointer or pointer vector we do not alias.
2396  const Value *ArgOp = CB.getArgOperand(OtherArgNo);
2397  if (!ArgOp->getType()->isPtrOrPtrVectorTy())
2398  return false;
2399 
2400  auto &CBArgMemBehaviorAA = A.getAAFor<AAMemoryBehavior>(
2401  *this, IRPosition::callsite_argument(CB, OtherArgNo),
2402  /* TrackDependence */ false);
2403 
2404  // If the argument is readnone, there is no read-write aliasing.
2405  if (CBArgMemBehaviorAA.isAssumedReadNone()) {
2406  A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
2407  return false;
2408  }
2409 
2410  // If the argument is readonly and the underlying value is readonly, there
2411  // is no read-write aliasing.
2412  bool IsReadOnly = MemBehaviorAA.isAssumedReadOnly();
2413  if (CBArgMemBehaviorAA.isAssumedReadOnly() && IsReadOnly) {
2414  A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
2415  A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
2416  return false;
2417  }
2418 
2419  // We have to utilize actual alias analysis queries so we need the object.
2420  if (!AAR)
2421  AAR = A.getInfoCache().getAAResultsForFunction(*getAnchorScope());
2422 
2423  // Try to rule it out at the call site.
2424  bool IsAliasing = !AAR || !AAR->isNoAlias(&getAssociatedValue(), ArgOp);
2425  LLVM_DEBUG(dbgs() << "[NoAliasCSArg] Check alias between "
2426  "callsite arguments: "
2427  << getAssociatedValue() << " " << *ArgOp << " => "
2428  << (IsAliasing ? "" : "no-") << "alias \n");
2429 
2430  return IsAliasing;
2431  }
2432 
2433  bool
2434  isKnownNoAliasDueToNoAliasPreservation(Attributor &A, AAResults *&AAR,
2435  const AAMemoryBehavior &MemBehaviorAA,
2436  const AANoAlias &NoAliasAA) {
2437  // We can deduce "noalias" if the following conditions hold.
2438  // (i) Associated value is assumed to be noalias in the definition.
2439  // (ii) Associated value is assumed to be no-capture in all the uses
2440  // possibly executed before this callsite.
2441  // (iii) There is no other pointer argument which could alias with the
2442  // value.
2443 
2444  bool AssociatedValueIsNoAliasAtDef = NoAliasAA.isAssumedNoAlias();
2445  if (!AssociatedValueIsNoAliasAtDef) {
2446  LLVM_DEBUG(dbgs() << "[AANoAlias] " << getAssociatedValue()
2447  << " is not no-alias at the definition\n");
2448  return false;
2449  }
2450 
2451  A.recordDependence(NoAliasAA, *this, DepClassTy::OPTIONAL);
2452 
2453  const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
2454  auto &NoCaptureAA =
2455  A.getAAFor<AANoCapture>(*this, VIRP, /* TrackDependence */ false);
2456  // Check whether the value is captured in the scope using AANoCapture.
2457  // Look at CFG and check only uses possibly executed before this
2458  // callsite.
2459  auto UsePred = [&](const Use &U, bool &Follow) -> bool {
2460  Instruction *UserI = cast<Instruction>(U.getUser());
2461 
2462  // If user if curr instr and only use.
2463  if (UserI == getCtxI() && UserI->hasOneUse())
2464  return true;
2465 
2466  const Function *ScopeFn = VIRP.getAnchorScope();
2467  if (ScopeFn) {
2468  const auto &ReachabilityAA =
2469  A.getAAFor<AAReachability>(*this, IRPosition::function(*ScopeFn));
2470 
2471  if (!ReachabilityAA.isAssumedReachable(UserI, getCtxI()))
2472  return true;
2473 
2474  if (auto *CB = dyn_cast<CallBase>(UserI)) {
2475  if (CB->isArgOperand(&U)) {
2476 
2477  unsigned ArgNo = CB->getArgOperandNo(&U);
2478 
2479  const auto &NoCaptureAA = A.getAAFor<AANoCapture>(
2480  *this, IRPosition::callsite_argument(*CB, ArgNo));
2481 
2482  if (NoCaptureAA.isAssumedNoCapture())
2483  return true;
2484  }
2485  }
2486  }
2487 
2488  // For cases which can potentially have more users
2489  if (isa<GetElementPtrInst>(U) || isa<BitCastInst>(U) || isa<PHINode>(U) ||
2490  isa<SelectInst>(U)) {
2491  Follow = true;
2492  return true;
2493  }
2494 
2495  LLVM_DEBUG(dbgs() << "[AANoAliasCSArg] Unknown user: " << *U << "\n");
2496  return false;
2497  };
2498 
2499  if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
2500  if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) {
2501  LLVM_DEBUG(
2502  dbgs() << "[AANoAliasCSArg] " << getAssociatedValue()
2503  << " cannot be noalias as it is potentially captured\n");
2504  return false;
2505  }
2506  }
2507  A.recordDependence(NoCaptureAA, *this, DepClassTy::OPTIONAL);
2508 
2509  // Check there is no other pointer argument which could alias with the
2510  // value passed at this call site.
2511  // TODO: AbstractCallSite
2512  const auto &CB = cast<CallBase>(getAnchorValue());
2513  for (unsigned OtherArgNo = 0; OtherArgNo < CB.getNumArgOperands();
2514  OtherArgNo++)
2515  if (mayAliasWithArgument(A, AAR, MemBehaviorAA, CB, OtherArgNo))
2516  return false;
2517 
2518  return true;
2519  }
2520 
2521  /// See AbstractAttribute::updateImpl(...).
2522  ChangeStatus updateImpl(Attributor &A) override {
2523  // If the argument is readnone we are done as there are no accesses via the
2524  // argument.
2525  auto &MemBehaviorAA =
2526  A.getAAFor<AAMemoryBehavior>(*this, getIRPosition(),
2527  /* TrackDependence */ false);
2528  if (MemBehaviorAA.isAssumedReadNone()) {
2529  A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
2530  return ChangeStatus::UNCHANGED;
2531  }
2532 
2533  const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
2534  const auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, VIRP,
2535  /* TrackDependence */ false);
2536 
2537  AAResults *AAR = nullptr;
2538  if (isKnownNoAliasDueToNoAliasPreservation(A, AAR, MemBehaviorAA,
2539  NoAliasAA)) {
2540  LLVM_DEBUG(
2541  dbgs() << "[AANoAlias] No-Alias deduced via no-alias preservation\n");
2542  return ChangeStatus::UNCHANGED;
2543  }
2544 
2545  return indicatePessimisticFixpoint();
2546  }
2547 
2548  /// See AbstractAttribute::trackStatistics()
2549  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) }
2550 };
2551 
2552 /// NoAlias attribute for function return value.
2553 struct AANoAliasReturned final : AANoAliasImpl {
2554  AANoAliasReturned(const IRPosition &IRP, Attributor &A)
2555  : AANoAliasImpl(IRP, A) {}
2556 
2557  /// See AbstractAttribute::updateImpl(...).
2558  virtual ChangeStatus updateImpl(Attributor &A) override {
2559 
2560  auto CheckReturnValue = [&](Value &RV) -> bool {
2561  if (Constant *C = dyn_cast<Constant>(&RV))
2562  if (C->isNullValue() || isa<UndefValue>(C))
2563  return true;
2564 
2565  /// For now, we can only deduce noalias if we have call sites.
2566  /// FIXME: add more support.
2567  if (!isa<CallBase>(&RV))
2568  return false;
2569 
2570  const IRPosition &RVPos = IRPosition::value(RV);
2571  const auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, RVPos);
2572  if (!NoAliasAA.isAssumedNoAlias())
2573  return false;
2574 
2575  const auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, RVPos);
2576  return NoCaptureAA.isAssumedNoCaptureMaybeReturned();
2577  };
2578 
2579  if (!A.checkForAllReturnedValues(CheckReturnValue, *this))
2580  return indicatePessimisticFixpoint();
2581 
2582  return ChangeStatus::UNCHANGED;
2583  }
2584 
2585  /// See AbstractAttribute::trackStatistics()
2586  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) }
2587 };
2588 
2589 /// NoAlias attribute deduction for a call site return value.
2590 struct AANoAliasCallSiteReturned final : AANoAliasImpl {
2591  AANoAliasCallSiteReturned(const IRPosition &IRP, Attributor &A)
2592  : AANoAliasImpl(IRP, A) {}
2593 
2594  /// See AbstractAttribute::initialize(...).
2595  void initialize(Attributor &A) override {
2597  Function *F = getAssociatedFunction();
2598  if (!F)
2599  indicatePessimisticFixpoint();
2600  }
2601 
2602  /// See AbstractAttribute::updateImpl(...).
2603  ChangeStatus updateImpl(Attributor &A) override {
2604  // TODO: Once we have call site specific value information we can provide
2605  // call site specific liveness information and then it makes
2606  // sense to specialize attributes for call sites arguments instead of
2607  // redirecting requests to the callee argument.
2608  Function *F = getAssociatedFunction();
2609  const IRPosition &FnPos = IRPosition::returned(*F);
2610  auto &FnAA = A.getAAFor<AANoAlias>(*this, FnPos);
2611  return clampStateAndIndicateChange(
2612  getState(), static_cast<const AANoAlias::StateType &>(FnAA.getState()));
2613  }
2614 
2615  /// See AbstractAttribute::trackStatistics()
2616  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); }
2617 };
2618 
2619 /// -------------------AAIsDead Function Attribute-----------------------
2620 
2621 struct AAIsDeadValueImpl : public AAIsDead {
2622  AAIsDeadValueImpl(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
2623 
2624  /// See AAIsDead::isAssumedDead().
2625  bool isAssumedDead() const override { return getAssumed(); }
2626 
2627  /// See AAIsDead::isKnownDead().
2628  bool isKnownDead() const override { return getKnown(); }
2629 
2630  /// See AAIsDead::isAssumedDead(BasicBlock *).
2631  bool isAssumedDead(const BasicBlock *BB) const override { return false; }
2632 
2633  /// See AAIsDead::isKnownDead(BasicBlock *).
2634  bool isKnownDead(const BasicBlock *BB) const override { return false; }
2635 
2636  /// See AAIsDead::isAssumedDead(Instruction *I).
2637  bool isAssumedDead(const Instruction *I) const override {
2638  return I == getCtxI() && isAssumedDead();
2639  }
2640 
2641  /// See AAIsDead::isKnownDead(Instruction *I).
2642  bool isKnownDead(const Instruction *I) const override {
2643  return isAssumedDead(I) && getKnown();
2644  }
2645 
2646  /// See AbstractAttribute::getAsStr().
2647  const std::string getAsStr() const override {
2648  return isAssumedDead() ? "assumed-dead" : "assumed-live";
2649  }
2650 
2651  /// Check if all uses are assumed dead.
2652  bool areAllUsesAssumedDead(Attributor &A, Value &V) {
2653  auto UsePred = [&](const Use &U, bool &Follow) { return false; };
2654  // Explicitly set the dependence class to required because we want a long
2655  // chain of N dependent instructions to be considered live as soon as one is
2656  // without going through N update cycles. This is not required for
2657  // correctness.
2658  return A.checkForAllUses(UsePred, *this, V, DepClassTy::REQUIRED);
2659  }
2660 
2661  /// Determine if \p I is assumed to be side-effect free.
2662  bool isAssumedSideEffectFree(Attributor &A, Instruction *I) {
2663  if (!I || wouldInstructionBeTriviallyDead(I))
2664  return true;
2665 
2666  auto *CB = dyn_cast<CallBase>(I);
2667  if (!CB || isa<IntrinsicInst>(CB))
2668  return false;
2669 
2670  const IRPosition &CallIRP = IRPosition::callsite_function(*CB);
2671  const auto &NoUnwindAA = A.getAndUpdateAAFor<AANoUnwind>(
2672  *this, CallIRP, /* TrackDependence */ false);
2673  if (!NoUnwindAA.isAssumedNoUnwind())
2674  return false;
2675  if (!NoUnwindAA.isKnownNoUnwind())
2676  A.recordDependence(NoUnwindAA, *this, DepClassTy::OPTIONAL);
2677 
2678  const auto &MemBehaviorAA = A.getAndUpdateAAFor<AAMemoryBehavior>(
2679  *this, CallIRP, /* TrackDependence */ false);
2680  if (MemBehaviorAA.isAssumedReadOnly()) {
2681  if (!MemBehaviorAA.isKnownReadOnly())
2682  A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
2683  return true;
2684  }
2685  return false;
2686  }
2687 };
2688 
2689 struct AAIsDeadFloating : public AAIsDeadValueImpl {
2690  AAIsDeadFloating(const IRPosition &IRP, Attributor &A)
2691  : AAIsDeadValueImpl(IRP, A) {}
2692 
2693  /// See AbstractAttribute::initialize(...).
2694  void initialize(Attributor &A) override {
2695  if (isa<UndefValue>(getAssociatedValue())) {
2696  indicatePessimisticFixpoint();
2697  return;
2698  }
2699 
2700  Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
2701  if (!isAssumedSideEffectFree(A, I))
2702  indicatePessimisticFixpoint();
2703  }
2704 
2705  /// See AbstractAttribute::updateImpl(...).
2706  ChangeStatus updateImpl(Attributor &A) override {
2707  Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
2708  if (!isAssumedSideEffectFree(A, I))
2709  return indicatePessimisticFixpoint();
2710 
2711  if (!areAllUsesAssumedDead(A, getAssociatedValue()))
2712  return indicatePessimisticFixpoint();
2713  return ChangeStatus::UNCHANGED;
2714  }
2715 
2716  /// See AbstractAttribute::manifest(...).
2717  ChangeStatus manifest(Attributor &A) override {
2718  Value &V = getAssociatedValue();
2719  if (auto *I = dyn_cast<Instruction>(&V)) {
2720  // If we get here we basically know the users are all dead. We check if
2721  // isAssumedSideEffectFree returns true here again because it might not be
2722  // the case and only the users are dead but the instruction (=call) is
2723  // still needed.
2724  if (isAssumedSideEffectFree(A, I) && !isa<InvokeInst>(I)) {
2725  A.deleteAfterManifest(*I);
2726  return ChangeStatus::CHANGED;
2727  }
2728  }
2729  if (V.use_empty())
2730  return ChangeStatus::UNCHANGED;
2731 
2732  bool UsedAssumedInformation = false;
2734  A.getAssumedConstant(V, *this, UsedAssumedInformation);
2735  if (C.hasValue() && C.getValue())
2736  return ChangeStatus::UNCHANGED;
2737 
2738  // Replace the value with undef as it is dead but keep droppable uses around
2739  // as they provide information we don't want to give up on just yet.
2740  UndefValue &UV = *UndefValue::get(V.getType());
2741  bool AnyChange =
2742  A.changeValueAfterManifest(V, UV, /* ChangeDropppable */ false);
2743  return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
2744  }
2745 
2746  /// See AbstractAttribute::trackStatistics()
2747  void trackStatistics() const override {
2749  }
2750 };
2751 
2752 struct AAIsDeadArgument : public AAIsDeadFloating {
2753  AAIsDeadArgument(const IRPosition &IRP, Attributor &A)
2754  : AAIsDeadFloating(IRP, A) {}
2755 
2756  /// See AbstractAttribute::initialize(...).
2757  void initialize(Attributor &A) override {
2758  if (!A.isFunctionIPOAmendable(*getAnchorScope()))
2759  indicatePessimisticFixpoint();
2760  }
2761 
2762  /// See AbstractAttribute::manifest(...).
2763  ChangeStatus manifest(Attributor &A) override {
2764  ChangeStatus Changed = AAIsDeadFloating::manifest(A);
2765  Argument &Arg = *getAssociatedArgument();
2766  if (A.isValidFunctionSignatureRewrite(Arg, /* ReplacementTypes */ {}))
2768  Arg, /* ReplacementTypes */ {},
2771  Arg.dropDroppableUses();
2772  return ChangeStatus::CHANGED;
2773  }
2774  return Changed;
2775  }
2776 
2777  /// See AbstractAttribute::trackStatistics()
2778  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) }
2779 };
2780 
2781 struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl {
2782  AAIsDeadCallSiteArgument(const IRPosition &IRP, Attributor &A)
2783  : AAIsDeadValueImpl(IRP, A) {}
2784 
2785  /// See AbstractAttribute::initialize(...).
2786  void initialize(Attributor &A) override {
2787  if (isa<UndefValue>(getAssociatedValue()))
2788  indicatePessimisticFixpoint();
2789  }
2790 
2791  /// See AbstractAttribute::updateImpl(...).
2792  ChangeStatus updateImpl(Attributor &A) override {
2793  // TODO: Once we have call site specific value information we can provide
2794  // call site specific liveness information and then it makes
2795  // sense to specialize attributes for call sites arguments instead of
2796  // redirecting requests to the callee argument.
2797  Argument *Arg = getAssociatedArgument();
2798  if (!Arg)
2799  return indicatePessimisticFixpoint();
2800  const IRPosition &ArgPos = IRPosition::argument(*Arg);
2801  auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos);
2802  return clampStateAndIndicateChange(
2803  getState(), static_cast<const AAIsDead::StateType &>(ArgAA.getState()));
2804  }
2805 
2806  /// See AbstractAttribute::manifest(...).
2807  ChangeStatus manifest(Attributor &A) override {
2808  CallBase &CB = cast<CallBase>(getAnchorValue());
2809  Use &U = CB.getArgOperandUse(getArgNo());
2810  assert(!isa<UndefValue>(U.get()) &&
2811  "Expected undef values to be filtered out!");
2812  UndefValue &UV = *UndefValue::get(U->getType());
2813  if (A.changeUseAfterManifest(U, UV))
2814  return ChangeStatus::CHANGED;
2815  return ChangeStatus::UNCHANGED;
2816  }
2817 
2818  /// See AbstractAttribute::trackStatistics()
2819  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) }
2820 };
2821 
2822 struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
2823  AAIsDeadCallSiteReturned(const IRPosition &IRP, Attributor &A)
2824  : AAIsDeadFloating(IRP, A), IsAssumedSideEffectFree(true) {}
2825 
2826  /// See AAIsDead::isAssumedDead().
2827  bool isAssumedDead() const override {
2828  return AAIsDeadFloating::isAssumedDead() && IsAssumedSideEffectFree;
2829  }
2830 
2831  /// See AbstractAttribute::initialize(...).
2832  void initialize(Attributor &A) override {
2833  if (isa<UndefValue>(getAssociatedValue())) {
2834  indicatePessimisticFixpoint();
2835  return;
2836  }
2837 
2838  // We track this separately as a secondary state.
2839  IsAssumedSideEffectFree = isAssumedSideEffectFree(A, getCtxI());
2840  }
2841 
2842  /// See AbstractAttribute::updateImpl(...).
2843  ChangeStatus updateImpl(Attributor &A) override {
2845  if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, getCtxI())) {
2846  IsAssumedSideEffectFree = false;
2847  Changed = ChangeStatus::CHANGED;
2848  }
2849 
2850  if (!areAllUsesAssumedDead(A, getAssociatedValue()))
2851  return indicatePessimisticFixpoint();
2852  return Changed;
2853  }
2854 
2855  /// See AbstractAttribute::trackStatistics()
2856  void trackStatistics() const override {
2857  if (IsAssumedSideEffectFree)
2859  else
2860  STATS_DECLTRACK_CSRET_ATTR(UnusedResult)
2861  }
2862 
2863  /// See AbstractAttribute::getAsStr().
2864  const std::string getAsStr() const override {
2865  return isAssumedDead()
2866  ? "assumed-dead"
2867  : (getAssumed() ? "assumed-dead-users" : "assumed-live");
2868  }
2869 
2870 private:
2871  bool IsAssumedSideEffectFree;
2872 };
2873 
2874 struct AAIsDeadReturned : public AAIsDeadValueImpl {
2875  AAIsDeadReturned(const IRPosition &IRP, Attributor &A)
2876  : AAIsDeadValueImpl(IRP, A) {}
2877 
2878  /// See AbstractAttribute::updateImpl(...).
2879  ChangeStatus updateImpl(Attributor &A) override {
2880 
2881  A.checkForAllInstructions([](Instruction &) { return true; }, *this,
2882  {Instruction::Ret});
2883 
2884  auto PredForCallSite = [&](AbstractCallSite ACS) {
2885  if (ACS.isCallbackCall() || !ACS.getInstruction())
2886  return false;
2887  return areAllUsesAssumedDead(A, *ACS.getInstruction());
2888  };
2889 
2890  bool AllCallSitesKnown;
2891  if (!A.checkForAllCallSites(PredForCallSite, *this, true,
2892  AllCallSitesKnown))
2893  return indicatePessimisticFixpoint();
2894 
2895  return ChangeStatus::UNCHANGED;
2896  }
2897 
2898  /// See AbstractAttribute::manifest(...).
2899  ChangeStatus manifest(Attributor &A) override {
2900  // TODO: Rewrite the signature to return void?
2901  bool AnyChange = false;
2902  UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType());
2903  auto RetInstPred = [&](Instruction &I) {
2904  ReturnInst &RI = cast<ReturnInst>(I);
2905  if (!isa<UndefValue>(RI.getReturnValue()))
2906  AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV);
2907  return true;
2908  };
2909  A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret});
2910  return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
2911  }
2912 
2913  /// See AbstractAttribute::trackStatistics()
2914  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) }
2915 };
2916 
2917 struct AAIsDeadFunction : public AAIsDead {
2918  AAIsDeadFunction(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
2919 
2920  /// See AbstractAttribute::initialize(...).
2921  void initialize(Attributor &A) override {
2922  const Function *F = getAnchorScope();
2923  if (F && !F->isDeclaration()) {
2924  ToBeExploredFrom.insert(&F->getEntryBlock().front());
2925  assumeLive(A, F->getEntryBlock());
2926  }
2927  }
2928 
2929  /// See AbstractAttribute::getAsStr().
2930  const std::string getAsStr() const override {
2931  return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
2932  std::to_string(getAnchorScope()->size()) + "][#TBEP " +
2933  std::to_string(ToBeExploredFrom.size()) + "][#KDE " +
2934  std::to_string(KnownDeadEnds.size()) + "]";
2935  }
2936 
2937  /// See AbstractAttribute::manifest(...).
2938  ChangeStatus manifest(Attributor &A) override {
2939  assert(getState().isValidState() &&
2940  "Attempted to manifest an invalid state!");
2941 
2943  Function &F = *getAnchorScope();
2944 
2945  if (AssumedLiveBlocks.empty()) {
2946  A.deleteAfterManifest(F);
2947  return ChangeStatus::CHANGED;
2948  }
2949 
2950  // Flag to determine if we can change an invoke to a call assuming the
2951  // callee is nounwind. This is not possible if the personality of the
2952  // function allows to catch asynchronous exceptions.
2953  bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
2954 
2955  KnownDeadEnds.set_union(ToBeExploredFrom);
2956  for (const Instruction *DeadEndI : KnownDeadEnds) {
2957  auto *CB = dyn_cast<CallBase>(DeadEndI);
2958  if (!CB)
2959  continue;
2960  const auto &NoReturnAA = A.getAndUpdateAAFor<AANoReturn>(
2961  *this, IRPosition::callsite_function(*CB), /* TrackDependence */ true,
2963  bool MayReturn = !NoReturnAA.isAssumedNoReturn();
2964  if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB)))
2965  continue;
2966 
2967  if (auto *II = dyn_cast<InvokeInst>(DeadEndI))
2968  A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II));
2969  else
2971  const_cast<Instruction *>(DeadEndI->getNextNode()));
2972  HasChanged = ChangeStatus::CHANGED;
2973  }
2974 
2975  STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted.");
2976  for (BasicBlock &BB : F)
2977  if (!AssumedLiveBlocks.count(&BB)) {
2978  A.deleteAfterManifest(BB);
2980  }
2981 
2982  return HasChanged;
2983  }
2984 
2985  /// See AbstractAttribute::updateImpl(...).
2986  ChangeStatus updateImpl(Attributor &A) override;
2987 
2988  /// See AbstractAttribute::trackStatistics()
2989  void trackStatistics() const override {}
2990 
2991  /// Returns true if the function is assumed dead.
2992  bool isAssumedDead() const override { return false; }
2993 
2994  /// See AAIsDead::isKnownDead().
2995  bool isKnownDead() const override { return false; }
2996 
2997  /// See AAIsDead::isAssumedDead(BasicBlock *).
2998  bool isAssumedDead(const BasicBlock *BB) const override {
2999  assert(BB->getParent() == getAnchorScope() &&
3000  "BB must be in the same anchor scope function.");
3001 
3002  if (!getAssumed())
3003  return false;
3004  return !AssumedLiveBlocks.count(BB);
3005  }
3006 
3007  /// See AAIsDead::isKnownDead(BasicBlock *).
3008  bool isKnownDead(const BasicBlock *BB) const override {
3009  return getKnown() && isAssumedDead(BB);
3010  }
3011 
3012  /// See AAIsDead::isAssumed(Instruction *I).
3013  bool isAssumedDead(const Instruction *I) const override {
3014  assert(I->getParent()->getParent() == getAnchorScope() &&
3015  "Instruction must be in the same anchor scope function.");
3016 
3017  if (!getAssumed())
3018  return false;
3019 
3020  // If it is not in AssumedLiveBlocks then it for sure dead.
3021  // Otherwise, it can still be after noreturn call in a live block.
3022  if (!AssumedLiveBlocks.count(I->getParent()))
3023  return true;
3024 
3025  // If it is not after a liveness barrier it is live.
3026  const Instruction *PrevI = I->getPrevNode();
3027  while (PrevI) {
3028  if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI))
3029  return true;
3030  PrevI = PrevI->getPrevNode();
3031  }
3032  return false;
3033  }
3034 
3035  /// See AAIsDead::isKnownDead(Instruction *I).
3036  bool isKnownDead(const Instruction *I) const override {
3037  return getKnown() && isAssumedDead(I);
3038  }
3039 
3040  /// Assume \p BB is (partially) live now and indicate to the Attributor \p A
3041  /// that internal function called from \p BB should now be looked at.
3042  bool assumeLive(Attributor &A, const BasicBlock &BB) {
3043  if (!AssumedLiveBlocks.insert(&BB).second)
3044  return false;
3045 
3046  // We assume that all of BB is (probably) live now and if there are calls to
3047  // internal functions we will assume that those are now live as well. This
3048  // is a performance optimization for blocks with calls to a lot of internal
3049  // functions. It can however cause dead functions to be treated as live.
3050  for (const Instruction &I : BB)
3051  if (const auto *CB = dyn_cast<CallBase>(&I))
3052  if (const Function *F = CB->getCalledFunction())
3053  if (F->hasLocalLinkage())
3055  return true;
3056  }
3057 
3058  /// Collection of instructions that need to be explored again, e.g., we
3059  /// did assume they do not transfer control to (one of their) successors.
3060  SmallSetVector<const Instruction *, 8> ToBeExploredFrom;
3061 
3062  /// Collection of instructions that are known to not transfer control.
3064 
3065  /// Collection of all assumed live BasicBlocks.
3066  DenseSet<const BasicBlock *> AssumedLiveBlocks;
3067 };
3068 
3069 static bool
3070 identifyAliveSuccessors(Attributor &A, const CallBase &CB,
3071  AbstractAttribute &AA,
3072  SmallVectorImpl<const Instruction *> &AliveSuccessors) {
3073  const IRPosition &IPos = IRPosition::callsite_function(CB);
3074 
3075  const auto &NoReturnAA = A.getAndUpdateAAFor<AANoReturn>(
3076  AA, IPos, /* TrackDependence */ true, DepClassTy::OPTIONAL);
3077  if (NoReturnAA.isAssumedNoReturn())
3078  return !NoReturnAA.isKnownNoReturn();
3079  if (CB.isTerminator())
3080  AliveSuccessors.push_back(&CB.getSuccessor(0)->front());
3081  else
3082  AliveSuccessors.push_back(CB.getNextNode());
3083  return false;
3084 }
3085 
3086 static bool
3087 identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
3088  AbstractAttribute &AA,
3089  SmallVectorImpl<const Instruction *> &AliveSuccessors) {
3090  bool UsedAssumedInformation =
3091  identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors);
3092 
3093  // First, determine if we can change an invoke to a call assuming the
3094  // callee is nounwind. This is not possible if the personality of the
3095  // function allows to catch asynchronous exceptions.
3096  if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) {
3097  AliveSuccessors.push_back(&II.getUnwindDest()->front());
3098  } else {
3099  const IRPosition &IPos = IRPosition::callsite_function(II);
3100  const auto &AANoUnw = A.getAndUpdateAAFor<AANoUnwind>(
3101  AA, IPos, /* TrackDependence */ true, DepClassTy::OPTIONAL);
3102  if (AANoUnw.isAssumedNoUnwind()) {
3103  UsedAssumedInformation |= !AANoUnw.isKnownNoUnwind();
3104  } else {
3105  AliveSuccessors.push_back(&II.getUnwindDest()->front());
3106  }
3107  }
3108  return UsedAssumedInformation;
3109 }
3110 
3111 static bool
3112 identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
3113  AbstractAttribute &AA,
3114  SmallVectorImpl<const Instruction *> &AliveSuccessors) {
3115  bool UsedAssumedInformation = false;
3116  if (BI.getNumSuccessors() == 1) {
3117  AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
3118  } else {
3119  Optional<ConstantInt *> CI = getAssumedConstantInt(
3120  A, *BI.getCondition(), AA, UsedAssumedInformation);
3121  if (!CI.hasValue()) {
3122  // No value yet, assume both edges are dead.
3123  } else if (CI.getValue()) {
3124  const BasicBlock *SuccBB =
3125  BI.getSuccessor(1 - CI.getValue()->getZExtValue());
3126  AliveSuccessors.push_back(&SuccBB->front());
3127  } else {
3128  AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
3129  AliveSuccessors.push_back(&BI.getSuccessor(1)->front());
3130  UsedAssumedInformation = false;
3131  }
3132  }
3133  return UsedAssumedInformation;
3134 }
3135 
3136 static bool
3137 identifyAliveSuccessors(Attributor &A, const SwitchInst &SI,
3138  AbstractAttribute &AA,
3139  SmallVectorImpl<const Instruction *> &AliveSuccessors) {
3140  bool UsedAssumedInformation = false;
3142  getAssumedConstantInt(A, *SI.getCondition(), AA, UsedAssumedInformation);
3143  if (!CI.hasValue()) {
3144  // No value yet, assume all edges are dead.
3145  } else if (CI.getValue()) {
3146  for (auto &CaseIt : SI.cases()) {
3147  if (CaseIt.getCaseValue() == CI.getValue()) {
3148  AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
3149  return UsedAssumedInformation;
3150  }
3151  }
3152  AliveSuccessors.push_back(&SI.getDefaultDest()->front());
3153  return UsedAssumedInformation;
3154  } else {
3155  for (const BasicBlock *SuccBB : successors(SI.getParent()))
3156  AliveSuccessors.push_back(&SuccBB->front());
3157  }
3158  return UsedAssumedInformation;
3159 }
3160 
3161 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
3163 
3164  LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/"
3165  << getAnchorScope()->size() << "] BBs and "
3166  << ToBeExploredFrom.size() << " exploration points and "
3167  << KnownDeadEnds.size() << " known dead ends\n");
3168 
3169  // Copy and clear the list of instructions we need to explore from. It is
3170  // refilled with instructions the next update has to look at.
3171  SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(),
3172  ToBeExploredFrom.end());
3173  decltype(ToBeExploredFrom) NewToBeExploredFrom;
3174 
3175  SmallVector<const Instruction *, 8> AliveSuccessors;
3176  while (!Worklist.empty()) {
3177  const Instruction *I = Worklist.pop_back_val();
3178  LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n");
3179 
3180  AliveSuccessors.clear();
3181 
3182  bool UsedAssumedInformation = false;
3183  switch (I->getOpcode()) {
3184  // TODO: look for (assumed) UB to backwards propagate "deadness".
3185  default:
3186  if (I->isTerminator()) {
3187  for (const BasicBlock *SuccBB : successors(I->getParent()))
3188  AliveSuccessors.push_back(&SuccBB->front());
3189  } else {
3190  AliveSuccessors.push_back(I->getNextNode());
3191  }
3192  break;
3193  case Instruction::Call:
3194  UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I),
3195  *this, AliveSuccessors);
3196  break;
3197  case Instruction::Invoke:
3198  UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I),
3199  *this, AliveSuccessors);
3200  break;
3201  case Instruction::Br:
3202  UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I),
3203  *this, AliveSuccessors);
3204  break;
3205  case Instruction::Switch:
3206  UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I),
3207  *this, AliveSuccessors);
3208  break;
3209  }
3210 
3211  if (UsedAssumedInformation) {
3212  NewToBeExploredFrom.insert(I);
3213  } else {
3214  Change = ChangeStatus::CHANGED;
3215  if (AliveSuccessors.empty() ||
3216  (I->isTerminator() && AliveSuccessors.size() < I->getNumSuccessors()))
3217  KnownDeadEnds.insert(I);
3218  }
3219 
3220  LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: "
3221  << AliveSuccessors.size() << " UsedAssumedInformation: "
3222  << UsedAssumedInformation << "\n");
3223 
3224  for (const Instruction *AliveSuccessor : AliveSuccessors) {
3225  if (!I->isTerminator()) {
3226  assert(AliveSuccessors.size() == 1 &&
3227  "Non-terminator expected to have a single successor!");
3228  Worklist.push_back(AliveSuccessor);
3229  } else {
3230  if (assumeLive(A, *AliveSuccessor->getParent()))
3231  Worklist.push_back(AliveSuccessor);
3232  }
3233  }
3234  }
3235 
3236  ToBeExploredFrom = std::move(NewToBeExploredFrom);
3237 
3238  // If we know everything is live there is no need to query for liveness.
3239  // Instead, indicating a pessimistic fixpoint will cause the state to be
3240  // "invalid" and all queries to be answered conservatively without lookups.
3241  // To be in this state we have to (1) finished the exploration and (3) not
3242  // discovered any non-trivial dead end and (2) not ruled unreachable code
3243  // dead.
3244  if (ToBeExploredFrom.empty() &&
3245  getAnchorScope()->size() == AssumedLiveBlocks.size() &&
3246  llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) {
3247  return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0;
3248  }))
3249  return indicatePessimisticFixpoint();
3250  return Change;
3251 }
3252 
3253 /// Liveness information for a call sites.
3254 struct AAIsDeadCallSite final : AAIsDeadFunction {
3255  AAIsDeadCallSite(const IRPosition &IRP, Attributor &A)
3256  : AAIsDeadFunction(IRP, A) {}
3257 
3258  /// See AbstractAttribute::initialize(...).
3259  void initialize(Attributor &A) override {
3260  // TODO: Once we have call site specific value information we can provide
3261  // call site specific liveness information and then it makes
3262  // sense to specialize attributes for call sites instead of
3263  // redirecting requests to the callee.
3264  llvm_unreachable("Abstract attributes for liveness are not "
3265  "supported for call sites yet!");
3266  }
3267 
3268  /// See AbstractAttribute::updateImpl(...).
3269  ChangeStatus updateImpl(Attributor &A) override {
3270  return indicatePessimisticFixpoint();
3271  }
3272 
3273  /// See AbstractAttribute::trackStatistics()
3274  void trackStatistics() const override {}
3275 };
3276 
3277 /// -------------------- Dereferenceable Argument Attribute --------------------
3278 
3279 template <>
3280 ChangeStatus clampStateAndIndicateChange<DerefState>(DerefState &S,
3281  const DerefState &R) {
3282  ChangeStatus CS0 =
3283  clampStateAndIndicateChange(S.DerefBytesState, R.DerefBytesState);
3284  ChangeStatus CS1 = clampStateAndIndicateChange(S.GlobalState, R.GlobalState);
3285  return CS0 | CS1;
3286 }
3287 
3288 struct AADereferenceableImpl : AADereferenceable {
3289  AADereferenceableImpl(const IRPosition &IRP, Attributor &A)
3290  : AADereferenceable(IRP, A) {}
3291  using StateType = DerefState;
3292 
3293  /// See AbstractAttribute::initialize(...).
3294  void initialize(Attributor &A) override {
3296  getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
3297  Attrs, /* IgnoreSubsumingPositions */ false, &A);
3298  for (const Attribute &Attr : Attrs)
3299  takeKnownDerefBytesMaximum(Attr.getValueAsInt());
3300 
3301  const IRPosition &IRP = this->getIRPosition();
3302  NonNullAA = &A.getAAFor<AANonNull>(*this, IRP,
3303  /* TrackDependence */ false);
3304 
3305  bool CanBeNull;
3306  takeKnownDerefBytesMaximum(
3308  A.getDataLayout(), CanBeNull));
3309 
3310  bool IsFnInterface = IRP.isFnInterfaceKind();
3311  Function *FnScope = IRP.getAnchorScope();
3312  if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope))) {
3313  indicatePessimisticFixpoint();
3314  return;
3315  }
3316 
3317  if (Instruction *CtxI = getCtxI())
3318  followUsesInMBEC(*this, A, getState(), *CtxI);
3319  }
3320 
3321  /// See AbstractAttribute::getState()
3322  /// {
3323  StateType &getState() override { return *this; }
3324  const StateType &getState() const override { return *this; }
3325  /// }
3326 
3327  /// Helper function for collecting accessed bytes in must-be-executed-context
3328  void addAccessedBytesForUse(Attributor &A, const Use *U, const Instruction *I,
3329  DerefState &State) {
3330  const Value *UseV = U->get();
3331  if (!UseV->getType()->isPointerTy())
3332  return;
3333 
3334  Type *PtrTy = UseV->getType();
3335  const DataLayout &DL = A.getDataLayout();
3336  int64_t Offset;
3337  if (const Value *Base = getBasePointerOfAccessPointerOperand(
3338  I, Offset, DL, /*AllowNonInbounds*/ true)) {
3339  if (Base == &getAssociatedValue() &&
3340  getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
3341  uint64_t Size = DL.getTypeStoreSize(PtrTy->getPointerElementType());
3342  State.addAccessedBytes(Offset, Size);
3343  }
3344  }
3345  return;
3346  }
3347 
3348  /// See followUsesInMBEC
3349  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
3351  bool IsNonNull = false;
3352  bool TrackUse = false;
3353  int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
3354  A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
3355  LLVM_DEBUG(dbgs() << "[AADereferenceable] Deref bytes: " << DerefBytes
3356  << " for instruction " << *I << "\n");
3357 
3358  addAccessedBytesForUse(A, U, I, State);
3359  State.takeKnownDerefBytesMaximum(DerefBytes);
3360  return TrackUse;
3361  }
3362 
3363  /// See AbstractAttribute::manifest(...).
3364  ChangeStatus manifest(Attributor &A) override {
3366  if (isAssumedNonNull() && hasAttr(Attribute::DereferenceableOrNull)) {
3367  removeAttrs({Attribute::DereferenceableOrNull});
3368  return ChangeStatus::CHANGED;
3369  }
3370  return Change;
3371  }
3372 
3373  void getDeducedAttributes(LLVMContext &Ctx,
3374  SmallVectorImpl<Attribute> &Attrs) const override {
3375  // TODO: Add *_globally support
3376  if (isAssumedNonNull())
3378  Ctx, getAssumedDereferenceableBytes()));
3379  else
3381  Ctx, getAssumedDereferenceableBytes()));
3382  }
3383 
3384  /// See AbstractAttribute::getAsStr().
3385  const std::string getAsStr() const override {
3386  if (!getAssumedDereferenceableBytes())
3387  return "unknown-dereferenceable";
3388  return std::string("dereferenceable") +
3389  (isAssumedNonNull() ? "" : "_or_null") +
3390  (isAssumedGlobal() ? "_globally" : "") + "<" +
3391  std::to_string(getKnownDereferenceableBytes()) + "-" +
3392  std::to_string(getAssumedDereferenceableBytes()) + ">";
3393  }
3394 };
3395 
3396 /// Dereferenceable attribute for a floating value.
3397 struct AADereferenceableFloating : AADereferenceableImpl {
3398  AADereferenceableFloating(const IRPosition &IRP, Attributor &A)
3399  : AADereferenceableImpl(IRP, A) {}
3400 
3401  /// See AbstractAttribute::updateImpl(...).
3402  ChangeStatus updateImpl(Attributor &A) override {
3403  const DataLayout &DL = A.getDataLayout();
3404 
3405  auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
3406  bool Stripped) -> bool {
3407  unsigned IdxWidth =
3409  APInt Offset(IdxWidth, 0);
3410  const Value *Base =
3411  stripAndAccumulateMinimalOffsets(A, *this, &V, DL, Offset, false);
3412 
3413  const auto &AA =
3414  A.getAAFor<AADereferenceable>(*this, IRPosition::value(*Base));
3415  int64_t DerefBytes = 0;
3416  if (!Stripped && this == &AA) {
3417  // Use IR information if we did not strip anything.
3418  // TODO: track globally.
3419  bool CanBeNull;
3420  DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
3421  T.GlobalState.indicatePessimisticFixpoint();
3422  } else {
3423  const DerefState &DS = static_cast<const DerefState &>(AA.getState());
3424  DerefBytes = DS.DerefBytesState.getAssumed();
3425  T.GlobalState &= DS.GlobalState;
3426  }
3427 
3428 
3429  // For now we do not try to "increase" dereferenceability due to negative
3430  // indices as we first have to come up with code to deal with loops and
3431  // for overflows of the dereferenceable bytes.
3432  int64_t OffsetSExt = Offset.getSExtValue();
3433  if (OffsetSExt < 0)
3434  OffsetSExt = 0;
3435 
3436  T.takeAssumedDerefBytesMinimum(
3437  std::max(int64_t(0), DerefBytes - OffsetSExt));
3438 
3439  if (this == &AA) {
3440  if (!Stripped) {
3441  // If nothing was stripped IR information is all we got.
3442  T.takeKnownDerefBytesMaximum(
3443  std::max(int64_t(0), DerefBytes - OffsetSExt));
3444  T.indicatePessimisticFixpoint();
3445  } else if (OffsetSExt > 0) {
3446  // If something was stripped but there is circular reasoning we look
3447  // for the offset. If it is positive we basically decrease the
3448  // dereferenceable bytes in a circluar loop now, which will simply
3449  // drive them down to the known value in a very slow way which we
3450  // can accelerate.
3451  T.indicatePessimisticFixpoint();
3452  }
3453  }
3454 
3455  return T.isValidState();
3456  };
3457 
3458  DerefState T;
3459  if (!genericValueTraversal<AADereferenceable, DerefState>(
3460  A, getIRPosition(), *this, T, VisitValueCB, getCtxI()))
3461  return indicatePessimisticFixpoint();
3462 
3463  return clampStateAndIndicateChange(getState(), T);
3464  }
3465 
3466  /// See AbstractAttribute::trackStatistics()
3467  void trackStatistics() const override {
3468  STATS_DECLTRACK_FLOATING_ATTR(dereferenceable)
3469  }
3470 };
3471 
3472 /// Dereferenceable attribute for a return value.
3473 struct AADereferenceableReturned final
3474  : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl> {
3475  AADereferenceableReturned(const IRPosition &IRP, Attributor &A)
3476  : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl>(
3477  IRP, A) {}
3478 
3479  /// See AbstractAttribute::trackStatistics()
3480  void trackStatistics() const override {
3481  STATS_DECLTRACK_FNRET_ATTR(dereferenceable)
3482  }
3483 };
3484 
3485 /// Dereferenceable attribute for an argument
3486 struct AADereferenceableArgument final
3487  : AAArgumentFromCallSiteArguments<AADereferenceable,
3488  AADereferenceableImpl> {
3489  using Base =
3490  AAArgumentFromCallSiteArguments<AADereferenceable, AADereferenceableImpl>;
3491  AADereferenceableArgument(const IRPosition &IRP, Attributor &A)
3492  : Base(IRP, A) {}
3493 
3494  /// See AbstractAttribute::trackStatistics()
3495  void trackStatistics() const override {
3496  STATS_DECLTRACK_ARG_ATTR(dereferenceable)
3497  }
3498 };
3499 
3500 /// Dereferenceable attribute for a call site argument.
3501 struct AADereferenceableCallSiteArgument final : AADereferenceableFloating {
3502  AADereferenceableCallSiteArgument(const IRPosition &IRP, Attributor &A)
3503  : AADereferenceableFloating(IRP, A) {}
3504 
3505  /// See AbstractAttribute::trackStatistics()
3506  void trackStatistics() const override {
3507  STATS_DECLTRACK_CSARG_ATTR(dereferenceable)
3508  }
3509 };
3510 
3511 /// Dereferenceable attribute deduction for a call site return value.
3512 struct AADereferenceableCallSiteReturned final
3513  : AACallSiteReturnedFromReturned<AADereferenceable, AADereferenceableImpl> {
3514  using Base =
3515  AACallSiteReturnedFromReturned<AADereferenceable, AADereferenceableImpl>;
3516  AADereferenceableCallSiteReturned(const IRPosition &IRP, Attributor &A)
3517  : Base(IRP, A) {}
3518 
3519  /// See AbstractAttribute::trackStatistics()
3520  void trackStatistics() const override {
3521  STATS_DECLTRACK_CS_ATTR(dereferenceable);
3522  }
3523 };
3524 
3525 // ------------------------ Align Argument Attribute ------------------------
3526 
3527 static unsigned getKnownAlignForUse(Attributor &A,
3528  AbstractAttribute &QueryingAA,
3529  Value &AssociatedValue, const Use *U,
3530  const Instruction *I, bool &TrackUse) {
3531  // We need to follow common pointer manipulation uses to the accesses they
3532  // feed into.
3533  if (isa<CastInst>(I)) {
3534  // Follow all but ptr2int casts.
3535  TrackUse = !isa<PtrToIntInst>(I);
3536  return 0;
3537  }
3538  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
3539  if (GEP->hasAllConstantIndices()) {
3540  TrackUse = true;
3541  return 0;
3542  }
3543  }
3544 
3545  MaybeAlign MA;
3546  if (const auto *CB = dyn_cast<CallBase>(I)) {
3547  if (CB->isBundleOperand(U) || CB->isCallee(U))
3548  return 0;
3549 
3550  unsigned ArgNo = CB->getArgOperandNo(U);
3551  IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
3552  // As long as we only use known information there is no need to track
3553  // dependences here.
3554  auto &AlignAA = A.getAAFor<AAAlign>(QueryingAA, IRP,
3555  /* TrackDependence */ false);
3556  MA = MaybeAlign(AlignAA.getKnownAlign());
3557  }
3558 
3559  const DataLayout &DL = A.getDataLayout();
3560  const Value *UseV = U->get();
3561  if (auto *SI = dyn_cast<StoreInst>(I)) {
3562  if (SI->getPointerOperand() == UseV)
3563  MA = SI->getAlign();
3564  } else if (auto *LI = dyn_cast<LoadInst>(I)) {
3565  if (LI->getPointerOperand() == UseV)
3566  MA = LI->getAlign();
3567  }
3568 
3569  if (!MA || *MA <= 1)
3570  return 0;
3571 
3572  unsigned Alignment = MA->value();
3573  int64_t Offset;
3574 
3575  if (const Value *Base = GetPointerBaseWithConstantOffset(UseV, Offset, DL)) {
3576  if (Base == &AssociatedValue) {
3577  // BasePointerAddr + Offset = Alignment * Q for some integer Q.
3578  // So we can say that the maximum power of two which is a divisor of
3579  // gcd(Offset, Alignment) is an alignment.
3580 
3581  uint32_t gcd =
3582  greatestCommonDivisor(uint32_t(abs((int32_t)Offset)), Alignment);
3583  Alignment = llvm::PowerOf2Floor(gcd);
3584  }
3585  }
3586 
3587  return Alignment;
3588 }
3589 
3590 struct AAAlignImpl : AAAlign {
3591  AAAlignImpl(const IRPosition &IRP, Attributor &A) : AAAlign(IRP, A) {}
3592 
3593  /// See AbstractAttribute::initialize(...).
3594  void initialize(Attributor &A) override {
3596  getAttrs({Attribute::Alignment}, Attrs);
3597  for (const Attribute &Attr : Attrs)
3598  takeKnownMaximum(Attr.getValueAsInt());
3599 
3600  Value &V = getAssociatedValue();
3601  // TODO: This is a HACK to avoid getPointerAlignment to introduce a ptr2int
3602  // use of the function pointer. This was caused by D73131. We want to
3603  // avoid this for function pointers especially because we iterate
3604  // their uses and int2ptr is not handled. It is not a correctness
3605  // problem though!
3606  if (!V.getType()->getPointerElementType()->isFunctionTy())
3607  takeKnownMaximum(V.getPointerAlignment(A.getDataLayout()).value());
3608 
3609  if (getIRPosition().isFnInterfaceKind() &&
3610  (!getAnchorScope() ||
3611  !A.isFunctionIPOAmendable(*getAssociatedFunction()))) {
3612  indicatePessimisticFixpoint();
3613  return;
3614  }
3615 
3616  if (Instruction *CtxI = getCtxI())
3617  followUsesInMBEC(*this, A, getState(), *CtxI);
3618  }
3619 
3620  /// See AbstractAttribute::manifest(...).
3621  ChangeStatus manifest(Attributor &A) override {
3622  ChangeStatus LoadStoreChanged = ChangeStatus::UNCHANGED;
3623 
3624  // Check for users that allow alignment annotations.
3625  Value &AssociatedValue = getAssociatedValue();
3626  for (const Use &U : AssociatedValue.uses()) {
3627  if (auto *SI = dyn_cast<StoreInst>(U.getUser())) {
3628  if (SI->getPointerOperand() == &AssociatedValue)
3629  if (SI->getAlignment() < getAssumedAlign()) {
3631  "Number of times alignment added to a store");
3632  SI->setAlignment(Align(getAssumedAlign()));
3633  LoadStoreChanged = ChangeStatus::CHANGED;
3634  }
3635  } else if (auto *LI = dyn_cast<LoadInst>(U.getUser())) {
3636  if (LI->getPointerOperand() == &AssociatedValue)
3637  if (LI->getAlignment() < getAssumedAlign()) {
3638  LI->setAlignment(Align(getAssumedAlign()));
3640  "Number of times alignment added to a load");
3641  LoadStoreChanged = ChangeStatus::CHANGED;
3642  }
3643  }
3644  }
3645 
3646  ChangeStatus Changed = AAAlign::manifest(A);
3647 
3648  Align InheritAlign =
3649  getAssociatedValue().getPointerAlignment(A.getDataLayout());
3650  if (InheritAlign >= getAssumedAlign())
3651  return LoadStoreChanged;
3652  return Changed | LoadStoreChanged;
3653  }
3654 
3655  // TODO: Provide a helper to determine the implied ABI alignment and check in
3656  // the existing manifest method and a new one for AAAlignImpl that value
3657  // to avoid making the alignment explicit if it did not improve.
3658 
3659  /// See AbstractAttribute::getDeducedAttributes
3660  virtual void
3661  getDeducedAttributes(LLVMContext &Ctx,
3662  SmallVectorImpl<Attribute> &Attrs) const override {
3663  if (getAssumedAlign() > 1)
3664  Attrs.emplace_back(
3665  Attribute::getWithAlignment(Ctx, Align(getAssumedAlign())));
3666  }
3667 
3668  /// See followUsesInMBEC
3669  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
3670  AAAlign::StateType &State) {
3671  bool TrackUse = false;
3672 
3673  unsigned int KnownAlign =
3674  getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse);
3675  State.takeKnownMaximum(KnownAlign);
3676 
3677  return TrackUse;
3678  }
3679 
3680  /// See AbstractAttribute::getAsStr().
3681  const std::string getAsStr() const override {
3682  return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) +
3683  "-" + std::to_string(getAssumedAlign()) + ">")
3684  : "unknown-align";
3685  }
3686 };
3687 
3688 /// Align attribute for a floating value.
3689 struct AAAlignFloating : AAAlignImpl {
3690  AAAlignFloating(const IRPosition &IRP, Attributor &A) : AAAlignImpl(IRP, A) {}
3691 
3692  /// See AbstractAttribute::updateImpl(...).
3693  ChangeStatus updateImpl(Attributor &A) override {
3694  const DataLayout &DL = A.getDataLayout();
3695 
3696  auto VisitValueCB = [&](Value &V, const Instruction *,
3697  AAAlign::StateType &T, bool Stripped) -> bool {
3698  const auto &AA = A.getAAFor<AAAlign>(*this, IRPosition::value(V));
3699  if (!Stripped && this == &AA) {
3700  // Use only IR information if we did not strip anything.
3701  Align PA = V.getPointerAlignment(DL);
3702  T.takeKnownMaximum(PA.value());
3703  T.indicatePessimisticFixpoint();
3704  } else {
3705  // Use abstract attribute information.
3706  const AAAlign::StateType &DS =
3707  static_cast<const AAAlign::StateType &>(AA.getState());
3708  T ^= DS;
3709  }
3710  return T.isValidState();
3711  };
3712 
3713  StateType T;
3714  if (!genericValueTraversal<AAAlign, StateType>(A, getIRPosition(), *this, T,
3715  VisitValueCB, getCtxI()))
3716  return indicatePessimisticFixpoint();
3717 
3718  // TODO: If we know we visited all incoming values, thus no are assumed
3719  // dead, we can take the known information from the state T.
3720  return clampStateAndIndicateChange(getState(), T);
3721  }
3722 
3723  /// See AbstractAttribute::trackStatistics()
3724  void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(align) }
3725 };
3726 
3727 /// Align attribute for function return value.
3728 struct AAAlignReturned final
3729  : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> {
3730  AAAlignReturned(const IRPosition &IRP, Attributor &A)
3731  : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>(IRP, A) {}
3732 
3733  /// See AbstractAttribute::trackStatistics()
3734  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) }
3735 };
3736 
3737 /// Align attribute for function argument.
3738 struct AAAlignArgument final
3739  : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl> {
3740  using Base = AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl>;
3741  AAAlignArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
3742 
3743  /// See AbstractAttribute::manifest(...).
3744  ChangeStatus manifest(Attributor &A) override {
3745  // If the associated argument is involved in a must-tail call we give up
3746  // because we would need to keep the argument alignments of caller and
3747  // callee in-sync. Just does not seem worth the trouble right now.
3748  if (A.getInfoCache().isInvolvedInMustTailCall(*getAssociatedArgument()))
3749  return ChangeStatus::UNCHANGED;
3750  return Base::manifest(A);
3751  }
3752 
3753  /// See AbstractAttribute::trackStatistics()
3754  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(aligned) }
3755 };
3756 
3757 struct AAAlignCallSiteArgument final : AAAlignFloating {
3758  AAAlignCallSiteArgument(const IRPosition &IRP, Attributor &A)
3759  : AAAlignFloating(IRP, A) {}
3760 
3761  /// See AbstractAttribute::manifest(...).
3762  ChangeStatus manifest(Attributor &A) override {
3763  // If the associated argument is involved in a must-tail call we give up
3764  // because we would need to keep the argument alignments of caller and
3765  // callee in-sync. Just does not seem worth the trouble right now.
3766  if (Argument *Arg = getAssociatedArgument())
3768  return ChangeStatus::UNCHANGED;
3769  ChangeStatus Changed = AAAlignImpl::manifest(A);
3770  Align InheritAlign =
3771  getAssociatedValue().getPointerAlignment(A.getDataLayout());
3772  if (InheritAlign >= getAssumedAlign())
3773  Changed = ChangeStatus::UNCHANGED;
3774  return Changed;
3775  }
3776 
3777  /// See AbstractAttribute::updateImpl(Attributor &A).
3778  ChangeStatus updateImpl(Attributor &A) override {
3779  ChangeStatus Changed = AAAlignFloating::updateImpl(A);
3780  if (Argument *Arg = getAssociatedArgument()) {
3781  // We only take known information from the argument
3782  // so we do not need to track a dependence.
3783  const auto &ArgAlignAA = A.getAAFor<AAAlign>(
3784  *this, IRPosition::argument(*Arg), /* TrackDependence */ false);
3785  takeKnownMaximum(ArgAlignAA.getKnownAlign());
3786  }
3787  return Changed;
3788  }
3789 
3790  /// See AbstractAttribute::trackStatistics()
3791  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) }
3792 };
3793 
3794 /// Align attribute deduction for a call site return value.
3795 struct AAAlignCallSiteReturned final
3796  : AACallSiteReturnedFromReturned<AAAlign, AAAlignImpl> {
3797  using Base = AACallSiteReturnedFromReturned<AAAlign, AAAlignImpl>;
3798  AAAlignCallSiteReturned(const IRPosition &IRP, Attributor &A)
3799  : Base(IRP, A) {}
3800 
3801  /// See AbstractAttribute::initialize(...).
3802  void initialize(Attributor &A) override {
3803  Base::initialize(A);
3804  Function *F = getAssociatedFunction();
3805  if (!F)
3806  indicatePessimisticFixpoint();
3807  }
3808 
3809  /// See AbstractAttribute::trackStatistics()
3810  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(align); }
3811 };
3812 
3813 /// ------------------ Function No-Return Attribute ----------------------------
3814 struct AANoReturnImpl : public AANoReturn {
3815  AANoReturnImpl(const IRPosition &IRP, Attributor &A) : AANoReturn(IRP, A) {}
3816 
3817  /// See AbstractAttribute::initialize(...).
3818  void initialize(Attributor &A) override {
3820  Function *F = getAssociatedFunction();
3821  if (!F)
3822  indicatePessimisticFixpoint();
3823  }
3824 
3825  /// See AbstractAttribute::getAsStr().
3826  const std::string getAsStr() const override {
3827  return getAssumed() ? "noreturn" : "may-return";
3828  }
3829 
3830  /// See AbstractAttribute::updateImpl(Attributor &A).
3831  virtual ChangeStatus updateImpl(Attributor &A) override {
3832  auto CheckForNoReturn = [](Instruction &) { return false; };
3833  if (!A.checkForAllInstructions(CheckForNoReturn, *this,
3834  {(unsigned)Instruction::Ret}))
3835  return indicatePessimisticFixpoint();
3836  return ChangeStatus::UNCHANGED;
3837  }
3838 };
3839 
3840 struct AANoReturnFunction final : AANoReturnImpl {
3841  AANoReturnFunction(const IRPosition &IRP, Attributor &A)
3842  : AANoReturnImpl(IRP, A) {}
3843 
3844  /// See AbstractAttribute::trackStatistics()
3845  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(noreturn) }
3846 };
3847 
3848 /// NoReturn attribute deduction for a call sites.
3849 struct AANoReturnCallSite final : AANoReturnImpl {
3850  AANoReturnCallSite(const IRPosition &IRP, Attributor &A)
3851  : AANoReturnImpl(IRP, A) {}
3852 
3853  /// See AbstractAttribute::updateImpl(...).
3854  ChangeStatus updateImpl(Attributor &A) override {
3855  // TODO: Once we have call site specific value information we can provide
3856  // call site specific liveness information and then it makes
3857  // sense to specialize attributes for call sites arguments instead of
3858  // redirecting requests to the callee argument.
3859  Function *F = getAssociatedFunction();
3860  const IRPosition &FnPos = IRPosition::function(*F);
3861  auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos);
3862  return clampStateAndIndicateChange(
3863  getState(),
3864  static_cast<const AANoReturn::StateType &>(FnAA.getState()));
3865  }
3866 
3867  /// See AbstractAttribute::trackStatistics()
3868  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(noreturn); }
3869 };
3870 
3871 /// ----------------------- Variable Capturing ---------------------------------
3872 
3873 /// A class to hold the state of for no-capture attributes.
3874 struct AANoCaptureImpl : public AANoCapture {
3875  AANoCaptureImpl(const IRPosition &IRP, Attributor &A) : AANoCapture(IRP, A) {}
3876 
3877  /// See AbstractAttribute::initialize(...).
3878  void initialize(Attributor &A) override {
3879  if (hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ true)) {
3880  indicateOptimisticFixpoint();
3881  return;
3882  }
3883  Function *AnchorScope = getAnchorScope();
3884  if (isFnInterfaceKind() &&
3885  (!AnchorScope || !A.isFunctionIPOAmendable(*AnchorScope))) {
3886  indicatePessimisticFixpoint();
3887  return;
3888  }
3889 
3890  // You cannot "capture" null in the default address space.
3891  if (isa<ConstantPointerNull>(getAssociatedValue()) &&
3892  getAssociatedValue().getType()->getPointerAddressSpace() == 0) {
3893  indicateOptimisticFixpoint();
3894  return;
3895  }
3896 
3897  const Function *F = getArgNo() >= 0 ? getAssociatedFunction() : AnchorScope;
3898 
3899  // Check what state the associated function can actually capture.
3900  if (F)
3901  determineFunctionCaptureCapabilities(getIRPosition(), *F, *this);
3902  else
3903  indicatePessimisticFixpoint();
3904  }
3905 
3906  /// See AbstractAttribute::updateImpl(...).
3907  ChangeStatus updateImpl(Attributor &A) override;
3908 
3909  /// see AbstractAttribute::isAssumedNoCaptureMaybeReturned(...).
3910  virtual void
3911  getDeducedAttributes(LLVMContext &Ctx,
3912  SmallVectorImpl<Attribute> &Attrs) const override {
3913  if (!isAssumedNoCaptureMaybeReturned())
3914  return;
3915 
3916  if (getArgNo() >= 0) {
3917  if (isAssumedNoCapture())
3918  Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture));
3919  else if (ManifestInternal)
3920  Attrs.emplace_back(Attribute::get(Ctx, "no-capture-maybe-returned"));
3921  }
3922  }
3923 
3924  /// Set the NOT_CAPTURED_IN_MEM and NOT_CAPTURED_IN_RET bits in \p Known
3925  /// depending on the ability of the function associated with \p IRP to capture
3926  /// state in memory and through "returning/throwing", respectively.
3927  static void determineFunctionCaptureCapabilities(const IRPosition &IRP,
3928  const Function &F,
3929  BitIntegerState &State) {
3930  // TODO: Once we have memory behavior attributes we should use them here.
3931 
3932  // If we know we cannot communicate or write to memory, we do not care about
3933  // ptr2int anymore.
3934  if (F.onlyReadsMemory() && F.doesNotThrow() &&
3935  F.getReturnType()->isVoidTy()) {
3936  State.addKnownBits(NO_CAPTURE);
3937  return;
3938  }
3939 
3940  // A function cannot capture state in memory if it only reads memory, it can
3941  // however return/throw state and the state might be influenced by the
3942  // pointer value, e.g., loading from a returned pointer might reveal a bit.
3943  if (F.onlyReadsMemory())
3944  State.addKnownBits(NOT_CAPTURED_IN_MEM);
3945 
3946  // A function cannot communicate state back if it does not through
3947  // exceptions and doesn not return values.
3948  if (F.doesNotThrow() && F.getReturnType()->isVoidTy())
3949  State.addKnownBits(NOT_CAPTURED_IN_RET);
3950 
3951  // Check existing "returned" attributes.
3952  int ArgNo = IRP.getArgNo();
3953  if (F.doesNotThrow() && ArgNo >= 0) {
3954  for (unsigned u = 0, e = F.arg_size(); u < e; ++u)
3955  if (F.hasParamAttribute(u, Attribute::Returned)) {
3956  if (u == unsigned(ArgNo))
3957  State.removeAssumedBits(NOT_CAPTURED_IN_RET);
3958  else if (F.onlyReadsMemory())
3959  State.addKnownBits(NO_CAPTURE);
3960  else
3961  State.addKnownBits(NOT_CAPTURED_IN_RET);
3962  break;
3963  }
3964  }
3965  }
3966 
3967  /// See AbstractState::getAsStr().
3968  const std::string getAsStr() const override {
3969  if (isKnownNoCapture())
3970  return "known not-captured";
3971  if (isAssumedNoCapture())
3972  return "assumed not-captured";
3973  if (isKnownNoCaptureMaybeReturned())
3974  return "known not-captured-maybe-returned";
3975  if (isAssumedNoCaptureMaybeReturned())
3976  return "assumed not-captured-maybe-returned";
3977  return "assumed-captured";
3978  }
3979 };
3980 
3981 /// Attributor-aware capture tracker.
3982 struct AACaptureUseTracker final : public CaptureTracker {
3983 
3984  /// Create a capture tracker that can lookup in-flight abstract attributes
3985  /// through the Attributor \p A.
3986  ///
3987  /// If a use leads to a potential capture, \p CapturedInMemory is set and the
3988  /// search is stopped. If a use leads to a return instruction,
3989  /// \p CommunicatedBack is set to true and \p CapturedInMemory is not changed.
3990  /// If a use leads to a ptr2int which may capture the value,
3991  /// \p CapturedInInteger is set. If a use is found that is currently assumed
3992  /// "no-capture-maybe-returned", the user is added to the \p PotentialCopies
3993  /// set. All values in \p PotentialCopies are later tracked as well. For every
3994  /// explored use we decrement \p RemainingUsesToExplore. Once it reaches 0,
3995  /// the search is stopped with \p CapturedInMemory and \p CapturedInInteger
3996  /// conservatively set to true.
3997  AACaptureUseTracker(Attributor &A, AANoCapture &NoCaptureAA,
3998  const AAIsDead &IsDeadAA, AANoCapture::StateType &State,
3999  SmallVectorImpl<const Value *> &PotentialCopies,
4000  unsigned &RemainingUsesToExplore)
4001  : A(A), NoCaptureAA(NoCaptureAA), IsDeadAA(IsDeadAA), State(State),
4002  PotentialCopies(PotentialCopies),
4003  RemainingUsesToExplore(RemainingUsesToExplore) {}
4004 
4005  /// Determine if \p V maybe captured. *Also updates the state!*
4006  bool valueMayBeCaptured(const Value *V) {
4007  if (V->getType()->isPointerTy()) {
4008  PointerMayBeCaptured(V, this);
4009  } else {
4010  State.indicatePessimisticFixpoint();
4011  }
4012  return State.isAssumed(AANoCapture::NO_CAPTURE_MAYBE_RETURNED);
4013  }
4014 
4015  /// See CaptureTracker::tooManyUses().
4016  void tooManyUses() override {
4017  State.removeAssumedBits(AANoCapture::NO_CAPTURE);
4018  }
4019 
4020  bool isDereferenceableOrNull(Value *O, const DataLayout &DL) override {
4022  return true;
4023  const auto &DerefAA = A.getAAFor<AADereferenceable>(
4024  NoCaptureAA, IRPosition::value(*O), /* TrackDependence */ true,
4026  return DerefAA.getAssumedDereferenceableBytes();
4027  }
4028 
4029  /// See CaptureTracker::captured(...).
4030  bool captured(const Use *U) override {
4031  Instruction *UInst = cast<Instruction>(U->getUser());
4032  LLVM_DEBUG(dbgs() << "Check use: " << *U->get() << " in " << *UInst
4033  << "\n");
4034 
4035  // Because we may reuse the tracker multiple times we keep track of the
4036  // number of explored uses ourselves as well.
4037  if (RemainingUsesToExplore-- == 0) {
4038  LLVM_DEBUG(dbgs() << " - too many uses to explore!\n");
4039  return isCapturedIn(/* Memory */ true, /* Integer */ true,
4040  /* Return */ true);
4041  }
4042 
4043  // Deal with ptr2int by following uses.
4044  if (isa<PtrToIntInst>(UInst)) {
4045  LLVM_DEBUG(dbgs() << " - ptr2int assume the worst!\n");
4046  return valueMayBeCaptured(UInst);
4047  }
4048 
4049  // Explicitly catch return instructions.
4050  if (isa<ReturnInst>(UInst))
4051  return isCapturedIn(/* Memory */ false, /* Integer */ false,
4052  /* Return */ true);
4053 
4054  // For now we only use special logic for call sites. However, the tracker
4055  // itself knows about a lot of other non-capturing cases already.
4056  auto *CB = dyn_cast<CallBase>(UInst);
4057  if (!CB || !CB->isArgOperand(U))
4058  return isCapturedIn(/* Memory */ true, /* Integer */ true,
4059  /* Return */ true);
4060 
4061  unsigned ArgNo = CB->getArgOperandNo(U);
4062  const IRPosition &CSArgPos = IRPosition::callsite_argument(*CB, ArgNo);
4063  // If we have a abstract no-capture attribute for the argument we can use
4064  // it to justify a non-capture attribute here. This allows recursion!
4065  auto &ArgNoCaptureAA = A.getAAFor<AANoCapture>(NoCaptureAA, CSArgPos);
4066  if (ArgNoCaptureAA.isAssumedNoCapture())
4067  return isCapturedIn(/* Memory */ false, /* Integer */ false,
4068  /* Return */ false);
4069  if (ArgNoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
4070  addPotentialCopy(*CB);
4071  return isCapturedIn(/* Memory */ false, /* Integer */ false,
4072  /* Return */ false);
4073  }
4074 
4075  // Lastly, we could not find a reason no-capture can be assumed so we don't.
4076  return isCapturedIn(/* Memory */ true, /* Integer */ true,
4077  /* Return */ true);
4078  }
4079 
4080  /// Register \p CS as potential copy of the value we are checking.
4081  void addPotentialCopy(CallBase &CB) { PotentialCopies.push_back(&CB); }
4082 
4083  /// See CaptureTracker::shouldExplore(...).
4084  bool shouldExplore(const Use *U) override {
4085  // Check liveness and ignore droppable users.
4086  return !U->getUser()->isDroppable() &&
4087  !A.isAssumedDead(*U, &NoCaptureAA, &IsDeadAA);
4088  }
4089 
4090  /// Update the state according to \p CapturedInMem, \p CapturedInInt, and
4091  /// \p CapturedInRet, then return the appropriate value for use in the
4092  /// CaptureTracker::captured() interface.
4093  bool isCapturedIn(bool CapturedInMem, bool CapturedInInt,
4094  bool CapturedInRet) {
4095  LLVM_DEBUG(dbgs() << " - captures [Mem " << CapturedInMem << "|Int "
4096  << CapturedInInt << "|Ret " << CapturedInRet << "]\n");
4097  if (CapturedInMem)
4098  State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_MEM);
4099  if (CapturedInInt)
4100  State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_INT);
4101  if (CapturedInRet)
4102  State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_RET);
4103  return !State.isAssumed(AANoCapture::NO_CAPTURE_MAYBE_RETURNED);
4104  }
4105 
4106 private:
4107  /// The attributor providing in-flight abstract attributes.
4108  Attributor &A;
4109 
4110  /// The abstract attribute currently updated.
4111  AANoCapture &NoCaptureAA;
4112 
4113  /// The abstract liveness state.
4114  const AAIsDead &IsDeadAA;
4115 
4116  /// The state currently updated.
4117  AANoCapture::StateType &State;
4118 
4119  /// Set of potential copies of the tracked value.
4120  SmallVectorImpl<const Value *> &PotentialCopies;
4121 
4122  /// Global counter to limit the number of explored uses.
4123  unsigned &RemainingUsesToExplore;
4124 };
4125 
4126 ChangeStatus AANoCaptureImpl::updateImpl(Attributor &A) {
4127  const IRPosition &IRP = getIRPosition();
4128  const Value *V =
4129  getArgNo() >= 0 ? IRP.getAssociatedArgument() : &IRP.getAssociatedValue();
4130  if (!V)
4131  return indicatePessimisticFixpoint();
4132 
4133  const Function *F =
4134  getArgNo() >= 0 ? IRP.getAssociatedFunction() : IRP.getAnchorScope();
4135  assert(F && "Expected a function!");
4136  const IRPosition &FnPos = IRPosition::function(*F);
4137  const auto &IsDeadAA =
4138  A.getAAFor<AAIsDead>(*this, FnPos, /* TrackDependence */ false);
4139 
4141 
4142  // Readonly means we cannot capture through memory.
4143  const auto &FnMemAA =
4144  A.getAAFor<AAMemoryBehavior>(*this, FnPos, /* TrackDependence */ false);
4145  if (FnMemAA.isAssumedReadOnly()) {
4146  T.addKnownBits(NOT_CAPTURED_IN_MEM);
4147  if (FnMemAA.isKnownReadOnly())
4148  addKnownBits(NOT_CAPTURED_IN_MEM);
4149  else
4150  A.recordDependence(FnMemAA, *this, DepClassTy::OPTIONAL);
4151  }
4152 
4153  // Make sure all returned values are different than the underlying value.
4154  // TODO: we could do this in a more sophisticated way inside
4155  // AAReturnedValues, e.g., track all values that escape through returns
4156  // directly somehow.
4157  auto CheckReturnedArgs = [&](const AAReturnedValues &RVAA) {
4158  bool SeenConstant = false;
4159  for (auto &It : RVAA.returned_values()) {
4160  if (isa<Constant>(It.first)) {
4161  if (SeenConstant)
4162  return false;
4163  SeenConstant = true;
4164  } else if (!isa<Argument>(It.first) ||
4165  It.first == getAssociatedArgument())
4166  return false;
4167  }
4168  return true;
4169  };
4170 
4171  const auto &NoUnwindAA = A.getAAFor<AANoUnwind>(
4172  *this, FnPos, /* TrackDependence */ true, DepClassTy::OPTIONAL);
4173  if (NoUnwindAA.isAssumedNoUnwind()) {
4174  bool IsVoidTy = F->getReturnType()->isVoidTy();
4175  const AAReturnedValues *RVAA =
4176  IsVoidTy ? nullptr
4177  : &A.getAAFor<AAReturnedValues>(*this, FnPos,
4178  /* TrackDependence */ true,
4180  if (IsVoidTy || CheckReturnedArgs(*RVAA)) {
4181  T.addKnownBits(NOT_CAPTURED_IN_RET);
4182  if (T.isKnown(NOT_CAPTURED_IN_MEM))
4183  return ChangeStatus::UNCHANGED;
4184  if (NoUnwindAA.isKnownNoUnwind() &&
4185  (IsVoidTy || RVAA->getState().isAtFixpoint())) {
4186  addKnownBits(NOT_CAPTURED_IN_RET);
4187  if (isKnown(NOT_CAPTURED_IN_MEM))
4188  return indicateOptimisticFixpoint();
4189  }
4190  }
4191  }
4192 
4193  // Use the CaptureTracker interface and logic with the specialized tracker,
4194  // defined in AACaptureUseTracker, that can look at in-flight abstract
4195  // attributes and directly updates the assumed state.
4196  SmallVector<const Value *, 4> PotentialCopies;
4197  unsigned RemainingUsesToExplore =
4199  AACaptureUseTracker Tracker(A, *this, IsDeadAA, T, PotentialCopies,
4200  RemainingUsesToExplore);
4201 
4202  // Check all potential copies of the associated value until we can assume
4203  // none will be captured or we have to assume at least one might be.
4204  unsigned Idx = 0;
4205  PotentialCopies.push_back(V);
4206  while (T.isAssumed(NO_CAPTURE_MAYBE_RETURNED) && Idx < PotentialCopies.size())
4207  Tracker.valueMayBeCaptured(PotentialCopies[Idx++]);
4208 
4209  AANoCapture::StateType &S = getState();
4210  auto Assumed = S.getAssumed();
4211  S.intersectAssumedBits(T.getAssumed());
4212  if (!isAssumedNoCaptureMaybeReturned())
4213  return indicatePessimisticFixpoint();
4214  return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED
4216 }
4217 
4218 /// NoCapture attribute for function arguments.
4219 struct AANoCaptureArgument final : AANoCaptureImpl {
4220  AANoCaptureArgument(const IRPosition &IRP, Attributor &A)
4221  : AANoCaptureImpl(IRP, A) {}
4222 
4223  /// See AbstractAttribute::trackStatistics()
4224  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nocapture) }
4225 };
4226 
4227 /// NoCapture attribute for call site arguments.
4228 struct AANoCaptureCallSiteArgument final : AANoCaptureImpl {
4229  AANoCaptureCallSiteArgument(const IRPosition &IRP, Attributor &A)
4230  : AANoCaptureImpl(IRP, A) {}
4231 
4232  /// See AbstractAttribute::initialize(...).
4233  void initialize(Attributor &A) override {
4234  if (Argument *Arg = getAssociatedArgument())
4235  if (Arg->hasByValAttr())
4236  indicateOptimisticFixpoint();
4238  }
4239 
4240  /// See AbstractAttribute::updateImpl(...).
4241  ChangeStatus updateImpl(Attributor &A) override {
4242  // TODO: Once we have call site specific value information we can provide
4243  // call site specific liveness information and then it makes
4244  // sense to specialize attributes for call sites arguments instead of
4245  // redirecting requests to the callee argument.
4246  Argument *Arg = getAssociatedArgument();
4247  if (!Arg)
4248  return indicatePessimisticFixpoint();
4249  const IRPosition &ArgPos = IRPosition::argument(*Arg);
4250  auto &ArgAA = A.getAAFor<AANoCapture>(*this, ArgPos);
4251  return clampStateAndIndicateChange(
4252  getState(),
4253  static_cast<const AANoCapture::StateType &>(ArgAA.getState()));
4254  }
4255 
4256  /// See AbstractAttribute::trackStatistics()
4257  void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nocapture)};
4258 };
4259 
4260 /// NoCapture attribute for floating values.
4261 struct AANoCaptureFloating final : AANoCaptureImpl {
4262  AANoCaptureFloating(const IRPosition &IRP, Attributor &A)
4263  : AANoCaptureImpl(IRP, A) {}
4264 
4265  /// See AbstractAttribute::trackStatistics()
4266  void trackStatistics() const override {
4268  }
4269 };
4270 
4271 /// NoCapture attribute for function return value.
4272 struct AANoCaptureReturned final : AANoCaptureImpl {
4273  AANoCaptureReturned(const IRPosition &IRP, Attributor &A)
4274  : AANoCaptureImpl(IRP, A) {
4275  llvm_unreachable("NoCapture is not applicable to function returns!");
4276  }
4277 
4278  /// See AbstractAttribute::initialize(...).
4279  void initialize(Attributor &A) override {
4280  llvm_unreachable("NoCapture is not applicable to function returns!");
4281  }
4282 
4283  /// See AbstractAttribute::updateImpl(...).
4284  ChangeStatus updateImpl(Attributor &A) override {
4285  llvm_unreachable("NoCapture is not applicable to function returns!");
4286  }
4287 
4288  /// See AbstractAttribute::trackStatistics()
4289  void trackStatistics() const override {}
4290 };
4291 
4292 /// NoCapture attribute deduction for a call site return value.
4293 struct AANoCaptureCallSiteReturned final : AANoCaptureImpl {
4294  AANoCaptureCallSiteReturned(const IRPosition &IRP, Attributor &A)
4295  : AANoCaptureImpl(IRP, A) {}
4296 
4297  /// See AbstractAttribute::trackStatistics()
4298  void trackStatistics() const override {
4299  STATS_DECLTRACK_CSRET_ATTR(nocapture)
4300  }
4301 };
4302 
4303 /// ------------------ Value Simplify Attribute ----------------------------
4304 struct AAValueSimplifyImpl : AAValueSimplify {
4305  AAValueSimplifyImpl(const IRPosition &IRP, Attributor &A)
4306  : AAValueSimplify(IRP, A) {}
4307 
4308  /// See AbstractAttribute::initialize(...).
4309  void initialize(Attributor &A) override {
4310  if (getAssociatedValue().getType()->isVoidTy())
4311  indicatePessimisticFixpoint();
4312  }
4313 
4314  /// See AbstractAttribute::getAsStr().
4315  const std::string getAsStr() const override {
4316  return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple")
4317  : "not-simple";
4318  }
4319 
4320  /// See AbstractAttribute::trackStatistics()
4321  void trackStatistics() const override {}
4322 
4323  /// See AAValueSimplify::getAssumedSimplifiedValue()
4324  Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const override {
4325  if (!getAssumed())
4326  return const_cast<Value *>(&getAssociatedValue());
4327  return SimplifiedAssociatedValue;
4328  }
4329 
4330  /// Helper function for querying AAValueSimplify and updating candicate.
4331  /// \param QueryingValue Value trying to unify with SimplifiedValue
4332  /// \param AccumulatedSimplifiedValue Current simplification result.
4333  static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA,
4334  Value &QueryingValue,
4335  Optional<Value *> &AccumulatedSimplifiedValue) {
4336  // FIXME: Add a typecast support.
4337 
4338  auto &ValueSimplifyAA = A.getAAFor<AAValueSimplify>(
4339  QueryingAA, IRPosition::value(QueryingValue));
4340 
4341  Optional<Value *> QueryingValueSimplified =
4342  ValueSimplifyAA.getAssumedSimplifiedValue(A);
4343 
4344  if (!QueryingValueSimplified.hasValue())
4345  return true;
4346 
4347  if (!QueryingValueSimplified.getValue())
4348  return false;
4349 
4350  Value &QueryingValueSimplifiedUnwrapped =
4351  *QueryingValueSimplified.getValue();
4352 
4353  if (AccumulatedSimplifiedValue.hasValue() &&
4354  !isa<UndefValue>(AccumulatedSimplifiedValue.getValue()) &&
4355  !isa<UndefValue>(QueryingValueSimplifiedUnwrapped))
4356  return AccumulatedSimplifiedValue == QueryingValueSimplified;
4357  if (AccumulatedSimplifiedValue.hasValue() &&
4358  isa<UndefValue>(QueryingValueSimplifiedUnwrapped))
4359  return true;
4360 
4361  LLVM_DEBUG(dbgs() << "[ValueSimplify] " << QueryingValue
4362  << " is assumed to be "
4363  << QueryingValueSimplifiedUnwrapped << "\n");
4364 
4365  AccumulatedSimplifiedValue = QueryingValueSimplified;
4366  return true;
4367  }
4368 
4369  bool askSimplifiedValueForAAValueConstantRange(Attributor &A) {
4370  if (!getAssociatedValue().getType()->isIntegerTy())
4371  return false;
4372 
4373  const auto &ValueConstantRangeAA =
4374  A.getAAFor<AAValueConstantRange>(*this, getIRPosition());
4375 
4377  ValueConstantRangeAA.getAssumedConstantInt(A);
4378  if (COpt.hasValue()) {
4379  if (auto *C = COpt.getValue())
4380  SimplifiedAssociatedValue = C;
4381  else
4382  return false;
4383  } else {
4384  SimplifiedAssociatedValue = llvm::None;
4385  }
4386  return true;
4387  }
4388 
4389  /// See AbstractAttribute::manifest(...).
4390  ChangeStatus manifest(Attributor &A) override {
4392 
4393  if (SimplifiedAssociatedValue.hasValue() &&
4394  !SimplifiedAssociatedValue.getValue())
4395  return Changed;
4396 
4397  Value &V = getAssociatedValue();
4398  auto *C = SimplifiedAssociatedValue.hasValue()
4399  ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())
4400  : UndefValue::get(V.getType());
4401  if (C) {
4402  // We can replace the AssociatedValue with the constant.
4403  if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
4404  LLVM_DEBUG(dbgs() << "[ValueSimplify] " << V << " -> " << *C
4405  << " :: " << *this << "\n");
4406  if (A.changeValueAfterManifest(V, *C))
4407  Changed = ChangeStatus::CHANGED;
4408  }
4409  }
4410 
4411  return Changed | AAValueSimplify::manifest(A);
4412  }
4413 
4414  /// See AbstractState::indicatePessimisticFixpoint(...).
4415  ChangeStatus indicatePessimisticFixpoint() override {
4416  // NOTE: Associated value will be returned in a pessimistic fixpoint and is
4417  // regarded as known. That's why`indicateOptimisticFixpoint` is called.
4418  SimplifiedAssociatedValue = &getAssociatedValue();
4419  indicateOptimisticFixpoint();
4420  return ChangeStatus::CHANGED;
4421  }
4422 
4423 protected:
4424  // An assumed simplified value. Initially, it is set to Optional::None, which
4425  // means that the value is not clear under current assumption. If in the
4426  // pessimistic state, getAssumedSimplifiedValue doesn't return this value but
4427  // returns orignal associated value.
4428  Optional<Value *> SimplifiedAssociatedValue;
4429 };
4430 
4431 struct AAValueSimplifyArgument final : AAValueSimplifyImpl {
4432  AAValueSimplifyArgument(const IRPosition &IRP, Attributor &A)
4433  : AAValueSimplifyImpl(IRP, A) {}
4434 
4435  void initialize(Attributor &A) override {
4437  if (!getAnchorScope() || getAnchorScope()->isDeclaration())
4438  indicatePessimisticFixpoint();
4439  if (hasAttr({Attribute::InAlloca, Attribute::Preallocated,
4440  Attribute::StructRet, Attribute::Nest},
4441  /* IgnoreSubsumingPositions */ true))
4442  indicatePessimisticFixpoint();
4443 
4444  // FIXME: This is a hack to prevent us from propagating function poiner in
4445  // the new pass manager CGSCC pass as it creates call edges the
4446  // CallGraphUpdater cannot handle yet.
4447  Value &V = getAssociatedValue();
4448  if (V.getType()->isPointerTy() &&
4450  !A.isModulePass())
4451  indicatePessimisticFixpoint();
4452  }
4453 
4454  /// See AbstractAttribute::updateImpl(...).
4455  ChangeStatus updateImpl(Attributor &A) override {
4456  // Byval is only replacable if it is readonly otherwise we would write into
4457  // the replaced value and not the copy that byval creates implicitly.
4458  Argument *Arg = getAssociatedArgument();
4459  if (Arg->hasByValAttr()) {
4460  // TODO: We probably need to verify synchronization is not an issue, e.g.,
4461  // there is no race by not copying a constant byval.
4462  const auto &MemAA = A.getAAFor<AAMemoryBehavior>(*this, getIRPosition());
4463  if (!MemAA.isAssumedReadOnly())
4464  return indicatePessimisticFixpoint();
4465  }
4466 
4467  bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
4468 
4469  auto PredForCallSite = [&](AbstractCallSite ACS) {
4470  const IRPosition &ACSArgPos =
4471  IRPosition::callsite_argument(ACS, getArgNo());
4472  // Check if a coresponding argument was found or if it is on not
4473  // associated (which can happen for callback calls).
4474  if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
4475  return false;
4476 
4477  // We can only propagate thread independent values through callbacks.
4478  // This is different to direct/indirect call sites because for them we
4479  // know the thread executing the caller and callee is the same. For
4480  // callbacks this is not guaranteed, thus a thread dependent value could
4481  // be different for the caller and callee, making it invalid to propagate.
4482  Value &ArgOp = ACSArgPos.getAssociatedValue();
4483  if (ACS.isCallbackCall())
4484  if (auto *C = dyn_cast<Constant>(&ArgOp))
4485  if (C->isThreadDependent())
4486  return false;
4487  return checkAndUpdate(A, *this, ArgOp, SimplifiedAssociatedValue);
4488  };
4489 
4490  bool AllCallSitesKnown;
4491  if (!A.checkForAllCallSites(PredForCallSite, *this, true,
4492  AllCallSitesKnown))
4493  if (!askSimplifiedValueForAAValueConstantRange(A))
4494  return indicatePessimisticFixpoint();
4495 
4496  // If a candicate was found in this update, return CHANGED.
4497  return HasValueBefore == SimplifiedAssociatedValue.hasValue()
4500  }
4501 
4502  /// See AbstractAttribute::trackStatistics()
4503  void trackStatistics() const override {
4504  STATS_DECLTRACK_ARG_ATTR(value_simplify)
4505  }
4506 };
4507 
4508 struct AAValueSimplifyReturned : AAValueSimplifyImpl {
4509  AAValueSimplifyReturned(const IRPosition &IRP, Attributor &A)
4510  : AAValueSimplifyImpl(IRP, A) {}
4511 
4512  /// See AbstractAttribute::updateImpl(...).
4513  ChangeStatus updateImpl(Attributor &A) override {
4514  bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
4515 
4516  auto PredForReturned = [&](Value &V) {
4517  return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
4518  };
4519 
4520  if (!A.checkForAllReturnedValues(PredForReturned, *this))
4521  if (!askSimplifiedValueForAAValueConstantRange(A))
4522  return indicatePessimisticFixpoint();
4523 
4524  // If a candicate was found in this update, return CHANGED.
4525  return HasValueBefore == SimplifiedAssociatedValue.hasValue()
4528  }
4529 
4530  ChangeStatus manifest(Attributor &A) override {
4532 
4533  if (SimplifiedAssociatedValue.hasValue() &&
4534  !SimplifiedAssociatedValue.getValue())
4535  return Changed;
4536 
4537  Value &V = getAssociatedValue();
4538  auto *C = SimplifiedAssociatedValue.hasValue()
4539  ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())
4540  : UndefValue::get(V.getType());
4541  if (C) {
4542  auto PredForReturned =
4543  [&](Value &V, const SmallSetVector<ReturnInst *, 4> &RetInsts) {
4544  // We can replace the AssociatedValue with the constant.
4545  if (&V == C || V.getType() != C->getType() || isa<UndefValue>(V))
4546  return true;
4547 
4548  for (ReturnInst *RI : RetInsts) {
4549  if (RI->getFunction() != getAnchorScope())
4550  continue;
4551  auto *RC = C;
4552  if (RC->getType() != RI->getReturnValue()->getType())
4553  RC = ConstantExpr::getBitCast(RC,
4554  RI->getReturnValue()->getType());
4555  LLVM_DEBUG(dbgs() << "[ValueSimplify] " << V << " -> " << *RC
4556  << " in " << *RI << " :: " << *this << "\n");
4557  if (A.changeUseAfterManifest(RI->getOperandUse(0), *RC))
4558  Changed = ChangeStatus::CHANGED;
4559  }
4560  return true;
4561  };
4562  A.checkForAllReturnedValuesAndReturnInsts(PredForReturned, *this);
4563  }
4564 
4565  return Changed | AAValueSimplify::manifest(A);
4566  }
4567 
4568  /// See AbstractAttribute::trackStatistics()
4569  void trackStatistics() const override {
4570  STATS_DECLTRACK_FNRET_ATTR(value_simplify)
4571  }
4572 };
4573 
4574 struct AAValueSimplifyFloating : AAValueSimplifyImpl {
4575  AAValueSimplifyFloating(const IRPosition &IRP, Attributor &A)
4576  : AAValueSimplifyImpl(IRP, A) {}
4577 
4578  /// See AbstractAttribute::initialize(...).
4579  void initialize(Attributor &A) override {
4580  // FIXME: This might have exposed a SCC iterator update bug in the old PM.
4581  // Needs investigation.
4582  // AAValueSimplifyImpl::initialize(A);
4583  Value &V = getAnchorValue();
4584 
4585  // TODO: add other stuffs
4586  if (isa<Constant>(V))
4587  indicatePessimisticFixpoint();
4588  }
4589 
4590  /// See AbstractAttribute::updateImpl(...).
4591  ChangeStatus updateImpl(Attributor &A) override {
4592  bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
4593 
4594  auto VisitValueCB = [&](Value &V, const Instruction *CtxI, bool &,
4595  bool Stripped) -> bool {
4596  auto &AA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
4597  if (!Stripped && this == &AA) {
4598  // TODO: Look the instruction and check recursively.
4599 
4600  LLVM_DEBUG(dbgs() << "[ValueSimplify] Can't be stripped more : " << V
4601  << "\n");
4602  return false;
4603  }
4604  return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
4605  };
4606 
4607  bool Dummy = false;
4608  if (!genericValueTraversal<AAValueSimplify, bool>(
4609  A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(),
4610  /* UseValueSimplify */ false))
4611  if (!askSimplifiedValueForAAValueConstantRange(A))
4612  return indicatePessimisticFixpoint();
4613 
4614  // If a candicate was found in this update, return CHANGED.
4615 
4616  return HasValueBefore == SimplifiedAssociatedValue.hasValue()
4619  }
4620 
4621  /// See AbstractAttribute::trackStatistics()
4622  void trackStatistics() const override {
4623  STATS_DECLTRACK_FLOATING_ATTR(value_simplify)
4624  }
4625 };
4626 
4627 struct AAValueSimplifyFunction : AAValueSimplifyImpl {
4628  AAValueSimplifyFunction(const IRPosition &IRP, Attributor &A)
4629  : AAValueSimplifyImpl(IRP, A) {}
4630 
4631  /// See AbstractAttribute::initialize(...).
4632  void initialize(Attributor &A) override {
4633  SimplifiedAssociatedValue = &getAnchorValue();
4634  indicateOptimisticFixpoint();
4635  }
4636  /// See AbstractAttribute::initialize(...).
4637  ChangeStatus updateImpl(Attributor &A) override {
4639  "AAValueSimplify(Function|CallSite)::updateImpl will not be called");
4640  }
4641  /// See AbstractAttribute::trackStatistics()
4642  void trackStatistics() const override {
4643  STATS_DECLTRACK_FN_ATTR(value_simplify)
4644  }
4645 };
4646 
4647 struct AAValueSimplifyCallSite : AAValueSimplifyFunction {
4648  AAValueSimplifyCallSite(const IRPosition &IRP, Attributor &A)
4649  : AAValueSimplifyFunction(IRP, A) {}
4650  /// See AbstractAttribute::trackStatistics()
4651  void trackStatistics() const override {
4652  STATS_DECLTRACK_CS_ATTR(value_simplify)
4653  }
4654 };
4655 
4656 struct AAValueSimplifyCallSiteReturned : AAValueSimplifyReturned {
4657  AAValueSimplifyCallSiteReturned(const IRPosition &IRP, Attributor &A)
4658  : AAValueSimplifyReturned(IRP, A) {}
4659 
4660  /// See AbstractAttribute::manifest(...).
4661  ChangeStatus manifest(Attributor &A) override {
4662  return AAValueSimplifyImpl::manifest(A);
4663  }
4664 
4665  void trackStatistics() const override {
4666  STATS_DECLTRACK_CSRET_ATTR(value_simplify)
4667  }
4668 };
4669 struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating {
4670  AAValueSimplifyCallSiteArgument(const IRPosition &IRP, Attributor &A)
4671  : AAValueSimplifyFloating(IRP, A) {}
4672 
4673  /// See AbstractAttribute::manifest(...).
4674  ChangeStatus manifest(Attributor &A) override {
4676 
4677  if (SimplifiedAssociatedValue.hasValue() &&
4678  !SimplifiedAssociatedValue.getValue())
4679  return Changed;
4680 
4681  Value &V = getAssociatedValue();
4682  auto *C = SimplifiedAssociatedValue.hasValue()
4683  ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())
4684  : UndefValue::get(V.getType());
4685  if (C) {
4686  Use &U = cast<CallBase>(&getAnchorValue())->getArgOperandUse(getArgNo());
4687  // We can replace the AssociatedValue with the constant.
4688  if (&V != C && V.getType() == C->getType()) {
4689  if (A.changeUseAfterManifest(U, *C))
4690  Changed = ChangeStatus::CHANGED;
4691  }
4692  }
4693 
4694  return Changed | AAValueSimplify::manifest(A);
4695  }
4696 
4697  void trackStatistics() const override {
4698  STATS_DECLTRACK_CSARG_ATTR(value_simplify)
4699  }
4700 };
4701 
4702 /// ----------------------- Heap-To-Stack Conversion ---------------------------
4703 struct AAHeapToStackImpl : public AAHeapToStack {
4704  AAHeapToStackImpl(const IRPosition &IRP, Attributor &A)
4705  : AAHeapToStack(IRP, A) {}
4706 
4707  const std::string getAsStr() const override {
4708  return "[H2S] Mallocs: " + std::to_string(MallocCalls.size());
4709  }
4710 
4711  ChangeStatus manifest(Attributor &A) override {
4712  assert(getState().isValidState() &&
4713  "Attempted to manifest an invalid state!");
4714 
4716  Function *F = getAnchorScope();
4717  const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F);
4718 
4719  for (Instruction *MallocCall : MallocCalls) {
4720  // This malloc cannot be replaced.
4721  if (BadMallocCalls.count(MallocCall))
4722  continue;
4723 
4724  for (Instruction *FreeCall : FreesForMalloc[MallocCall]) {
4725  LLVM_DEBUG(dbgs() << "H2S: Removing free call: " << *FreeCall << "\n");
4726  A.deleteAfterManifest(*FreeCall);
4727  HasChanged = ChangeStatus::CHANGED;
4728  }
4729 
4730  LLVM_DEBUG(dbgs() << "H2S: Removing malloc call: " << *MallocCall
4731  << "\n");
4732 
4733  Align Alignment;
4734  Constant *Size;
4735  if (isCallocLikeFn(MallocCall, TLI)) {
4736  auto *Num = cast<ConstantInt>(MallocCall->getOperand(0));
4737  auto *SizeT = cast<ConstantInt>(MallocCall->getOperand(1));
4738  APInt TotalSize = SizeT->getValue() * Num->getValue();
4739  Size =
4740  ConstantInt::get(MallocCall->getOperand(0)->getType(), TotalSize);
4741  } else if (isAlignedAllocLikeFn(MallocCall, TLI)) {
4742  Size = cast<ConstantInt>(MallocCall->getOperand(1));
4743  Alignment = MaybeAlign(cast<ConstantInt>(MallocCall->getOperand(0))
4744  ->getValue()
4745  .getZExtValue())
4746  .valueOrOne();
4747  } else {
4748  Size = cast<ConstantInt>(MallocCall->getOperand(0));
4749  }
4750 
4751  unsigned AS = cast<PointerType>(MallocCall->getType())->getAddressSpace();
4752  Instruction *AI =
4753  new AllocaInst(Type::getInt8Ty(F->getContext()), AS, Size, Alignment,
4754  "", MallocCall->getNextNode());
4755 
4756  if (AI->getType() != MallocCall->getType())
4757  AI = new BitCastInst(AI, MallocCall->getType(), "malloc_bc",
4758  AI->getNextNode());
4759 
4760  A.changeValueAfterManifest(*MallocCall, *AI);
4761 
4762  if (auto *II = dyn_cast<InvokeInst>(MallocCall)) {
4763  auto *NBB = II->getNormalDest();
4764  BranchInst::Create(NBB, MallocCall->getParent());
4765  A.deleteAfterManifest(*MallocCall);
4766  } else {
4767  A.deleteAfterManifest(*MallocCall);
4768  }
4769 
4770  // Zero out the allocated memory if it was a calloc.
4771  if (isCallocLikeFn(MallocCall, TLI)) {
4772  auto *BI = new BitCastInst(AI, MallocCall->getType(), "calloc_bc",
4773  AI->getNextNode());
4774  Value *Ops[] = {
4775  BI, ConstantInt::get(F->getContext(), APInt(8, 0, false)), Size,
4777 
4778  Type *Tys[] = {BI->getType(), MallocCall->getOperand(0)->getType()};
4779  Module *M = F->getParent();
4780  Function *Fn = Intrinsic::getDeclaration(M, Intrinsic::memset, Tys);
4781  CallInst::Create(Fn, Ops, "", BI->getNextNode());
4782  }
4783  HasChanged = ChangeStatus::CHANGED;
4784  }
4785 
4786  return HasChanged;
4787  }
4788 
4789  /// Collection of all malloc calls in a function.
4791 
4792  /// Collection of malloc calls that cannot be converted.
4793  DenseSet<const Instruction *> BadMallocCalls;
4794 
4795  /// A map for each malloc call to the set of associated free calls.
4797 
4798  ChangeStatus updateImpl(Attributor &A) override;
4799 };
4800 
4801 ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) {
4802  const Function *F = getAnchorScope();
4803  const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F);
4804 
4805  MustBeExecutedContextExplorer &Explorer =
4807 
4808  auto FreeCheck = [&](Instruction &I) {
4809  const auto &Frees = FreesForMalloc.lookup(&I);
4810  if (Frees.size() != 1)
4811  return false;
4812  Instruction *UniqueFree = *Frees.begin();
4813  return Explorer.findInContextOf(UniqueFree, I.getNextNode());
4814  };
4815 
4816  auto UsesCheck = [&](Instruction &I) {
4817  bool ValidUsesOnly = true;
4818  bool MustUse = true;
4819  auto Pred = [&](const Use &U, bool &Follow) -> bool {
4820  Instruction *UserI = cast<Instruction>(U.getUser());
4821  if (isa<LoadInst>(UserI))
4822  return true;
4823  if (auto *SI = dyn_cast<StoreInst>(UserI)) {
4824  if (SI->getValueOperand() == U.get()) {
4825  LLVM_DEBUG(dbgs()
4826  << "[H2S] escaping store to memory: " << *UserI << "\n");
4827  ValidUsesOnly = false;
4828  } else {
4829  // A store into the malloc'ed memory is fine.
4830  }
4831  return true;
4832  }
4833  if (auto *CB = dyn_cast<CallBase>(UserI)) {
4834  if (!CB->isArgOperand(&U) || CB->isLifetimeStartOrEnd())
4835  return true;
4836  // Record malloc.
4837  if (isFreeCall(UserI, TLI)) {
4838  if (MustUse) {
4839  FreesForMalloc[&I].insert(UserI);
4840  } else {
4841  LLVM_DEBUG(dbgs() << "[H2S] free potentially on different mallocs: "
4842  << *UserI << "\n");
4843  ValidUsesOnly = false;
4844  }
4845  return true;
4846  }
4847 
4848  unsigned ArgNo = CB->getArgOperandNo(&U);
4849 
4850  const auto &NoCaptureAA = A.getAAFor<AANoCapture>(
4851  *this, IRPosition::callsite_argument(*CB, ArgNo));
4852 
4853  // If a callsite argument use is nofree, we are fine.
4854  const auto &ArgNoFreeAA = A.getAAFor<AANoFree>(
4855  *this, IRPosition::callsite_argument(*CB, ArgNo));
4856 
4857  if (!NoCaptureAA.isAssumedNoCapture() ||
4858  !ArgNoFreeAA.isAssumedNoFree()) {
4859  LLVM_DEBUG(dbgs() << "[H2S] Bad user: " << *UserI << "\n");
4860  ValidUsesOnly = false;
4861  }
4862  return true;
4863  }
4864 
4865  if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) ||
4866  isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
4867  MustUse &= !(isa<PHINode>(UserI) || isa<SelectInst>(UserI));
4868  Follow = true;
4869  return true;
4870  }
4871  // Unknown user for which we can not track uses further (in a way that
4872  // makes sense).
4873  LLVM_DEBUG(dbgs() << "[H2S] Unknown user: " << *UserI << "\n");
4874  ValidUsesOnly = false;
4875  return true;
4876  };
4877  A.checkForAllUses(Pred, *this, I);
4878  return ValidUsesOnly;
4879  };
4880 
4881  auto MallocCallocCheck = [&](Instruction &I) {
4882  if (BadMallocCalls.count(&I))
4883  return true;
4884 
4885  bool IsMalloc = isMallocLikeFn(&I, TLI);
4886  bool IsAlignedAllocLike = isAlignedAllocLikeFn(&I, TLI);
4887  bool IsCalloc = !IsMalloc && isCallocLikeFn(&I, TLI);
4888  if (!IsMalloc && !IsAlignedAllocLike && !IsCalloc) {
4889  BadMallocCalls.insert(&I);
4890  return true;
4891  }
4892 
4893  if (IsMalloc) {
4894  if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(0)))
4895  if (Size->getValue().ule(MaxHeapToStackSize))
4896  if (UsesCheck(I) || FreeCheck(I)) {
4897  MallocCalls.insert(&I);
4898  return true;
4899  }
4900  } else if (IsAlignedAllocLike && isa<ConstantInt>(I.getOperand(0))) {
4901  // Only if the alignment and sizes are constant.
4902  if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(1)))
4903  if (Size->getValue().ule(MaxHeapToStackSize))
4904  if (UsesCheck(I) || FreeCheck(I)) {
4905  MallocCalls.insert(&I);
4906  return true;
4907  }
4908  } else if (IsCalloc) {
4909  bool Overflow = false;
4910  if (auto *Num = dyn_cast<ConstantInt>(I.getOperand(0)))
4911  if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(1)))
4912  if ((Size->getValue().umul_ov(Num->getValue(), Overflow))
4913  .ule(MaxHeapToStackSize))
4914  if (!Overflow && (UsesCheck(I) || FreeCheck(I))) {
4915  MallocCalls.insert(&I);
4916  return true;
4917  }
4918  }
4919 
4920  BadMallocCalls.insert(&I);
4921  return true;
4922  };
4923 
4924  size_t NumBadMallocs = BadMallocCalls.size();
4925 
4926  A.checkForAllCallLikeInstructions(MallocCallocCheck, *this);
4927 
4928  if (NumBadMallocs != BadMallocCalls.size())
4929  return ChangeStatus::CHANGED;
4930 
4931  return ChangeStatus::UNCHANGED;
4932 }
4933 
4934 struct AAHeapToStackFunction final : public AAHeapToStackImpl {
4935  AAHeapToStackFunction(const IRPosition &IRP, Attributor &A)
4936  : AAHeapToStackImpl(IRP, A) {}
4937 
4938  /// See AbstractAttribute::trackStatistics().
4939  void trackStatistics() const override {
4940  STATS_DECL(
4941  MallocCalls, Function,
4942  "Number of malloc/calloc/aligned_alloc calls converted to allocas");
4943  for (auto *C : MallocCalls)
4944  if (!BadMallocCalls.count(C))
4945  ++BUILD_STAT_NAME(MallocCalls, Function);
4946  }
4947 };
4948 
4949 /// ----------------------- Privatizable Pointers ------------------------------
4950 struct AAPrivatizablePtrImpl : public AAPrivatizablePtr {
4951  AAPrivatizablePtrImpl(const IRPosition &IRP, Attributor &A)
4952  : AAPrivatizablePtr(IRP, A), PrivatizableType(llvm::None) {}
4953 
4954  ChangeStatus indicatePessimisticFixpoint() override {
4956  PrivatizableType = nullptr;
4957  return ChangeStatus::CHANGED;
4958  }
4959 
4960  /// Identify the type we can chose for a private copy of the underlying
4961  /// argument. None means it is not clear yet, nullptr means there is none.
4962  virtual Optional<Type *> identifyPrivatizableType(Attributor &A) = 0;
4963 
4964  /// Return a privatizable type that encloses both T0 and T1.
4965  /// TODO: This is merely a stub for now as we should manage a mapping as well.
4967  if (!T0.hasValue())
4968  return T1;
4969  if (!T1.hasValue())
4970  return T0;
4971  if (T0 == T1)
4972  return T0;
4973  return nullptr;
4974  }
4975 
4976  Optional<Type *> getPrivatizableType() const override {
4977  return PrivatizableType;
4978  }
4979 
4980  const std::string getAsStr() const override {
4981  return isAssumedPrivatizablePtr() ? "[priv]" : "[no-priv]";
4982  }
4983 
4984 protected:
4985  Optional<Type *> PrivatizableType;
4986 };
4987 
4988 // TODO: Do this for call site arguments (probably also other values) as well.
4989 
4990 struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl {
4991  AAPrivatizablePtrArgument(const IRPosition &IRP, Attributor &A)
4992  : AAPrivatizablePtrImpl(IRP, A) {}
4993 
4994  /// See AAPrivatizablePtrImpl::identifyPrivatizableType(...)
4995  Optional<Type *> identifyPrivatizableType(Attributor &A) override {
4996  // If this is a byval argument and we know all the call sites (so we can
4997  // rewrite them), there is no need to check them explicitly.
4998  bool AllCallSitesKnown;
4999  if (getIRPosition().hasAttr(Attribute::ByVal) &&
5000  A.checkForAllCallSites([](AbstractCallSite ACS) { return true; }, *this,
5001  true, AllCallSitesKnown))
5002  return getAssociatedValue().getType()->getPointerElementType();
5003 
5004  Optional<Type *> Ty;
5005  unsigned ArgNo = getIRPosition().getArgNo();
5006 
5007  // Make sure the associated call site argument has the same type at all call
5008  // sites and it is an allocation we know is safe to privatize, for now that
5009  // means we only allow alloca instructions.
5010  // TODO: We can additionally analyze the accesses in the callee to create
5011  // the type from that information instead. That is a little more
5012  // involved and will be done in a follow up patch.
5013  auto CallSiteCheck = [&](AbstractCallSite ACS) {
5014  IRPosition ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo);
5015  // Check if a coresponding argument was found or if it is one not
5016  // associated (which can happen for callback calls).
5017  if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
5018  return false;
5019 
5020  // Check that all call sites agree on a type.
5021  auto &PrivCSArgAA = A.getAAFor<AAPrivatizablePtr>(*this, ACSArgPos);
5022  Optional<Type *> CSTy = PrivCSArgAA.getPrivatizableType();
5023 
5024  LLVM_DEBUG({
5025  dbgs() << "[AAPrivatizablePtr] ACSPos: " << ACSArgPos << ", CSTy: ";
5026  if (CSTy.hasValue() && CSTy.getValue())
5027  CSTy.getValue()->print(dbgs());
5028  else if (CSTy.hasValue())
5029  dbgs() << "<nullptr>";
5030  else
5031  dbgs() << "<none>";
5032  });
5033 
5034  Ty = combineTypes(Ty, CSTy);
5035 
5036  LLVM_DEBUG({
5037  dbgs() << " : New Type: ";
5038  if (Ty.hasValue() && Ty.getValue())
5039  Ty.getValue()->print(dbgs());
5040  else if (Ty.hasValue())
5041  dbgs() << "<nullptr>";
5042  else
5043  dbgs() << "<none>";
5044  dbgs() << "\n";
5045  });
5046 
5047  return !Ty.hasValue() || Ty.getValue();
5048  };
5049 
5050  if (!A.checkForAllCallSites(CallSiteCheck, *this, true, AllCallSitesKnown))
5051  return nullptr;
5052  return Ty;
5053  }
5054 
5055  /// See AbstractAttribute::updateImpl(...).
5056  ChangeStatus updateImpl(Attributor &A) override {
5057  PrivatizableType = identifyPrivatizableType(A);
5058  if (!PrivatizableType.hasValue())
5059  return ChangeStatus::UNCHANGED;
5060  if (!PrivatizableType.getValue())
5061  return indicatePessimisticFixpoint();
5062 
5063  // The dependence is optional so we don't give up once we give up on the
5064  // alignment.
5065  A.getAAFor<AAAlign>(*this, IRPosition::value(getAssociatedValue()),
5066  /* TrackDependence */ true, DepClassTy::OPTIONAL);
5067 
5068  // Avoid arguments with padding for now.
5069  if (!getIRPosition().hasAttr(Attribute::ByVal) &&
5070  !ArgumentPromotionPass::isDenselyPacked(PrivatizableType.getValue(),
5071  A.getInfoCache().getDL())) {
5072  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] Padding detected\n");
5073  return indicatePessimisticFixpoint();
5074  }
5075 
5076  // Verify callee and caller agree on how the promoted argument would be
5077  // passed.
5078  // TODO: The use of the ArgumentPromotion interface here is ugly, we need a
5079  // specialized form of TargetTransformInfo::areFunctionArgsABICompatible
5080  // which doesn't require the arguments ArgumentPromotion wanted to pass.
5081  Function &Fn = *getIRPosition().getAnchorScope();
5082  SmallPtrSet<Argument *, 1> ArgsToPromote, Dummy;
5083  ArgsToPromote.insert(getAssociatedArgument());
5084  const auto *TTI =
5086  if (!TTI ||
5088  Fn, *TTI, ArgsToPromote, Dummy) ||
5089  ArgsToPromote.empty()) {
5090  LLVM_DEBUG(
5091  dbgs() << "[AAPrivatizablePtr] ABI incompatibility detected for "
5092  << Fn.getName() << "\n");
5093  return indicatePessimisticFixpoint();
5094  }
5095 
5096  // Collect the types that will replace the privatizable type in the function
5097  // signature.
5098  SmallVector<Type *, 16> ReplacementTypes;
5099  identifyReplacementTypes(PrivatizableType.getValue(), ReplacementTypes);
5100 
5101  // Register a rewrite of the argument.
5102  Argument *Arg = getAssociatedArgument();
5103  if (!A.isValidFunctionSignatureRewrite(*Arg, ReplacementTypes)) {
5104  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] Rewrite not valid\n");
5105  return indicatePessimisticFixpoint();
5106  }
5107 
5108  unsigned ArgNo = Arg->getArgNo();
5109 
5110  // Helper to check if for the given call site the associated argument is
5111  // passed to a callback where the privatization would be different.
5112  auto IsCompatiblePrivArgOfCallback = [&](CallBase &CB) {
5113  SmallVector<const Use *, 4> CallbackUses;
5114  AbstractCallSite::getCallbackUses(CB, CallbackUses);
5115  for (const Use *U : CallbackUses) {
5116  AbstractCallSite CBACS(U);
5117  assert(CBACS && CBACS.isCallbackCall());
5118  for (Argument &CBArg : CBACS.getCalledFunction()->args()) {
5119  int CBArgNo = CBACS.getCallArgOperandNo(CBArg);
5120 
5121  LLVM_DEBUG({
5122  dbgs()
5123  << "[AAPrivatizablePtr] Argument " << *Arg
5124  << "check if can be privatized in the context of its parent ("
5125  << Arg->getParent()->getName()
5126  << ")\n[AAPrivatizablePtr] because it is an argument in a "
5127  "callback ("
5128  << CBArgNo << "@" << CBACS.getCalledFunction()->getName()
5129  << ")\n[AAPrivatizablePtr] " << CBArg << " : "
5130  << CBACS.getCallArgOperand(CBArg) << " vs "
5131  << CB.getArgOperand(ArgNo) << "\n"
5132  << "[AAPrivatizablePtr] " << CBArg << " : "
5133  << CBACS.getCallArgOperandNo(CBArg) << " vs " << ArgNo << "\n";
5134  });
5135 
5136  if (CBArgNo != int(ArgNo))
5137  continue;
5138  const auto &CBArgPrivAA =
5140  if (CBArgPrivAA.isValidState()) {
5141  auto CBArgPrivTy = CBArgPrivAA.getPrivatizableType();
5142  if (!CBArgPrivTy.hasValue())
5143  continue;
5144  if (CBArgPrivTy.getValue() == PrivatizableType)
5145  continue;
5146  }
5147 
5148  LLVM_DEBUG({
5149  dbgs() << "[AAPrivatizablePtr] Argument " << *Arg
5150  << " cannot be privatized in the context of its parent ("
5151  << Arg->getParent()->getName()
5152  << ")\n[AAPrivatizablePtr] because it is an argument in a "
5153  "callback ("
5154  << CBArgNo << "@" << CBACS.getCalledFunction()->getName()
5155  << ").\n[AAPrivatizablePtr] for which the argument "
5156  "privatization is not compatible.\n";
5157  });
5158  return false;
5159  }
5160  }
5161  return true;
5162  };
5163 
5164  // Helper to check if for the given call site the associated argument is
5165  // passed to a direct call where the privatization would be different.
5166  auto IsCompatiblePrivArgOfDirectCS = [&](AbstractCallSite ACS) {
5167  CallBase *DC = cast<CallBase>(ACS.getInstruction());
5168  int DCArgNo = ACS.getCallArgOperandNo(ArgNo);
5169  assert(DCArgNo >= 0 && unsigned(DCArgNo) < DC->getNumArgOperands() &&
5170  "Expected a direct call operand for callback call operand");
5171 
5172  LLVM_DEBUG({
5173  dbgs() << "[AAPrivatizablePtr] Argument " << *Arg
5174  << " check if be privatized in the context of its parent ("
5175  << Arg->getParent()->getName()
5176  << ")\n[AAPrivatizablePtr] because it is an argument in a "
5177  "direct call of ("
5178  << DCArgNo << "@" << DC->getCalledFunction()->getName()
5179  << ").\n";
5180  });
5181 
5182  Function *DCCallee = DC->getCalledFunction();
5183  if (unsigned(DCArgNo) < DCCallee->arg_size()) {
5184  const auto &DCArgPrivAA = A.getAAFor<AAPrivatizablePtr>(
5185  *this, IRPosition::argument(*DCCallee->getArg(DCArgNo)));
5186  if (DCArgPrivAA.isValidState()) {
5187  auto DCArgPrivTy = DCArgPrivAA.getPrivatizableType();
5188  if (!DCArgPrivTy.hasValue())
5189  return true;
5190  if (DCArgPrivTy.getValue() == PrivatizableType)
5191  return true;
5192  }
5193  }
5194 
5195  LLVM_DEBUG({
5196  dbgs() << "[AAPrivatizablePtr] Argument " << *Arg
5197  << " cannot be privatized in the context of its parent ("
5198  << Arg->getParent()->getName()
5199  << ")\n[AAPrivatizablePtr] because it is an argument in a "
5200  "direct call of ("
5201  << ACS.getInstruction()->getCalledFunction()->getName()
5202  << ").\n[AAPrivatizablePtr] for which the argument "
5203  "privatization is not compatible.\n";
5204  });
5205  return false;
5206  };
5207 
5208  // Helper to check if the associated argument is used at the given abstract
5209  // call site in a way that is incompatible with the privatization assumed
5210  // here.
5211  auto IsCompatiblePrivArgOfOtherCallSite = [&](AbstractCallSite ACS) {
5212  if (ACS.isDirectCall())
5213  return IsCompatiblePrivArgOfCallback(*ACS.getInstruction());
5214  if (ACS.isCallbackCall())
5215  return IsCompatiblePrivArgOfDirectCS(ACS);
5216  return false;
5217  };
5218 
5219  bool AllCallSitesKnown;
5220  if (!A.checkForAllCallSites(IsCompatiblePrivArgOfOtherCallSite, *this, true,
5221  AllCallSitesKnown))
5222  return indicatePessimisticFixpoint();
5223 
5224  return ChangeStatus::UNCHANGED;
5225  }
5226 
5227  /// Given a type to private \p PrivType, collect the constituates (which are
5228  /// used) in \p ReplacementTypes.
5229  static void
5230  identifyReplacementTypes(Type *PrivType,
5231  SmallVectorImpl<Type *> &ReplacementTypes) {
5232  // TODO: For now we expand the privatization type to the fullest which can
5233  // lead to dead arguments that need to be removed later.
5234  assert(PrivType && "Expected privatizable type!");
5235 
5236  // Traverse the type, extract constituate types on the outermost level.
5237  if (auto *PrivStructType = dyn_cast<StructType>(PrivType)) {
5238  for (unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++)
5239  ReplacementTypes.push_back(PrivStructType->getElementType(u));
5240  } else if (auto *PrivArrayType = dyn_cast<ArrayType>(PrivType)) {
5241  ReplacementTypes.append(PrivArrayType->getNumElements(),
5242  PrivArrayType->getElementType());
5243  } else {
5244  ReplacementTypes.push_back(PrivType);
5245  }
5246  }
5247 
5248  /// Initialize \p Base according to the type \p PrivType at position \p IP.
5249  /// The values needed are taken from the arguments of \p F starting at
5250  /// position \p ArgNo.
5251  static void createInitialization(Type *PrivType, Value &Base, Function &F,
5252  unsigned ArgNo, Instruction &IP) {
5253  assert(PrivType && "Expected privatizable type!");
5254 
5255  IRBuilder<NoFolder> IRB(&IP);
5256  const DataLayout &DL = F.getParent()->getDataLayout();
5257 
5258  // Traverse the type, build GEPs and stores.
5259  if (auto *PrivStructType = dyn_cast<StructType>(PrivType)) {
5260  const StructLayout *PrivStructLayout = DL.getStructLayout(PrivStructType);
5261  for (unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++) {
5262  Type *PointeeTy = PrivStructType->getElementType(u)->getPointerTo();
5263  Value *Ptr = constructPointer(
5264  PointeeTy, &Base, PrivStructLayout->getElementOffset(u), IRB, DL);
5265  new StoreInst(F.getArg(ArgNo + u), Ptr, &IP);
5266  }
5267  } else if (auto *PrivArrayType = dyn_cast<ArrayType>(PrivType)) {
5268  Type *PointeePtrTy = PrivArrayType->getElementType()->getPointerTo();
5269  uint64_t PointeeTySize = DL.getTypeStoreSize(PointeePtrTy);
5270  for (unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) {
5271  Value *Ptr =
5272  constructPointer(PointeePtrTy, &Base, u * PointeeTySize, IRB, DL);
5273  new StoreInst(F.getArg(ArgNo + u), Ptr, &IP);
5274  }
5275  } else {
5276  new StoreInst(F.getArg(ArgNo), &Base, &IP);
5277  }
5278  }
5279 
5280  /// Extract values from \p Base according to the type \p PrivType at the
5281  /// call position \p ACS. The values are appended to \p ReplacementValues.
5282  void createReplacementValues(Align Alignment, Type *PrivType,
5283  AbstractCallSite ACS, Value *Base,
5284  SmallVectorImpl<Value *> &ReplacementValues) {
5285  assert(Base && "Expected base value!");
5286  assert(PrivType && "Expected privatizable type!");
5287  Instruction *IP = ACS.getInstruction();
5288 
5289  IRBuilder<NoFolder> IRB(IP);
5290  const DataLayout &DL = IP->getModule()->getDataLayout();
5291 
5292  if (Base->getType()->getPointerElementType() != PrivType)
5293  Base = BitCastInst::CreateBitOrPointerCast(Base, PrivType->getPointerTo(),
5294  "", ACS.getInstruction());
5295 
5296  // Traverse the type, build GEPs and loads.
5297  if (auto *PrivStructType = dyn_cast<StructType>(PrivType)) {
5298  const StructLayout *PrivStructLayout = DL.getStructLayout(PrivStructType);
5299  for (unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++) {
5300  Type *PointeeTy = PrivStructType->getElementType(u);
5301  Value *Ptr =
5302  constructPointer(PointeeTy->getPointerTo(), Base,
5303  PrivStructLayout->getElementOffset(u), IRB, DL);
5304  LoadInst *L = new LoadInst(PointeeTy, Ptr, "", IP);
5305  L->setAlignment(Alignment);
5306  ReplacementValues.push_back(L);
5307  }
5308  } else if (auto *PrivArrayType = dyn_cast<ArrayType>(PrivType)) {
5309  Type *PointeeTy = PrivArrayType->getElementType();
5310  uint64_t PointeeTySize = DL.getTypeStoreSize(PointeeTy);
5311  Type *PointeePtrTy = PointeeTy->getPointerTo();
5312  for (unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) {
5313  Value *Ptr =
5314  constructPointer(PointeePtrTy, Base, u * PointeeTySize, IRB, DL);
5315  LoadInst *L = new LoadInst(PointeePtrTy, Ptr, "", IP);
5316  L->setAlignment(Alignment);
5317  ReplacementValues.push_back(L);
5318  }
5319  } else {
5320  LoadInst *L = new LoadInst(PrivType, Base, "", IP);
5321  L->setAlignment(Alignment);
5322  ReplacementValues.push_back(L);
5323  }
5324  }
5325 
5326  /// See AbstractAttribute::manifest(...)
5327  ChangeStatus manifest(Attributor &A) override {
5328  if (!PrivatizableType.hasValue())
5329  return ChangeStatus::UNCHANGED;
5330  assert(PrivatizableType.getValue() && "Expected privatizable type!");
5331 
5332  // Collect all tail calls in the function as we cannot allow new allocas to
5333  // escape into tail recursion.
5334  // TODO: Be smarter about new allocas escaping into tail calls.
5335  SmallVector<CallInst *, 16> TailCalls;
5336  if (!A.checkForAllInstructions(
5337  [&](Instruction &I) {
5338  CallInst &CI = cast<CallInst>(I);
5339  if (CI.isTailCall())
5340  TailCalls.push_back(&CI);
5341  return true;
5342  },
5343  *this, {Instruction::Call}))
5344  return ChangeStatus::UNCHANGED;
5345 
5346  Argument *Arg = getAssociatedArgument();
5347  // Query AAAlign attribute for alignment of associated argument to
5348  // determine the best alignment of loads.
5349  const auto &AlignAA = A.getAAFor<AAAlign>(*this, IRPosition::value(*Arg));
5350 
5351  // Callback to repair the associated function. A new alloca is placed at the
5352  // beginning and initialized with the values passed through arguments. The
5353  // new alloca replaces the use of the old pointer argument.
5355  [=](const Attributor::ArgumentReplacementInfo &ARI,
5356  Function &ReplacementFn, Function::arg_iterator ArgIt) {
5357  BasicBlock &EntryBB = ReplacementFn.getEntryBlock();
5358  Instruction *IP = &*EntryBB.getFirstInsertionPt();
5359  auto *AI = new AllocaInst(PrivatizableType.getValue(), 0,
5360  Arg->getName() + ".priv", IP);
5361  createInitialization(PrivatizableType.getValue(), *AI, ReplacementFn,
5362  ArgIt->getArgNo(), *IP);
5363  Arg->replaceAllUsesWith(AI);
5364 
5365  for (CallInst *CI : TailCalls)
5366  CI->setTailCall(false);
5367  };
5368 
5369  // Callback to repair a call site of the associated function. The elements
5370  // of the privatizable type are loaded prior to the call and passed to the
5371  // new function version.
5373  [=, &AlignAA](const Attributor::ArgumentReplacementInfo &ARI,
5374  AbstractCallSite ACS,
5375  SmallVectorImpl<Value *> &NewArgOperands) {
5376  // When no alignment is specified for the load instruction,
5377  // natural alignment is assumed.
5378  createReplacementValues(
5379  assumeAligned(AlignAA.getAssumedAlign()),
5380  PrivatizableType.getValue(), ACS,
5381  ACS.getCallArgOperand(ARI.getReplacedArg().getArgNo()),
5382  NewArgOperands);
5383  };
5384 
5385  // Collect the types that will replace the privatizable type in the function
5386  // signature.
5387  SmallVector<Type *, 16> ReplacementTypes;
5388  identifyReplacementTypes(PrivatizableType.getValue(), ReplacementTypes);
5389 
5390  // Register a rewrite of the argument.
5391  if (A.registerFunctionSignatureRewrite(*Arg, ReplacementTypes,
5392  std::move(FnRepairCB),
5393  std::move(ACSRepairCB)))
5394  return ChangeStatus::CHANGED;
5395  return ChangeStatus::UNCHANGED;
5396  }
5397 
5398  /// See AbstractAttribute::trackStatistics()
5399  void trackStatistics() const override {
5400  STATS_DECLTRACK_ARG_ATTR(privatizable_ptr);
5401  }
5402 };
5403 
5404 struct AAPrivatizablePtrFloating : public AAPrivatizablePtrImpl {
5405  AAPrivatizablePtrFloating(const IRPosition &IRP, Attributor &A)
5406  : AAPrivatizablePtrImpl(IRP, A) {}
5407 
5408  /// See AbstractAttribute::initialize(...).
5409  virtual void initialize(Attributor &A) override {
5410  // TODO: We can privatize more than arguments.
5411  indicatePessimisticFixpoint();
5412  }
5413 
5414  ChangeStatus updateImpl(Attributor &A) override {
5415  llvm_unreachable("AAPrivatizablePtr(Floating|Returned|CallSiteReturned)::"
5416  "updateImpl will not be called");
5417  }
5418 
5419  /// See AAPrivatizablePtrImpl::identifyPrivatizableType(...)
5420  Optional<Type *> identifyPrivatizableType(Attributor &A) override {
5421  Value *Obj =
5422  GetUnderlyingObject(&getAssociatedValue(), A.getInfoCache().getDL());
5423  if (!Obj) {
5424  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] No underlying object found!\n");
5425  return nullptr;
5426  }
5427 
5428  if (auto *AI = dyn_cast<AllocaInst>(Obj))
5429  if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize()))
5430  if (CI->isOne())
5431  return Obj->getType()->getPointerElementType();
5432  if (auto *Arg = dyn_cast<Argument>(Obj)) {
5433  auto &PrivArgAA =
5435  if (PrivArgAA.isAssumedPrivatizablePtr())
5436  return Obj->getType()->getPointerElementType();
5437  }
5438 
5439  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] Underlying object neither valid "
5440  "alloca nor privatizable argument: "
5441  << *Obj << "!\n");
5442  return nullptr;
5443  }
5444 
5445  /// See AbstractAttribute::trackStatistics()
5446  void trackStatistics() const override {
5447  STATS_DECLTRACK_FLOATING_ATTR(privatizable_ptr);
5448  }
5449 };
5450 
5451 struct AAPrivatizablePtrCallSiteArgument final
5452  : public AAPrivatizablePtrFloating {
5453  AAPrivatizablePtrCallSiteArgument(const IRPosition &IRP, Attributor &A)
5454  : AAPrivatizablePtrFloating(IRP, A) {}
5455 
5456  /// See AbstractAttribute::initialize(...).
5457  void initialize(Attributor &A) override {
5458  if (getIRPosition().hasAttr(Attribute::ByVal))
5459  indicateOptimisticFixpoint();
5460  }
5461 
5462  /// See AbstractAttribute::updateImpl(...).
5463  ChangeStatus updateImpl(Attributor &A) override {
5464  PrivatizableType = identifyPrivatizableType(A);
5465  if (!PrivatizableType.hasValue())
5466  return ChangeStatus::UNCHANGED;
5467  if (!PrivatizableType.getValue())
5468  return indicatePessimisticFixpoint();
5469 
5470  const IRPosition &IRP = getIRPosition();
5471  auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP);
5472  if (!NoCaptureAA.isAssumedNoCapture()) {
5473  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] pointer might be captured!\n");
5474  return indicatePessimisticFixpoint();
5475  }
5476 
5477  auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, IRP);
5478  if (!NoAliasAA.isAssumedNoAlias()) {
5479  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] pointer might alias!\n");
5480  return indicatePessimisticFixpoint();
5481  }
5482 
5483  const auto &MemBehaviorAA = A.getAAFor<AAMemoryBehavior>(*this, IRP);
5484  if (!MemBehaviorAA.isAssumedReadOnly()) {
5485  LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] pointer is written!\n");
5486  return indicatePessimisticFixpoint();
5487  }
5488 
5489  return ChangeStatus::UNCHANGED;
5490  }
5491 
5492  /// See AbstractAttribute::trackStatistics()
5493  void trackStatistics() const override {
5494  STATS_DECLTRACK_CSARG_ATTR(privatizable_ptr);
5495  }
5496 };
5497 
5498 struct AAPrivatizablePtrCallSiteReturned final
5499  : public AAPrivatizablePtrFloating {
5500  AAPrivatizablePtrCallSiteReturned(const IRPosition &IRP, Attributor &A)
5501  : AAPrivatizablePtrFloating(IRP, A) {}
5502 
5503  /// See AbstractAttribute::initialize(...).
5504  void initialize(Attributor &A) override {
5505  // TODO: We can privatize more than arguments.
5506  indicatePessimisticFixpoint();
5507  }
5508 
5509  /// See AbstractAttribute::trackStatistics()
5510  void trackStatistics() const override {
5511  STATS_DECLTRACK_CSRET_ATTR(privatizable_ptr);
5512  }
5513 };
5514 
5515 struct AAPrivatizablePtrReturned final : public AAPrivatizablePtrFloating {
5516  AAPrivatizablePtrReturned(const IRPosition &IRP, Attributor &A)
5517  : AAPrivatizablePtrFloating(IRP, A) {}
5518 
5519  /// See AbstractAttribute::initialize(...).
5520  void initialize(Attributor &A) override {
5521  // TODO: We can privatize more than arguments.
5522  indicatePessimisticFixpoint();
5523  }
5524 
5525  /// See AbstractAttribute::trackStatistics()
5526  void trackStatistics() const override {
5527  STATS_DECLTRACK_FNRET_ATTR(privatizable_ptr);
5528  }
5529 };
5530 
5531 /// -------------------- Memory Behavior Attributes ----------------------------
5532 /// Includes read-none, read-only, and write-only.
5533 /// ----------------------------------------------------------------------------
5534 struct AAMemoryBehaviorImpl : public AAMemoryBehavior {
5535  AAMemoryBehaviorImpl(const IRPosition &IRP, Attributor &A)
5536  : AAMemoryBehavior(IRP, A) {}
5537 
5538  /// See AbstractAttribute::initialize(...).
5539  void initialize(Attributor &A) override {
5540  intersectAssumedBits(BEST_STATE);
5541  getKnownStateFromValue(getIRPosition(), getState());
5543  }
5544 
5545  /// Return the memory behavior information encoded in the IR for \p IRP.
5546  static void getKnownStateFromValue(const IRPosition &IRP,
5547  BitIntegerState &State,
5548  bool IgnoreSubsumingPositions = false) {
5550  IRP.getAttrs(AttrKinds, Attrs, IgnoreSubsumingPositions);
5551  for (const Attribute &Attr : Attrs) {
5552  switch (Attr.getKindAsEnum()) {
5553  case Attribute::ReadNone:
5554  State.addKnownBits(NO_ACCESSES);
5555  break;
5556  case Attribute::ReadOnly:
5557  State.addKnownBits(NO_WRITES);
5558  break;
5559  case Attribute::WriteOnly:
5560  State.addKnownBits(NO_READS);
5561  break;
5562  default:
5563  llvm_unreachable("Unexpected attribute!");
5564  }
5565  }
5566 
5567  if (auto *I = dyn_cast<Instruction>(&IRP.getAnchorValue())) {
5568  if (!I->mayReadFromMemory())
5569  State.addKnownBits(NO_READS);
5570  if (!I->mayWriteToMemory())
5571  State.addKnownBits(NO_WRITES);
5572  }
5573  }
5574 
5575  /// See AbstractAttribute::getDeducedAttributes(...).
5576  void getDeducedAttributes(LLVMContext &Ctx,
5577  SmallVectorImpl<Attribute> &Attrs) const override {
5578  assert(Attrs.size() == 0);
5579  if (isAssumedReadNone())
5580  Attrs.push_back(Attribute::get(Ctx, Attribute::ReadNone));
5581  else if (isAssumedReadOnly())
5582  Attrs.push_back(Attribute::get(Ctx, Attribute::ReadOnly));
5583  else if (isAssumedWriteOnly())
5584  Attrs.push_back(Attribute::get(Ctx, Attribute::WriteOnly));
5585  assert(Attrs.size() <= 1);
5586  }
5587 
5588  /// See AbstractAttribute::manifest(...).
5589  ChangeStatus manifest(Attributor &A) override {
5590  if (hasAttr(Attribute::ReadNone, /* IgnoreSubsumingPositions */ true))
5591  return ChangeStatus::UNCHANGED;
5592 
5593  const IRPosition &IRP = getIRPosition();
5594 
5595  // Check if we would improve the existing attributes first.
5596  SmallVector<Attribute, 4> DeducedAttrs;
5597  getDeducedAttributes(IRP.getAnchorValue().getContext(), DeducedAttrs);
5598  if (llvm::all_of(DeducedAttrs, [&](const Attribute &Attr) {
5599  return IRP.hasAttr(Attr.getKindAsEnum(),
5600  /* IgnoreSubsumingPositions */ true);
5601  }))
5602  return ChangeStatus::UNCHANGED;
5603 
5604  // Clear existing attributes.
5605  IRP.removeAttrs(AttrKinds);
5606 
5607  // Use the generic manifest method.
5608  return IRAttribute::manifest(A);
5609  }
5610 
5611  /// See AbstractState::getAsStr().
5612  const std::string getAsStr() const override {
5613  if (isAssumedReadNone())
5614  return "readnone";
5615  if (isAssumedReadOnly())
5616  return "readonly";
5617  if (isAssumedWriteOnly())
5618  return "writeonly";
5619  return "may-read/write";
5620  }
5621 
5622  /// The set of IR attributes AAMemoryBehavior deals with.
5623  static const Attribute::AttrKind AttrKinds[3];
5624 };
5625 
5626 const Attribute::AttrKind AAMemoryBehaviorImpl::AttrKinds[] = {
5627  Attribute::ReadNone, Attribute::ReadOnly, Attribute::WriteOnly};
5628 
5629 /// Memory behavior attribute for a floating value.
5630 struct AAMemoryBehaviorFloating : AAMemoryBehaviorImpl {
5631  AAMemoryBehaviorFloating(const IRPosition &IRP, Attributor &A)
5632  : AAMemoryBehaviorImpl(IRP, A) {}
5633 
5634  /// See AbstractAttribute::initialize(...).
5635  void initialize(Attributor &A) override {
5637  // Initialize the use vector with all direct uses of the associated value.
5638  for (const Use &U : getAssociatedValue().uses())
5639  Uses.insert(&U);
5640  }
5641 
5642  /// See AbstractAttribute::updateImpl(...).
5643  ChangeStatus updateImpl(Attributor &A) override;
5644 
5645  /// See AbstractAttribute::trackStatistics()
5646  void trackStatistics() const override {
5647  if (isAssumedReadNone())
5648