contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp

   1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements an inter procedural pass that deduces and/or propagating
  10 // attributes. This is done in an abstract interpretation style fixpoint
  11 // iteration. See the Attributor.h file comment and the class descriptions in
  12 // that file for more information.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/IPO/Attributor.h"
  17
  18 #include "llvm/ADT/DepthFirstIterator.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/GlobalsModRef.h"
  24 #include "llvm/Analysis/ValueTracking.h"
  25 #include "llvm/IR/Argument.h"
  26 #include "llvm/IR/Attributes.h"
  27 #include "llvm/IR/CFG.h"
  28 #include "llvm/IR/InstIterator.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include <cassert>
  34
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "attributor"
  38
  39 STATISTIC(NumFnWithExactDefinition,
  40           "Number of function with exact definitions");
  41 STATISTIC(NumFnWithoutExactDefinition,
  42           "Number of function without exact definitions");
  43 STATISTIC(NumAttributesTimedOut,
  44           "Number of abstract attributes timed out before fixpoint");
  45 STATISTIC(NumAttributesValidFixpoint,
  46           "Number of abstract attributes in a valid fixpoint state");
  47 STATISTIC(NumAttributesManifested,
  48           "Number of abstract attributes manifested in IR");
  49 STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind");
  50
  51 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
  52 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
  53 STATISTIC(NumFnArgumentReturned,
  54           "Number of function arguments marked returned");
  55 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
  56 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
  57 STATISTIC(NumFnReturnedNonNull,
  58           "Number of function return values marked nonnull");
  59 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
  60 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
  61 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
  62
  63 // TODO: Determine a good default value.
  64 //
  65 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
  66 // (when run with the first 5 abstract attributes). The results also indicate
  67 // that we never reach 32 iterations but always find a fixpoint sooner.
  68 //
  69 // This will become more evolved once we perform two interleaved fixpoint
  70 // iterations: bottom-up and top-down.
  71 static cl::opt<unsigned>
  72     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
  73                           cl::desc("Maximal number of fixpoint iterations."),
  74                           cl::init(32));
  75
  76 static cl::opt<bool> DisableAttributor(
  77     "attributor-disable", cl::Hidden,
  78     cl::desc("Disable the attributor inter-procedural deduction pass."),
  79     cl::init(true));
  80
  81 static cl::opt<bool> VerifyAttributor(
  82     "attributor-verify", cl::Hidden,
  83     cl::desc("Verify the Attributor deduction and "
  84              "manifestation of attributes -- may issue false-positive errors"),
  85     cl::init(false));
  86
  87 /// Logic operators for the change status enum class.
  88 ///
  89 ///{
  90 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
  91   return l == ChangeStatus::CHANGED ? l : r;
  92 }
  93 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
  94   return l == ChangeStatus::UNCHANGED ? l : r;
  95 }
  96 ///}
  97
  98 /// Helper to adjust the statistics.
  99 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
 100                         const Attribute &Attr) {
 101   if (!AreStatisticsEnabled())
 102     return;
 103
 104   if (!Attr.isEnumAttribute())
 105     return;
 106   switch (Attr.getKindAsEnum()) {
 107   case Attribute::NoUnwind:
 108     NumFnNoUnwind++;
 109     return;
 110   case Attribute::Returned:
 111     NumFnArgumentReturned++;
 112     return;
 113   case Attribute::NoSync:
 114     NumFnNoSync++;
 115     break;
 116   case Attribute::NoFree:
 117     NumFnNoFree++;
 118     break;
 119   case Attribute::NonNull:
 120     switch (MP) {
 121     case AbstractAttribute::MP_RETURNED:
 122       NumFnReturnedNonNull++;
 123       break;
 124     case AbstractAttribute::MP_ARGUMENT:
 125       NumFnArgumentNonNull++;
 126       break;
 127     case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 128       NumCSArgumentNonNull++;
 129       break;
 130     default:
 131       break;
 132     }
 133     break;
 134   case Attribute::WillReturn:
 135     NumFnWillReturn++;
 136     break;
 137   default:
 138     return;
 139   }
 140 }
 141
 142 template <typename StateTy>
 143 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
 144 template <typename StateTy>
 145 using visitValueCB_t = std::function<void(Value *, StateTy &State)>;
 146
 147 /// Recursively visit all values that might become \p InitV at some point. This
 148 /// will be done by looking through cast instructions, selects, phis, and calls
 149 /// with the "returned" attribute. The callback \p FollowValueCB is asked before
 150 /// a potential origin value is looked at. If no \p FollowValueCB is passed, a
 151 /// default one is used that will make sure we visit every value only once. Once
 152 /// we cannot look through the value any further, the callback \p VisitValueCB
 153 /// is invoked and passed the current value and the \p State. To limit how much
 154 /// effort is invested, we will never visit more than \p MaxValues values.
 155 template <typename StateTy>
 156 static bool genericValueTraversal(
 157     Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
 158     followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
 159
 160   SmallPtrSet<Value *, 16> Visited;
 161   followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
 162     return Visited.insert(Val).second;
 163   };
 164
 165   if (!FollowValueCB)
 166     FollowValueCB = &DefaultFollowValueCB;
 167
 168   SmallVector<Value *, 16> Worklist;
 169   Worklist.push_back(InitV);
 170
 171   int Iteration = 0;
 172   do {
 173     Value *V = Worklist.pop_back_val();
 174
 175     // Check if we should process the current value. To prevent endless
 176     // recursion keep a record of the values we followed!
 177     if (!(*FollowValueCB)(V, State))
 178       continue;
 179
 180     // Make sure we limit the compile time for complex expressions.
 181     if (Iteration++ >= MaxValues)
 182       return false;
 183
 184     // Explicitly look through calls with a "returned" attribute if we do
 185     // not have a pointer as stripPointerCasts only works on them.
 186     if (V->getType()->isPointerTy()) {
 187       V = V->stripPointerCasts();
 188     } else {
 189       CallSite CS(V);
 190       if (CS && CS.getCalledFunction()) {
 191         Value *NewV = nullptr;
 192         for (Argument &Arg : CS.getCalledFunction()->args())
 193           if (Arg.hasReturnedAttr()) {
 194             NewV = CS.getArgOperand(Arg.getArgNo());
 195             break;
 196           }
 197         if (NewV) {
 198           Worklist.push_back(NewV);
 199           continue;
 200         }
 201       }
 202     }
 203
 204     // Look through select instructions, visit both potential values.
 205     if (auto *SI = dyn_cast<SelectInst>(V)) {
 206       Worklist.push_back(SI->getTrueValue());
 207       Worklist.push_back(SI->getFalseValue());
 208       continue;
 209     }
 210
 211     // Look through phi nodes, visit all operands.
 212     if (auto *PHI = dyn_cast<PHINode>(V)) {
 213       Worklist.append(PHI->op_begin(), PHI->op_end());
 214       continue;
 215     }
 216
 217     // Once a leaf is reached we inform the user through the callback.
 218     VisitValueCB(V, State);
 219   } while (!Worklist.empty());
 220
 221   // All values have been visited.
 222   return true;
 223 }
 224
 225 /// Helper to identify the correct offset into an attribute list.
 226 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
 227                              unsigned ArgNo = 0) {
 228   switch (MP) {
 229   case AbstractAttribute::MP_ARGUMENT:
 230   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 231     return ArgNo + AttributeList::FirstArgIndex;
 232   case AbstractAttribute::MP_FUNCTION:
 233     return AttributeList::FunctionIndex;
 234   case AbstractAttribute::MP_RETURNED:
 235     return AttributeList::ReturnIndex;
 236   }
 237   llvm_unreachable("Unknown manifest position!");
 238 }
 239
 240 /// Return true if \p New is equal or worse than \p Old.
 241 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
 242   if (!Old.isIntAttribute())
 243     return true;
 244
 245   return Old.getValueAsInt() >= New.getValueAsInt();
 246 }
 247
 248 /// Return true if the information provided by \p Attr was added to the
 249 /// attribute list \p Attrs. This is only the case if it was not already present
 250 /// in \p Attrs at the position describe by \p MP and \p ArgNo.
 251 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
 252                              AttributeList &Attrs,
 253                              AbstractAttribute::ManifestPosition MP,
 254                              unsigned ArgNo = 0) {
 255   unsigned AttrIdx = getAttrIndex(MP, ArgNo);
 256
 257   if (Attr.isEnumAttribute()) {
 258     Attribute::AttrKind Kind = Attr.getKindAsEnum();
 259     if (Attrs.hasAttribute(AttrIdx, Kind))
 260       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 261         return false;
 262     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 263     return true;
 264   }
 265   if (Attr.isStringAttribute()) {
 266     StringRef Kind = Attr.getKindAsString();
 267     if (Attrs.hasAttribute(AttrIdx, Kind))
 268       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 269         return false;
 270     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 271     return true;
 272   }
 273
 274   llvm_unreachable("Expected enum or string attribute!");
 275 }
 276
 277 ChangeStatus AbstractAttribute::update(Attributor &A) {
 278   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 279   if (getState().isAtFixpoint())
 280     return HasChanged;
 281
 282   LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
 283
 284   HasChanged = updateImpl(A);
 285
 286   LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
 287                     << "\n");
 288
 289   return HasChanged;
 290 }
 291
 292 ChangeStatus AbstractAttribute::manifest(Attributor &A) {
 293   assert(getState().isValidState() &&
 294          "Attempted to manifest an invalid state!");
 295   assert(getAssociatedValue() &&
 296          "Attempted to manifest an attribute without associated value!");
 297
 298   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 299   SmallVector<Attribute, 4> DeducedAttrs;
 300   getDeducedAttributes(DeducedAttrs);
 301
 302   Function &ScopeFn = getAnchorScope();
 303   LLVMContext &Ctx = ScopeFn.getContext();
 304   ManifestPosition MP = getManifestPosition();
 305
 306   AttributeList Attrs;
 307   SmallVector<unsigned, 4> ArgNos;
 308
 309   // In the following some generic code that will manifest attributes in
 310   // DeducedAttrs if they improve the current IR. Due to the different
 311   // annotation positions we use the underlying AttributeList interface.
 312   // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
 313
 314   switch (MP) {
 315   case MP_ARGUMENT:
 316     ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
 317     Attrs = ScopeFn.getAttributes();
 318     break;
 319   case MP_FUNCTION:
 320   case MP_RETURNED:
 321     ArgNos.push_back(0);
 322     Attrs = ScopeFn.getAttributes();
 323     break;
 324   case MP_CALL_SITE_ARGUMENT: {
 325     CallSite CS(&getAnchoredValue());
 326     for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
 327       if (CS.getArgOperand(u) == getAssociatedValue())
 328         ArgNos.push_back(u);
 329     Attrs = CS.getAttributes();
 330   }
 331   }
 332
 333   for (const Attribute &Attr : DeducedAttrs) {
 334     for (unsigned ArgNo : ArgNos) {
 335       if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
 336         continue;
 337
 338       HasChanged = ChangeStatus::CHANGED;
 339       bookkeeping(MP, Attr);
 340     }
 341   }
 342
 343   if (HasChanged == ChangeStatus::UNCHANGED)
 344     return HasChanged;
 345
 346   switch (MP) {
 347   case MP_ARGUMENT:
 348   case MP_FUNCTION:
 349   case MP_RETURNED:
 350     ScopeFn.setAttributes(Attrs);
 351     break;
 352   case MP_CALL_SITE_ARGUMENT:
 353     CallSite(&getAnchoredValue()).setAttributes(Attrs);
 354   }
 355
 356   return HasChanged;
 357 }
 358
 359 Function &AbstractAttribute::getAnchorScope() {
 360   Value &V = getAnchoredValue();
 361   if (isa<Function>(V))
 362     return cast<Function>(V);
 363   if (isa<Argument>(V))
 364     return *cast<Argument>(V).getParent();
 365   if (isa<Instruction>(V))
 366     return *cast<Instruction>(V).getFunction();
 367   llvm_unreachable("No scope for anchored value found!");
 368 }
 369
 370 const Function &AbstractAttribute::getAnchorScope() const {
 371   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 372 }
 373
 374 /// -----------------------NoUnwind Function Attribute--------------------------
 375
 376 struct AANoUnwindFunction : AANoUnwind, BooleanState {
 377
 378   AANoUnwindFunction(Function &F, InformationCache &InfoCache)
 379       : AANoUnwind(F, InfoCache) {}
 380
 381   /// See AbstractAttribute::getState()
 382   /// {
 383   AbstractState &getState() override { return *this; }
 384   const AbstractState &getState() const override { return *this; }
 385   /// }
 386
 387   /// See AbstractAttribute::getManifestPosition().
 388   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 389
 390   const std::string getAsStr() const override {
 391     return getAssumed() ? "nounwind" : "may-unwind";
 392   }
 393
 394   /// See AbstractAttribute::updateImpl(...).
 395   ChangeStatus updateImpl(Attributor &A) override;
 396
 397   /// See AANoUnwind::isAssumedNoUnwind().
 398   bool isAssumedNoUnwind() const override { return getAssumed(); }
 399
 400   /// See AANoUnwind::isKnownNoUnwind().
 401   bool isKnownNoUnwind() const override { return getKnown(); }
 402 };
 403
 404 ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
 405   Function &F = getAnchorScope();
 406
 407   // The map from instruction opcodes to those instructions in the function.
 408   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 409   auto Opcodes = {
 410       (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
 411       (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
 412       (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
 413
 414   for (unsigned Opcode : Opcodes) {
 415     for (Instruction *I : OpcodeInstMap[Opcode]) {
 416       if (!I->mayThrow())
 417         continue;
 418
 419       auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
 420
 421       if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
 422         indicatePessimisticFixpoint();
 423         return ChangeStatus::CHANGED;
 424       }
 425     }
 426   }
 427   return ChangeStatus::UNCHANGED;
 428 }
 429
 430 /// --------------------- Function Return Values -------------------------------
 431
 432 /// "Attribute" that collects all potential returned values and the return
 433 /// instructions that they arise from.
 434 ///
 435 /// If there is a unique returned value R, the manifest method will:
 436 ///   - mark R with the "returned" attribute, if R is an argument.
 437 class AAReturnedValuesImpl final : public AAReturnedValues, AbstractState {
 438
 439   /// Mapping of values potentially returned by the associated function to the
 440   /// return instructions that might return them.
 441   DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> ReturnedValues;
 442
 443   /// State flags
 444   ///
 445   ///{
 446   bool IsFixed;
 447   bool IsValidState;
 448   bool HasOverdefinedReturnedCalls;
 449   ///}
 450
 451   /// Collect values that could become \p V in the set \p Values, each mapped to
 452   /// \p ReturnInsts.
 453   void collectValuesRecursively(
 454       Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
 455       DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> &Values) {
 456
 457     visitValueCB_t<bool> VisitValueCB = [&](Value *Val, bool &) {
 458       assert(!isa<Instruction>(Val) ||
 459              &getAnchorScope() == cast<Instruction>(Val)->getFunction());
 460       Values[Val].insert(ReturnInsts.begin(), ReturnInsts.end());
 461     };
 462
 463     bool UnusedBool;
 464     bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
 465
 466     // If we did abort the above traversal we haven't see all the values.
 467     // Consequently, we cannot know if the information we would derive is
 468     // accurate so we give up early.
 469     if (!Success)
 470       indicatePessimisticFixpoint();
 471   }
 472
 473 public:
 474   /// See AbstractAttribute::AbstractAttribute(...).
 475   AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
 476       : AAReturnedValues(F, InfoCache) {
 477     // We do not have an associated argument yet.
 478     AssociatedVal = nullptr;
 479   }
 480
 481   /// See AbstractAttribute::initialize(...).
 482   void initialize(Attributor &A) override {
 483     // Reset the state.
 484     AssociatedVal = nullptr;
 485     IsFixed = false;
 486     IsValidState = true;
 487     HasOverdefinedReturnedCalls = false;
 488     ReturnedValues.clear();
 489
 490     Function &F = cast<Function>(getAnchoredValue());
 491
 492     // The map from instruction opcodes to those instructions in the function.
 493     auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 494
 495     // Look through all arguments, if one is marked as returned we are done.
 496     for (Argument &Arg : F.args()) {
 497       if (Arg.hasReturnedAttr()) {
 498
 499         auto &ReturnInstSet = ReturnedValues[&Arg];
 500         for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
 501           ReturnInstSet.insert(cast<ReturnInst>(RI));
 502
 503         indicateOptimisticFixpoint();
 504         return;
 505       }
 506     }
 507
 508     // If no argument was marked as returned we look at all return instructions
 509     // and collect potentially returned values.
 510     for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) {
 511       SmallPtrSet<ReturnInst *, 1> RISet({cast<ReturnInst>(RI)});
 512       collectValuesRecursively(A, cast<ReturnInst>(RI)->getReturnValue(), RISet,
 513                                ReturnedValues);
 514     }
 515   }
 516
 517   /// See AbstractAttribute::manifest(...).
 518   ChangeStatus manifest(Attributor &A) override;
 519
 520   /// See AbstractAttribute::getState(...).
 521   AbstractState &getState() override { return *this; }
 522
 523   /// See AbstractAttribute::getState(...).
 524   const AbstractState &getState() const override { return *this; }
 525
 526   /// See AbstractAttribute::getManifestPosition().
 527   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
 528
 529   /// See AbstractAttribute::updateImpl(Attributor &A).
 530   ChangeStatus updateImpl(Attributor &A) override;
 531
 532   /// Return the number of potential return values, -1 if unknown.
 533   size_t getNumReturnValues() const {
 534     return isValidState() ? ReturnedValues.size() : -1;
 535   }
 536
 537   /// Return an assumed unique return value if a single candidate is found. If
 538   /// there cannot be one, return a nullptr. If it is not clear yet, return the
 539   /// Optional::NoneType.
 540   Optional<Value *> getAssumedUniqueReturnValue() const;
 541
 542   /// See AbstractState::checkForallReturnedValues(...).
 543   bool
 544   checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
 545
 546   /// Pretty print the attribute similar to the IR representation.
 547   const std::string getAsStr() const override;
 548
 549   /// See AbstractState::isAtFixpoint().
 550   bool isAtFixpoint() const override { return IsFixed; }
 551
 552   /// See AbstractState::isValidState().
 553   bool isValidState() const override { return IsValidState; }
 554
 555   /// See AbstractState::indicateOptimisticFixpoint(...).
 556   void indicateOptimisticFixpoint() override {
 557     IsFixed = true;
 558     IsValidState &= true;
 559   }
 560   void indicatePessimisticFixpoint() override {
 561     IsFixed = true;
 562     IsValidState = false;
 563   }
 564 };
 565
 566 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
 567   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 568
 569   // Bookkeeping.
 570   assert(isValidState());
 571   NumFnKnownReturns++;
 572
 573   // Check if we have an assumed unique return value that we could manifest.
 574   Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
 575
 576   if (!UniqueRV.hasValue() || !UniqueRV.getValue())
 577     return Changed;
 578
 579   // Bookkeeping.
 580   NumFnUniqueReturned++;
 581
 582   // If the assumed unique return value is an argument, annotate it.
 583   if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
 584     AssociatedVal = UniqueRVArg;
 585     Changed = AbstractAttribute::manifest(A) | Changed;
 586   }
 587
 588   return Changed;
 589 }
 590
 591 const std::string AAReturnedValuesImpl::getAsStr() const {
 592   return (isAtFixpoint() ? "returns(#" : "may-return(#") +
 593          (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
 594 }
 595
 596 Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue() const {
 597   // If checkForallReturnedValues provides a unique value, ignoring potential
 598   // undef values that can also be present, it is assumed to be the actual
 599   // return value and forwarded to the caller of this method. If there are
 600   // multiple, a nullptr is returned indicating there cannot be a unique
 601   // returned value.
 602   Optional<Value *> UniqueRV;
 603
 604   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
 605     // If we found a second returned value and neither the current nor the saved
 606     // one is an undef, there is no unique returned value. Undefs are special
 607     // since we can pretend they have any value.
 608     if (UniqueRV.hasValue() && UniqueRV != &RV &&
 609         !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
 610       UniqueRV = nullptr;
 611       return false;
 612     }
 613
 614     // Do not overwrite a value with an undef.
 615     if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
 616       UniqueRV = &RV;
 617
 618     return true;
 619   };
 620
 621   if (!checkForallReturnedValues(Pred))
 622     UniqueRV = nullptr;
 623
 624   return UniqueRV;
 625 }
 626
 627 bool AAReturnedValuesImpl::checkForallReturnedValues(
 628     std::function<bool(Value &)> &Pred) const {
 629   if (!isValidState())
 630     return false;
 631
 632   // Check all returned values but ignore call sites as long as we have not
 633   // encountered an overdefined one during an update.
 634   for (auto &It : ReturnedValues) {
 635     Value *RV = It.first;
 636
 637     ImmutableCallSite ICS(RV);
 638     if (ICS && !HasOverdefinedReturnedCalls)
 639       continue;
 640
 641     if (!Pred(*RV))
 642       return false;
 643   }
 644
 645   return true;
 646 }
 647
 648 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
 649
 650   // Check if we know of any values returned by the associated function,
 651   // if not, we are done.
 652   if (getNumReturnValues() == 0) {
 653     indicateOptimisticFixpoint();
 654     return ChangeStatus::UNCHANGED;
 655   }
 656
 657   // Check if any of the returned values is a call site we can refine.
 658   decltype(ReturnedValues) AddRVs;
 659   bool HasCallSite = false;
 660
 661   // Look at all returned call sites.
 662   for (auto &It : ReturnedValues) {
 663     SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
 664     Value *RV = It.first;
 665     LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
 666                       << "\n");
 667
 668     // Only call sites can change during an update, ignore the rest.
 669     CallSite RetCS(RV);
 670     if (!RetCS)
 671       continue;
 672
 673     // For now, any call site we see will prevent us from directly fixing the
 674     // state. However, if the information on the callees is fixed, the call
 675     // sites will be removed and we will fix the information for this state.
 676     HasCallSite = true;
 677
 678     // Try to find a assumed unique return value for the called function.
 679     auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
 680     if (!RetCSAA) {
 681       HasOverdefinedReturnedCalls = true;
 682       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
 683                         << ") with " << (RetCSAA ? "invalid" : "no")
 684                         << " associated state\n");
 685       continue;
 686     }
 687
 688     // Try to find a assumed unique return value for the called function.
 689     Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
 690
 691     // If no assumed unique return value was found due to the lack of
 692     // candidates, we may need to resolve more calls (through more update
 693     // iterations) or the called function will not return. Either way, we simply
 694     // stick with the call sites as return values. Because there were not
 695     // multiple possibilities, we do not treat it as overdefined.
 696     if (!AssumedUniqueRV.hasValue())
 697       continue;
 698
 699     // If multiple, non-refinable values were found, there cannot be a unique
 700     // return value for the called function. The returned call is overdefined!
 701     if (!AssumedUniqueRV.getValue()) {
 702       HasOverdefinedReturnedCalls = true;
 703       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
 704                            "potentially returned values\n");
 705       continue;
 706     }
 707
 708     LLVM_DEBUG({
 709       bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
 710       dbgs() << "[AAReturnedValues] Returned call site "
 711              << (UniqueRVIsKnown ? "known" : "assumed")
 712              << " unique return value: " << *AssumedUniqueRV << "\n";
 713     });
 714
 715     // The assumed unique return value.
 716     Value *AssumedRetVal = AssumedUniqueRV.getValue();
 717
 718     // If the assumed unique return value is an argument, lookup the matching
 719     // call site operand and recursively collect new returned values.
 720     // If it is not an argument, it is just put into the set of returned values
 721     // as we would have already looked through casts, phis, and similar values.
 722     if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
 723       collectValuesRecursively(A,
 724                                RetCS.getArgOperand(AssumedRetArg->getArgNo()),
 725                                ReturnInsts, AddRVs);
 726     else
 727       AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
 728   }
 729
 730   // Keep track of any change to trigger updates on dependent attributes.
 731   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 732
 733   for (auto &It : AddRVs) {
 734     assert(!It.second.empty() && "Entry does not add anything.");
 735     auto &ReturnInsts = ReturnedValues[It.first];
 736     for (ReturnInst *RI : It.second)
 737       if (ReturnInsts.insert(RI).second) {
 738         LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
 739                           << *It.first << " => " << *RI << "\n");
 740         Changed = ChangeStatus::CHANGED;
 741       }
 742   }
 743
 744   // If there is no call site in the returned values we are done.
 745   if (!HasCallSite) {
 746     indicateOptimisticFixpoint();
 747     return ChangeStatus::CHANGED;
 748   }
 749
 750   return Changed;
 751 }
 752
 753 /// ------------------------ NoSync Function Attribute -------------------------
 754
 755 struct AANoSyncFunction : AANoSync, BooleanState {
 756
 757   AANoSyncFunction(Function &F, InformationCache &InfoCache)
 758       : AANoSync(F, InfoCache) {}
 759
 760   /// See AbstractAttribute::getState()
 761   /// {
 762   AbstractState &getState() override { return *this; }
 763   const AbstractState &getState() const override { return *this; }
 764   /// }
 765
 766   /// See AbstractAttribute::getManifestPosition().
 767   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 768
 769   const std::string getAsStr() const override {
 770     return getAssumed() ? "nosync" : "may-sync";
 771   }
 772
 773   /// See AbstractAttribute::updateImpl(...).
 774   ChangeStatus updateImpl(Attributor &A) override;
 775
 776   /// See AANoSync::isAssumedNoSync()
 777   bool isAssumedNoSync() const override { return getAssumed(); }
 778
 779   /// See AANoSync::isKnownNoSync()
 780   bool isKnownNoSync() const override { return getKnown(); }
 781
 782   /// Helper function used to determine whether an instruction is non-relaxed
 783   /// atomic. In other words, if an atomic instruction does not have unordered
 784   /// or monotonic ordering
 785   static bool isNonRelaxedAtomic(Instruction *I);
 786
 787   /// Helper function used to determine whether an instruction is volatile.
 788   static bool isVolatile(Instruction *I);
 789
 790   /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
 791   /// memset).
 792   static bool isNoSyncIntrinsic(Instruction *I);
 793 };
 794
 795 bool AANoSyncFunction::isNonRelaxedAtomic(Instruction *I) {
 796   if (!I->isAtomic())
 797     return false;
 798
 799   AtomicOrdering Ordering;
 800   switch (I->getOpcode()) {
 801   case Instruction::AtomicRMW:
 802     Ordering = cast<AtomicRMWInst>(I)->getOrdering();
 803     break;
 804   case Instruction::Store:
 805     Ordering = cast<StoreInst>(I)->getOrdering();
 806     break;
 807   case Instruction::Load:
 808     Ordering = cast<LoadInst>(I)->getOrdering();
 809     break;
 810   case Instruction::Fence: {
 811     auto *FI = cast<FenceInst>(I);
 812     if (FI->getSyncScopeID() == SyncScope::SingleThread)
 813       return false;
 814     Ordering = FI->getOrdering();
 815     break;
 816   }
 817   case Instruction::AtomicCmpXchg: {
 818     AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
 819     AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
 820     // Only if both are relaxed, than it can be treated as relaxed.
 821     // Otherwise it is non-relaxed.
 822     if (Success != AtomicOrdering::Unordered &&
 823         Success != AtomicOrdering::Monotonic)
 824       return true;
 825     if (Failure != AtomicOrdering::Unordered &&
 826         Failure != AtomicOrdering::Monotonic)
 827       return true;
 828     return false;
 829   }
 830   default:
 831     llvm_unreachable(
 832         "New atomic operations need to be known in the attributor.");
 833   }
 834
 835   // Relaxed.
 836   if (Ordering == AtomicOrdering::Unordered ||
 837       Ordering == AtomicOrdering::Monotonic)
 838     return false;
 839   return true;
 840 }
 841
 842 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
 843 /// FIXME: We should ipmrove the handling of intrinsics.
 844 bool AANoSyncFunction::isNoSyncIntrinsic(Instruction *I) {
 845   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
 846     switch (II->getIntrinsicID()) {
 847     /// Element wise atomic memory intrinsics are can only be unordered,
 848     /// therefore nosync.
 849     case Intrinsic::memset_element_unordered_atomic:
 850     case Intrinsic::memmove_element_unordered_atomic:
 851     case Intrinsic::memcpy_element_unordered_atomic:
 852       return true;
 853     case Intrinsic::memset:
 854     case Intrinsic::memmove:
 855     case Intrinsic::memcpy:
 856       if (!cast<MemIntrinsic>(II)->isVolatile())
 857         return true;
 858       return false;
 859     default:
 860       return false;
 861     }
 862   }
 863   return false;
 864 }
 865
 866 bool AANoSyncFunction::isVolatile(Instruction *I) {
 867   assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
 868          "Calls should not be checked here");
 869
 870   switch (I->getOpcode()) {
 871   case Instruction::AtomicRMW:
 872     return cast<AtomicRMWInst>(I)->isVolatile();
 873   case Instruction::Store:
 874     return cast<StoreInst>(I)->isVolatile();
 875   case Instruction::Load:
 876     return cast<LoadInst>(I)->isVolatile();
 877   case Instruction::AtomicCmpXchg:
 878     return cast<AtomicCmpXchgInst>(I)->isVolatile();
 879   default:
 880     return false;
 881   }
 882 }
 883
 884 ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
 885   Function &F = getAnchorScope();
 886
 887   /// We are looking for volatile instructions or Non-Relaxed atomics.
 888   /// FIXME: We should ipmrove the handling of intrinsics.
 889   for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) {
 890     ImmutableCallSite ICS(I);
 891     auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
 892
 893     if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
 894       continue;
 895
 896     if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
 897         !ICS.hasFnAttr(Attribute::NoSync)) {
 898       indicatePessimisticFixpoint();
 899       return ChangeStatus::CHANGED;
 900     }
 901
 902     if (ICS)
 903       continue;
 904
 905     if (!isVolatile(I) && !isNonRelaxedAtomic(I))
 906       continue;
 907
 908     indicatePessimisticFixpoint();
 909     return ChangeStatus::CHANGED;
 910   }
 911
 912   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 913   auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
 914                   (unsigned)Instruction::Call};
 915
 916   for (unsigned Opcode : Opcodes) {
 917     for (Instruction *I : OpcodeInstMap[Opcode]) {
 918       // At this point we handled all read/write effects and they are all
 919       // nosync, so they can be skipped.
 920       if (I->mayReadOrWriteMemory())
 921         continue;
 922
 923       ImmutableCallSite ICS(I);
 924
 925       // non-convergent and readnone imply nosync.
 926       if (!ICS.isConvergent())
 927         continue;
 928
 929       indicatePessimisticFixpoint();
 930       return ChangeStatus::CHANGED;
 931     }
 932   }
 933
 934   return ChangeStatus::UNCHANGED;
 935 }
 936
 937 /// ------------------------ No-Free Attributes ----------------------------
 938
 939 struct AANoFreeFunction : AbstractAttribute, BooleanState {
 940
 941   /// See AbstractAttribute::AbstractAttribute(...).
 942   AANoFreeFunction(Function &F, InformationCache &InfoCache)
 943       : AbstractAttribute(F, InfoCache) {}
 944
 945   /// See AbstractAttribute::getState()
 946   ///{
 947   AbstractState &getState() override { return *this; }
 948   const AbstractState &getState() const override { return *this; }
 949   ///}
 950
 951   /// See AbstractAttribute::getManifestPosition().
 952   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 953
 954   /// See AbstractAttribute::getAsStr().
 955   const std::string getAsStr() const override {
 956     return getAssumed() ? "nofree" : "may-free";
 957   }
 958
 959   /// See AbstractAttribute::updateImpl(...).
 960   ChangeStatus updateImpl(Attributor &A) override;
 961
 962   /// See AbstractAttribute::getAttrKind().
 963   Attribute::AttrKind getAttrKind() const override { return ID; }
 964
 965   /// Return true if "nofree" is assumed.
 966   bool isAssumedNoFree() const { return getAssumed(); }
 967
 968   /// Return true if "nofree" is known.
 969   bool isKnownNoFree() const { return getKnown(); }
 970
 971   /// The identifier used by the Attributor for this class of attributes.
 972   static constexpr Attribute::AttrKind ID = Attribute::NoFree;
 973 };
 974
 975 ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
 976   Function &F = getAnchorScope();
 977
 978   // The map from instruction opcodes to those instructions in the function.
 979   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 980
 981   for (unsigned Opcode :
 982        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
 983         (unsigned)Instruction::Call}) {
 984     for (Instruction *I : OpcodeInstMap[Opcode]) {
 985
 986       auto ICS = ImmutableCallSite(I);
 987       auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
 988
 989       if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
 990           !ICS.hasFnAttr(Attribute::NoFree)) {
 991         indicatePessimisticFixpoint();
 992         return ChangeStatus::CHANGED;
 993       }
 994     }
 995   }
 996   return ChangeStatus::UNCHANGED;
 997 }
 998
 999 /// ------------------------ NonNull Argument Attribute ------------------------
1000 struct AANonNullImpl : AANonNull, BooleanState {
1001
1002   AANonNullImpl(Value &V, InformationCache &InfoCache)
1003       : AANonNull(V, InfoCache) {}
1004
1005   AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue,
1006                 InformationCache &InfoCache)
1007       : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1008
1009   /// See AbstractAttribute::getState()
1010   /// {
1011   AbstractState &getState() override { return *this; }
1012   const AbstractState &getState() const override { return *this; }
1013   /// }
1014
1015   /// See AbstractAttribute::getAsStr().
1016   const std::string getAsStr() const override {
1017     return getAssumed() ? "nonnull" : "may-null";
1018   }
1019
1020   /// See AANonNull::isAssumedNonNull().
1021   bool isAssumedNonNull() const override { return getAssumed(); }
1022
1023   /// See AANonNull::isKnownNonNull().
1024   bool isKnownNonNull() const override { return getKnown(); }
1025
1026   /// Generate a predicate that checks if a given value is assumed nonnull.
1027   /// The generated function returns true if a value satisfies any of
1028   /// following conditions.
1029   /// (i) A value is known nonZero(=nonnull).
1030   /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
1031   /// true.
1032   std::function<bool(Value &)> generatePredicate(Attributor &);
1033 };
1034
1035 std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
1036   // FIXME: The `AAReturnedValues` should provide the predicate with the
1037   // `ReturnInst` vector as well such that we can use the control flow sensitive
1038   // version of `isKnownNonZero`. This should fix `test11` in
1039   // `test/Transforms/FunctionAttrs/nonnull.ll`
1040
1041   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1042     if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1043       return true;
1044
1045     auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1046
1047     ImmutableCallSite ICS(&RV);
1048
1049     if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
1050         (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
1051       return false;
1052
1053     return true;
1054   };
1055
1056   return Pred;
1057 }
1058
1059 /// NonNull attribute for function return value.
1060 struct AANonNullReturned : AANonNullImpl {
1061
1062   AANonNullReturned(Function &F, InformationCache &InfoCache)
1063       : AANonNullImpl(F, InfoCache) {}
1064
1065   /// See AbstractAttribute::getManifestPosition().
1066   ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1067
1068   /// See AbstractAttriubute::initialize(...).
1069   void initialize(Attributor &A) override {
1070     Function &F = getAnchorScope();
1071
1072     // Already nonnull.
1073     if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1074                                        Attribute::NonNull))
1075       indicateOptimisticFixpoint();
1076   }
1077
1078   /// See AbstractAttribute::updateImpl(...).
1079   ChangeStatus updateImpl(Attributor &A) override;
1080 };
1081
1082 ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
1083   Function &F = getAnchorScope();
1084
1085   auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1086   if (!AARetVal) {
1087     indicatePessimisticFixpoint();
1088     return ChangeStatus::CHANGED;
1089   }
1090
1091   std::function<bool(Value &)> Pred = this->generatePredicate(A);
1092   if (!AARetVal->checkForallReturnedValues(Pred)) {
1093     indicatePessimisticFixpoint();
1094     return ChangeStatus::CHANGED;
1095   }
1096   return ChangeStatus::UNCHANGED;
1097 }
1098
1099 /// NonNull attribute for function argument.
1100 struct AANonNullArgument : AANonNullImpl {
1101
1102   AANonNullArgument(Argument &A, InformationCache &InfoCache)
1103       : AANonNullImpl(A, InfoCache) {}
1104
1105   /// See AbstractAttribute::getManifestPosition().
1106   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1107
1108   /// See AbstractAttriubute::initialize(...).
1109   void initialize(Attributor &A) override {
1110     Argument *Arg = cast<Argument>(getAssociatedValue());
1111     if (Arg->hasNonNullAttr())
1112       indicateOptimisticFixpoint();
1113   }
1114
1115   /// See AbstractAttribute::updateImpl(...).
1116   ChangeStatus updateImpl(Attributor &A) override;
1117 };
1118
1119 /// NonNull attribute for a call site argument.
1120 struct AANonNullCallSiteArgument : AANonNullImpl {
1121
1122   /// See AANonNullImpl::AANonNullImpl(...).
1123   AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
1124                             InformationCache &InfoCache)
1125       : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1126         ArgNo(ArgNo) {}
1127
1128   /// See AbstractAttribute::initialize(...).
1129   void initialize(Attributor &A) override {
1130     CallSite CS(&getAnchoredValue());
1131     if (isKnownNonZero(getAssociatedValue(),
1132                        getAnchorScope().getParent()->getDataLayout()) ||
1133         CS.paramHasAttr(ArgNo, getAttrKind()))
1134       indicateOptimisticFixpoint();
1135   }
1136
1137   /// See AbstractAttribute::updateImpl(Attributor &A).
1138   ChangeStatus updateImpl(Attributor &A) override;
1139
1140   /// See AbstractAttribute::getManifestPosition().
1141   ManifestPosition getManifestPosition() const override {
1142     return MP_CALL_SITE_ARGUMENT;
1143   };
1144
1145   // Return argument index of associated value.
1146   int getArgNo() const { return ArgNo; }
1147
1148 private:
1149   unsigned ArgNo;
1150 };
1151 ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
1152   Function &F = getAnchorScope();
1153   Argument &Arg = cast<Argument>(getAnchoredValue());
1154
1155   unsigned ArgNo = Arg.getArgNo();
1156
1157   // Callback function
1158   std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1159     assert(CS && "Sanity check: Call site was not initialized properly!");
1160
1161     auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1162
1163     // Check that NonNullAA is AANonNullCallSiteArgument.
1164     if (NonNullAA) {
1165       ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1166       if (ICS && CS.getInstruction() == ICS.getInstruction())
1167         return NonNullAA->isAssumedNonNull();
1168       return false;
1169     }
1170
1171     if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1172       return true;
1173
1174     Value *V = CS.getArgOperand(ArgNo);
1175     if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1176       return true;
1177
1178     return false;
1179   };
1180   if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1181     indicatePessimisticFixpoint();
1182     return ChangeStatus::CHANGED;
1183   }
1184   return ChangeStatus::UNCHANGED;
1185 }
1186
1187 ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
1188   // NOTE: Never look at the argument of the callee in this method.
1189   //       If we do this, "nonnull" is always deduced because of the assumption.
1190
1191   Value &V = *getAssociatedValue();
1192
1193   auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1194
1195   if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
1196     indicatePessimisticFixpoint();
1197     return ChangeStatus::CHANGED;
1198   }
1199
1200   return ChangeStatus::UNCHANGED;
1201 }
1202
1203 /// ------------------------ Will-Return Attributes ----------------------------
1204
1205 struct AAWillReturnImpl : public AAWillReturn, BooleanState {
1206
1207   /// See AbstractAttribute::AbstractAttribute(...).
1208   AAWillReturnImpl(Function &F, InformationCache &InfoCache)
1209       : AAWillReturn(F, InfoCache) {}
1210
1211   /// See AAWillReturn::isKnownWillReturn().
1212   bool isKnownWillReturn() const override { return getKnown(); }
1213
1214   /// See AAWillReturn::isAssumedWillReturn().
1215   bool isAssumedWillReturn() const override { return getAssumed(); }
1216
1217   /// See AbstractAttribute::getState(...).
1218   AbstractState &getState() override { return *this; }
1219
1220   /// See AbstractAttribute::getState(...).
1221   const AbstractState &getState() const override { return *this; }
1222
1223   /// See AbstractAttribute::getAsStr()
1224   const std::string getAsStr() const override {
1225     return getAssumed() ? "willreturn" : "may-noreturn";
1226   }
1227 };
1228
1229 struct AAWillReturnFunction final : AAWillReturnImpl {
1230
1231   /// See AbstractAttribute::AbstractAttribute(...).
1232   AAWillReturnFunction(Function &F, InformationCache &InfoCache)
1233       : AAWillReturnImpl(F, InfoCache) {}
1234
1235   /// See AbstractAttribute::getManifestPosition().
1236   ManifestPosition getManifestPosition() const override {
1237     return MP_FUNCTION;
1238   }
1239
1240   /// See AbstractAttribute::initialize(...).
1241   void initialize(Attributor &A) override;
1242
1243   /// See AbstractAttribute::updateImpl(...).
1244   ChangeStatus updateImpl(Attributor &A) override;
1245 };
1246
1247 // Helper function that checks whether a function has any cycle.
1248 // TODO: Replace with more efficent code
1249 bool containsCycle(Function &F) {
1250   SmallPtrSet<BasicBlock *, 32> Visited;
1251
1252   // Traverse BB by dfs and check whether successor is already visited.
1253   for (BasicBlock *BB : depth_first(&F)) {
1254     Visited.insert(BB);
1255     for (auto *SuccBB : successors(BB)) {
1256       if (Visited.count(SuccBB))
1257         return true;
1258     }
1259   }
1260   return false;
1261 }
1262
1263 // Helper function that checks the function have a loop which might become an
1264 // endless loop
1265 // FIXME: Any cycle is regarded as endless loop for now.
1266 //        We have to allow some patterns.
1267 bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); }
1268
1269 void AAWillReturnFunction::initialize(Attributor &A) {
1270   Function &F = getAnchorScope();
1271
1272   if (containsPossiblyEndlessLoop(F))
1273     indicatePessimisticFixpoint();
1274 }
1275
1276 ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
1277   Function &F = getAnchorScope();
1278
1279   // The map from instruction opcodes to those instructions in the function.
1280   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1281
1282   for (unsigned Opcode :
1283        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1284         (unsigned)Instruction::Call}) {
1285     for (Instruction *I : OpcodeInstMap[Opcode]) {
1286       auto ICS = ImmutableCallSite(I);
1287
1288       if (ICS.hasFnAttr(Attribute::WillReturn))
1289         continue;
1290
1291       auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1292       if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
1293         indicatePessimisticFixpoint();
1294         return ChangeStatus::CHANGED;
1295       }
1296
1297       auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1298
1299       // FIXME: (i) Prohibit any recursion for now.
1300       //        (ii) AANoRecurse isn't implemented yet so currently any call is
1301       //        regarded as having recursion.
1302       //       Code below should be
1303       //       if ((!NoRecurseAA || !NoRecurseAA->isAssumedNoRecurse()) &&
1304       if (!NoRecurseAA && !ICS.hasFnAttr(Attribute::NoRecurse)) {
1305         indicatePessimisticFixpoint();
1306         return ChangeStatus::CHANGED;
1307       }
1308     }
1309   }
1310
1311   return ChangeStatus::UNCHANGED;
1312 }
1313
1314 /// ----------------------------------------------------------------------------
1315 ///                               Attributor
1316 /// ----------------------------------------------------------------------------
1317
1318 bool Attributor::checkForAllCallSites(Function &F,
1319                                       std::function<bool(CallSite)> &Pred,
1320                                       bool RequireAllCallSites) {
1321   // We can try to determine information from
1322   // the call sites. However, this is only possible all call sites are known,
1323   // hence the function has internal linkage.
1324   if (RequireAllCallSites && !F.hasInternalLinkage()) {
1325     LLVM_DEBUG(
1326         dbgs()
1327         << "Attributor: Function " << F.getName()
1328         << " has no internal linkage, hence not all call sites are known\n");
1329     return false;
1330   }
1331
1332   for (const Use &U : F.uses()) {
1333
1334     CallSite CS(U.getUser());
1335     if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1336       if (!RequireAllCallSites)
1337         continue;
1338
1339       LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
1340                         << " is an invalid use of " << F.getName() << "\n");
1341       return false;
1342     }
1343
1344     if (Pred(CS))
1345       continue;
1346
1347     LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
1348                       << *CS.getInstruction() << "\n");
1349     return false;
1350   }
1351
1352   return true;
1353 }
1354
1355 ChangeStatus Attributor::run() {
1356   // Initialize all abstract attributes.
1357   for (AbstractAttribute *AA : AllAbstractAttributes)
1358     AA->initialize(*this);
1359
1360   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
1361                     << AllAbstractAttributes.size()
1362                     << " abstract attributes.\n");
1363
1364   // Now that all abstract attributes are collected and initialized we start
1365   // the abstract analysis.
1366
1367   unsigned IterationCounter = 1;
1368
1369   SmallVector<AbstractAttribute *, 64> ChangedAAs;
1370   SetVector<AbstractAttribute *> Worklist;
1371   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
1372
1373   do {
1374     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1375                       << ", Worklist size: " << Worklist.size() << "\n");
1376
1377     // Add all abstract attributes that are potentially dependent on one that
1378     // changed to the work list.
1379     for (AbstractAttribute *ChangedAA : ChangedAAs) {
1380       auto &QuerriedAAs = QueryMap[ChangedAA];
1381       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
1382     }
1383
1384     // Reset the changed set.
1385     ChangedAAs.clear();
1386
1387     // Update all abstract attribute in the work list and record the ones that
1388     // changed.
1389     for (AbstractAttribute *AA : Worklist)
1390       if (AA->update(*this) == ChangeStatus::CHANGED)
1391         ChangedAAs.push_back(AA);
1392
1393     // Reset the work list and repopulate with the changed abstract attributes.
1394     // Note that dependent ones are added above.
1395     Worklist.clear();
1396     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1397
1398   } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
1399
1400   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1401                     << IterationCounter << "/" << MaxFixpointIterations
1402                     << " iterations\n");
1403
1404   bool FinishedAtFixpoint = Worklist.empty();
1405
1406   // Reset abstract arguments not settled in a sound fixpoint by now. This
1407   // happens when we stopped the fixpoint iteration early. Note that only the
1408   // ones marked as "changed" *and* the ones transitively depending on them
1409   // need to be reverted to a pessimistic state. Others might not be in a
1410   // fixpoint state but we can use the optimistic results for them anyway.
1411   SmallPtrSet<AbstractAttribute *, 32> Visited;
1412   for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1413     AbstractAttribute *ChangedAA = ChangedAAs[u];
1414     if (!Visited.insert(ChangedAA).second)
1415       continue;
1416
1417     AbstractState &State = ChangedAA->getState();
1418     if (!State.isAtFixpoint()) {
1419       State.indicatePessimisticFixpoint();
1420
1421       NumAttributesTimedOut++;
1422     }
1423
1424     auto &QuerriedAAs = QueryMap[ChangedAA];
1425     ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
1426   }
1427
1428   LLVM_DEBUG({
1429     if (!Visited.empty())
1430       dbgs() << "\n[Attributor] Finalized " << Visited.size()
1431              << " abstract attributes.\n";
1432   });
1433
1434   unsigned NumManifested = 0;
1435   unsigned NumAtFixpoint = 0;
1436   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1437   for (AbstractAttribute *AA : AllAbstractAttributes) {
1438     AbstractState &State = AA->getState();
1439
1440     // If there is not already a fixpoint reached, we can now take the
1441     // optimistic state. This is correct because we enforced a pessimistic one
1442     // on abstract attributes that were transitively dependent on a changed one
1443     // already above.
1444     if (!State.isAtFixpoint())
1445       State.indicateOptimisticFixpoint();
1446
1447     // If the state is invalid, we do not try to manifest it.
1448     if (!State.isValidState())
1449       continue;
1450
1451     // Manifest the state and record if we changed the IR.
1452     ChangeStatus LocalChange = AA->manifest(*this);
1453     ManifestChange = ManifestChange | LocalChange;
1454
1455     NumAtFixpoint++;
1456     NumManifested += (LocalChange == ChangeStatus::CHANGED);
1457   }
1458
1459   (void)NumManifested;
1460   (void)NumAtFixpoint;
1461   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1462                     << " arguments while " << NumAtFixpoint
1463                     << " were in a valid fixpoint state\n");
1464
1465   // If verification is requested, we finished this run at a fixpoint, and the
1466   // IR was changed, we re-run the whole fixpoint analysis, starting at
1467   // re-initialization of the arguments. This re-run should not result in an IR
1468   // change. Though, the (virtual) state of attributes at the end of the re-run
1469   // might be more optimistic than the known state or the IR state if the better
1470   // state cannot be manifested.
1471   if (VerifyAttributor && FinishedAtFixpoint &&
1472       ManifestChange == ChangeStatus::CHANGED) {
1473     VerifyAttributor = false;
1474     ChangeStatus VerifyStatus = run();
1475     if (VerifyStatus != ChangeStatus::UNCHANGED)
1476       llvm_unreachable(
1477           "Attributor verification failed, re-run did result in an IR change "
1478           "even after a fixpoint was reached in the original run. (False "
1479           "positives possible!)");
1480     VerifyAttributor = true;
1481   }
1482
1483   NumAttributesManifested += NumManifested;
1484   NumAttributesValidFixpoint += NumAtFixpoint;
1485
1486   return ManifestChange;
1487 }
1488
1489 void Attributor::identifyDefaultAbstractAttributes(
1490     Function &F, InformationCache &InfoCache,
1491     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
1492
1493   // Every function can be nounwind.
1494   registerAA(*new AANoUnwindFunction(F, InfoCache));
1495
1496   // Every function might be marked "nosync"
1497   registerAA(*new AANoSyncFunction(F, InfoCache));
1498
1499   // Every function might be "no-free".
1500   registerAA(*new AANoFreeFunction(F, InfoCache));
1501
1502   // Return attributes are only appropriate if the return type is non void.
1503   Type *ReturnType = F.getReturnType();
1504   if (!ReturnType->isVoidTy()) {
1505     // Argument attribute "returned" --- Create only one per function even
1506     // though it is an argument attribute.
1507     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
1508       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
1509
1510     // Every function with pointer return type might be marked nonnull.
1511     if (ReturnType->isPointerTy() &&
1512         (!Whitelist || Whitelist->count(AANonNullReturned::ID)))
1513       registerAA(*new AANonNullReturned(F, InfoCache));
1514   }
1515
1516   // Every argument with pointer type might be marked nonnull.
1517   for (Argument &Arg : F.args()) {
1518     if (Arg.getType()->isPointerTy())
1519       registerAA(*new AANonNullArgument(Arg, InfoCache));
1520   }
1521
1522   // Every function might be "will-return".
1523   registerAA(*new AAWillReturnFunction(F, InfoCache));
1524
1525   // Walk all instructions to find more attribute opportunities and also
1526   // interesting instructions that might be queried by abstract attributes
1527   // during their initialization or update.
1528   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
1529   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
1530
1531   for (Instruction &I : instructions(&F)) {
1532     bool IsInterestingOpcode = false;
1533
1534     // To allow easy access to all instructions in a function with a given
1535     // opcode we store them in the InfoCache. As not all opcodes are interesting
1536     // to concrete attributes we only cache the ones that are as identified in
1537     // the following switch.
1538     // Note: There are no concrete attributes now so this is initially empty.
1539     switch (I.getOpcode()) {
1540     default:
1541       assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
1542              "New call site/base instruction type needs to be known int the "
1543              "attributor.");
1544       break;
1545     case Instruction::Call:
1546     case Instruction::CallBr:
1547     case Instruction::Invoke:
1548     case Instruction::CleanupRet:
1549     case Instruction::CatchSwitch:
1550     case Instruction::Resume:
1551     case Instruction::Ret:
1552       IsInterestingOpcode = true;
1553     }
1554     if (IsInterestingOpcode)
1555       InstOpcodeMap[I.getOpcode()].push_back(&I);
1556     if (I.mayReadOrWriteMemory())
1557       ReadOrWriteInsts.push_back(&I);
1558
1559     CallSite CS(&I);
1560     if (CS && CS.getCalledFunction()) {
1561       for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
1562         if (!CS.getArgument(i)->getType()->isPointerTy())
1563           continue;
1564
1565         // Call site argument attribute "non-null".
1566         registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
1567       }
1568     }
1569   }
1570 }
1571
1572 /// Helpers to ease debugging through output streams and print calls.
1573 ///
1574 ///{
1575 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
1576   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
1577 }
1578
1579 raw_ostream &llvm::operator<<(raw_ostream &OS,
1580                               AbstractAttribute::ManifestPosition AP) {
1581   switch (AP) {
1582   case AbstractAttribute::MP_ARGUMENT:
1583     return OS << "arg";
1584   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
1585     return OS << "cs_arg";
1586   case AbstractAttribute::MP_FUNCTION:
1587     return OS << "fn";
1588   case AbstractAttribute::MP_RETURNED:
1589     return OS << "fn_ret";
1590   }
1591   llvm_unreachable("Unknown attribute position!");
1592 }
1593
1594 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
1595   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
1596 }
1597
1598 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
1599   AA.print(OS);
1600   return OS;
1601 }
1602
1603 void AbstractAttribute::print(raw_ostream &OS) const {
1604   OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
1605      << AnchoredVal.getName() << "]";
1606 }
1607 ///}
1608
1609 /// ----------------------------------------------------------------------------
1610 ///                       Pass (Manager) Boilerplate
1611 /// ----------------------------------------------------------------------------
1612
1613 static bool runAttributorOnModule(Module &M) {
1614   if (DisableAttributor)
1615     return false;
1616
1617   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
1618                     << " functions.\n");
1619
1620   // Create an Attributor and initially empty information cache that is filled
1621   // while we identify default attribute opportunities.
1622   Attributor A;
1623   InformationCache InfoCache;
1624
1625   for (Function &F : M) {
1626     // TODO: Not all attributes require an exact definition. Find a way to
1627     //       enable deduction for some but not all attributes in case the
1628     //       definition might be changed at runtime, see also
1629     //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
1630     // TODO: We could always determine abstract attributes and if sufficient
1631     //       information was found we could duplicate the functions that do not
1632     //       have an exact definition.
1633     if (!F.hasExactDefinition()) {
1634       NumFnWithoutExactDefinition++;
1635       continue;
1636     }
1637
1638     // For now we ignore naked and optnone functions.
1639     if (F.hasFnAttribute(Attribute::Naked) ||
1640         F.hasFnAttribute(Attribute::OptimizeNone))
1641       continue;
1642
1643     NumFnWithExactDefinition++;
1644
1645     // Populate the Attributor with abstract attribute opportunities in the
1646     // function and the information cache with IR information.
1647     A.identifyDefaultAbstractAttributes(F, InfoCache);
1648   }
1649
1650   return A.run() == ChangeStatus::CHANGED;
1651 }
1652
1653 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
1654   if (runAttributorOnModule(M)) {
1655     // FIXME: Think about passes we will preserve and add them here.
1656     return PreservedAnalyses::none();
1657   }
1658   return PreservedAnalyses::all();
1659 }
1660
1661 namespace {
1662
1663 struct AttributorLegacyPass : public ModulePass {
1664   static char ID;
1665
1666   AttributorLegacyPass() : ModulePass(ID) {
1667     initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
1668   }
1669
1670   bool runOnModule(Module &M) override {
1671     if (skipModule(M))
1672       return false;
1673     return runAttributorOnModule(M);
1674   }
1675
1676   void getAnalysisUsage(AnalysisUsage &AU) const override {
1677     // FIXME: Think about passes we will preserve and add them here.
1678     AU.setPreservesCFG();
1679   }
1680 };
1681
1682 } // end anonymous namespace
1683
1684 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
1685
1686 char AttributorLegacyPass::ID = 0;
1687 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
1688                       "Deduce and propagate attributes", false, false)
1689 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
1690                     "Deduce and propagate attributes", false, false)