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/STLExtras.h"
  20 #include "llvm/ADT/SetVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Analysis/CaptureTracking.h"
  25 #include "llvm/Analysis/GlobalsModRef.h"
  26 #include "llvm/Analysis/Loads.h"
  27 #include "llvm/Analysis/ValueTracking.h"
  28 #include "llvm/IR/Argument.h"
  29 #include "llvm/IR/Attributes.h"
  30 #include "llvm/IR/CFG.h"
  31 #include "llvm/IR/InstIterator.h"
  32 #include "llvm/IR/IntrinsicInst.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  37 #include "llvm/Transforms/Utils/Local.h"
  38
  39 #include <cassert>
  40
  41 using namespace llvm;
  42
  43 #define DEBUG_TYPE "attributor"
  44
  45 STATISTIC(NumFnWithExactDefinition,
  46           "Number of function with exact definitions");
  47 STATISTIC(NumFnWithoutExactDefinition,
  48           "Number of function without exact definitions");
  49 STATISTIC(NumAttributesTimedOut,
  50           "Number of abstract attributes timed out before fixpoint");
  51 STATISTIC(NumAttributesValidFixpoint,
  52           "Number of abstract attributes in a valid fixpoint state");
  53 STATISTIC(NumAttributesManifested,
  54           "Number of abstract attributes manifested in IR");
  55 STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind");
  56
  57 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
  58 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
  59 STATISTIC(NumFnArgumentReturned,
  60           "Number of function arguments marked returned");
  61 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
  62 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
  63 STATISTIC(NumFnReturnedNonNull,
  64           "Number of function return values marked nonnull");
  65 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
  66 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
  67 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
  68 STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
  69 STATISTIC(NumFnReturnedDereferenceable,
  70           "Number of function return values marked dereferenceable");
  71 STATISTIC(NumFnArgumentDereferenceable,
  72           "Number of function arguments marked dereferenceable");
  73 STATISTIC(NumCSArgumentDereferenceable,
  74           "Number of call site arguments marked dereferenceable");
  75
  76 // TODO: Determine a good default value.
  77 //
  78 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
  79 // (when run with the first 5 abstract attributes). The results also indicate
  80 // that we never reach 32 iterations but always find a fixpoint sooner.
  81 //
  82 // This will become more evolved once we perform two interleaved fixpoint
  83 // iterations: bottom-up and top-down.
  84 static cl::opt<unsigned>
  85     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
  86                           cl::desc("Maximal number of fixpoint iterations."),
  87                           cl::init(32));
  88
  89 static cl::opt<bool> DisableAttributor(
  90     "attributor-disable", cl::Hidden,
  91     cl::desc("Disable the attributor inter-procedural deduction pass."),
  92     cl::init(true));
  93
  94 static cl::opt<bool> VerifyAttributor(
  95     "attributor-verify", cl::Hidden,
  96     cl::desc("Verify the Attributor deduction and "
  97              "manifestation of attributes -- may issue false-positive errors"),
  98     cl::init(false));
  99
 100 /// Logic operators for the change status enum class.
 101 ///
 102 ///{
 103 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
 104   return l == ChangeStatus::CHANGED ? l : r;
 105 }
 106 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
 107   return l == ChangeStatus::UNCHANGED ? l : r;
 108 }
 109 ///}
 110
 111 /// Helper to adjust the statistics.
 112 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
 113                         const Attribute &Attr) {
 114   if (!AreStatisticsEnabled())
 115     return;
 116
 117   switch (Attr.getKindAsEnum()) {
 118   case Attribute::Dereferenceable:
 119     switch (MP) {
 120     case AbstractAttribute::MP_RETURNED:
 121       NumFnReturnedDereferenceable++;
 122       break;
 123     case AbstractAttribute::MP_ARGUMENT:
 124       NumFnArgumentDereferenceable++;
 125       break;
 126     case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 127       NumCSArgumentDereferenceable++;
 128       break;
 129     default:
 130       break;
 131     }
 132     break;
 133   case Attribute::NoUnwind:
 134     NumFnNoUnwind++;
 135     return;
 136   case Attribute::Returned:
 137     NumFnArgumentReturned++;
 138     return;
 139   case Attribute::NoSync:
 140     NumFnNoSync++;
 141     break;
 142   case Attribute::NoFree:
 143     NumFnNoFree++;
 144     break;
 145   case Attribute::NonNull:
 146     switch (MP) {
 147     case AbstractAttribute::MP_RETURNED:
 148       NumFnReturnedNonNull++;
 149       break;
 150     case AbstractAttribute::MP_ARGUMENT:
 151       NumFnArgumentNonNull++;
 152       break;
 153     case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 154       NumCSArgumentNonNull++;
 155       break;
 156     default:
 157       break;
 158     }
 159     break;
 160   case Attribute::WillReturn:
 161     NumFnWillReturn++;
 162     break;
 163   case Attribute::NoAlias:
 164     NumFnArgumentNoAlias++;
 165     return;
 166   default:
 167     return;
 168   }
 169 }
 170
 171 template <typename StateTy>
 172 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
 173 template <typename StateTy>
 174 using visitValueCB_t = std::function<void(Value *, StateTy &State)>;
 175
 176 /// Recursively visit all values that might become \p InitV at some point. This
 177 /// will be done by looking through cast instructions, selects, phis, and calls
 178 /// with the "returned" attribute. The callback \p FollowValueCB is asked before
 179 /// a potential origin value is looked at. If no \p FollowValueCB is passed, a
 180 /// default one is used that will make sure we visit every value only once. Once
 181 /// we cannot look through the value any further, the callback \p VisitValueCB
 182 /// is invoked and passed the current value and the \p State. To limit how much
 183 /// effort is invested, we will never visit more than \p MaxValues values.
 184 template <typename StateTy>
 185 static bool genericValueTraversal(
 186     Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
 187     followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
 188
 189   SmallPtrSet<Value *, 16> Visited;
 190   followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
 191     return Visited.insert(Val).second;
 192   };
 193
 194   if (!FollowValueCB)
 195     FollowValueCB = &DefaultFollowValueCB;
 196
 197   SmallVector<Value *, 16> Worklist;
 198   Worklist.push_back(InitV);
 199
 200   int Iteration = 0;
 201   do {
 202     Value *V = Worklist.pop_back_val();
 203
 204     // Check if we should process the current value. To prevent endless
 205     // recursion keep a record of the values we followed!
 206     if (!(*FollowValueCB)(V, State))
 207       continue;
 208
 209     // Make sure we limit the compile time for complex expressions.
 210     if (Iteration++ >= MaxValues)
 211       return false;
 212
 213     // Explicitly look through calls with a "returned" attribute if we do
 214     // not have a pointer as stripPointerCasts only works on them.
 215     if (V->getType()->isPointerTy()) {
 216       V = V->stripPointerCasts();
 217     } else {
 218       CallSite CS(V);
 219       if (CS && CS.getCalledFunction()) {
 220         Value *NewV = nullptr;
 221         for (Argument &Arg : CS.getCalledFunction()->args())
 222           if (Arg.hasReturnedAttr()) {
 223             NewV = CS.getArgOperand(Arg.getArgNo());
 224             break;
 225           }
 226         if (NewV) {
 227           Worklist.push_back(NewV);
 228           continue;
 229         }
 230       }
 231     }
 232
 233     // Look through select instructions, visit both potential values.
 234     if (auto *SI = dyn_cast<SelectInst>(V)) {
 235       Worklist.push_back(SI->getTrueValue());
 236       Worklist.push_back(SI->getFalseValue());
 237       continue;
 238     }
 239
 240     // Look through phi nodes, visit all operands.
 241     if (auto *PHI = dyn_cast<PHINode>(V)) {
 242       Worklist.append(PHI->op_begin(), PHI->op_end());
 243       continue;
 244     }
 245
 246     // Once a leaf is reached we inform the user through the callback.
 247     VisitValueCB(V, State);
 248   } while (!Worklist.empty());
 249
 250   // All values have been visited.
 251   return true;
 252 }
 253
 254 /// Helper to identify the correct offset into an attribute list.
 255 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
 256                              unsigned ArgNo = 0) {
 257   switch (MP) {
 258   case AbstractAttribute::MP_ARGUMENT:
 259   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 260     return ArgNo + AttributeList::FirstArgIndex;
 261   case AbstractAttribute::MP_FUNCTION:
 262     return AttributeList::FunctionIndex;
 263   case AbstractAttribute::MP_RETURNED:
 264     return AttributeList::ReturnIndex;
 265   }
 266   llvm_unreachable("Unknown manifest position!");
 267 }
 268
 269 /// Return true if \p New is equal or worse than \p Old.
 270 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
 271   if (!Old.isIntAttribute())
 272     return true;
 273
 274   return Old.getValueAsInt() >= New.getValueAsInt();
 275 }
 276
 277 /// Return true if the information provided by \p Attr was added to the
 278 /// attribute list \p Attrs. This is only the case if it was not already present
 279 /// in \p Attrs at the position describe by \p MP and \p ArgNo.
 280 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
 281                              AttributeList &Attrs,
 282                              AbstractAttribute::ManifestPosition MP,
 283                              unsigned ArgNo = 0) {
 284   unsigned AttrIdx = getAttrIndex(MP, ArgNo);
 285
 286   if (Attr.isEnumAttribute()) {
 287     Attribute::AttrKind Kind = Attr.getKindAsEnum();
 288     if (Attrs.hasAttribute(AttrIdx, Kind))
 289       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 290         return false;
 291     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 292     return true;
 293   }
 294   if (Attr.isStringAttribute()) {
 295     StringRef Kind = Attr.getKindAsString();
 296     if (Attrs.hasAttribute(AttrIdx, Kind))
 297       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 298         return false;
 299     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 300     return true;
 301   }
 302   if (Attr.isIntAttribute()) {
 303     Attribute::AttrKind Kind = Attr.getKindAsEnum();
 304     if (Attrs.hasAttribute(AttrIdx, Kind))
 305       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 306         return false;
 307     Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
 308     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 309     return true;
 310   }
 311
 312   llvm_unreachable("Expected enum or string attribute!");
 313 }
 314
 315 ChangeStatus AbstractAttribute::update(Attributor &A) {
 316   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 317   if (getState().isAtFixpoint())
 318     return HasChanged;
 319
 320   LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
 321
 322   HasChanged = updateImpl(A);
 323
 324   LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
 325                     << "\n");
 326
 327   return HasChanged;
 328 }
 329
 330 ChangeStatus AbstractAttribute::manifest(Attributor &A) {
 331   assert(getState().isValidState() &&
 332          "Attempted to manifest an invalid state!");
 333   assert(getAssociatedValue() &&
 334          "Attempted to manifest an attribute without associated value!");
 335
 336   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 337   SmallVector<Attribute, 4> DeducedAttrs;
 338   getDeducedAttributes(DeducedAttrs);
 339
 340   Function &ScopeFn = getAnchorScope();
 341   LLVMContext &Ctx = ScopeFn.getContext();
 342   ManifestPosition MP = getManifestPosition();
 343
 344   AttributeList Attrs;
 345   SmallVector<unsigned, 4> ArgNos;
 346
 347   // In the following some generic code that will manifest attributes in
 348   // DeducedAttrs if they improve the current IR. Due to the different
 349   // annotation positions we use the underlying AttributeList interface.
 350   // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
 351
 352   switch (MP) {
 353   case MP_ARGUMENT:
 354     ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
 355     Attrs = ScopeFn.getAttributes();
 356     break;
 357   case MP_FUNCTION:
 358   case MP_RETURNED:
 359     ArgNos.push_back(0);
 360     Attrs = ScopeFn.getAttributes();
 361     break;
 362   case MP_CALL_SITE_ARGUMENT: {
 363     CallSite CS(&getAnchoredValue());
 364     for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
 365       if (CS.getArgOperand(u) == getAssociatedValue())
 366         ArgNos.push_back(u);
 367     Attrs = CS.getAttributes();
 368   }
 369   }
 370
 371   for (const Attribute &Attr : DeducedAttrs) {
 372     for (unsigned ArgNo : ArgNos) {
 373       if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
 374         continue;
 375
 376       HasChanged = ChangeStatus::CHANGED;
 377       bookkeeping(MP, Attr);
 378     }
 379   }
 380
 381   if (HasChanged == ChangeStatus::UNCHANGED)
 382     return HasChanged;
 383
 384   switch (MP) {
 385   case MP_ARGUMENT:
 386   case MP_FUNCTION:
 387   case MP_RETURNED:
 388     ScopeFn.setAttributes(Attrs);
 389     break;
 390   case MP_CALL_SITE_ARGUMENT:
 391     CallSite(&getAnchoredValue()).setAttributes(Attrs);
 392   }
 393
 394   return HasChanged;
 395 }
 396
 397 Function &AbstractAttribute::getAnchorScope() {
 398   Value &V = getAnchoredValue();
 399   if (isa<Function>(V))
 400     return cast<Function>(V);
 401   if (isa<Argument>(V))
 402     return *cast<Argument>(V).getParent();
 403   if (isa<Instruction>(V))
 404     return *cast<Instruction>(V).getFunction();
 405   llvm_unreachable("No scope for anchored value found!");
 406 }
 407
 408 const Function &AbstractAttribute::getAnchorScope() const {
 409   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 410 }
 411
 412 // Helper function that returns argument index of value.
 413 // If the value is not an argument, this returns -1.
 414 static int getArgNo(Value &V) {
 415   if (auto *Arg = dyn_cast<Argument>(&V))
 416     return Arg->getArgNo();
 417   return -1;
 418 }
 419
 420 /// -----------------------NoUnwind Function Attribute--------------------------
 421
 422 struct AANoUnwindFunction : AANoUnwind, BooleanState {
 423
 424   AANoUnwindFunction(Function &F, InformationCache &InfoCache)
 425       : AANoUnwind(F, InfoCache) {}
 426
 427   /// See AbstractAttribute::getState()
 428   /// {
 429   AbstractState &getState() override { return *this; }
 430   const AbstractState &getState() const override { return *this; }
 431   /// }
 432
 433   /// See AbstractAttribute::getManifestPosition().
 434   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 435
 436   const std::string getAsStr() const override {
 437     return getAssumed() ? "nounwind" : "may-unwind";
 438   }
 439
 440   /// See AbstractAttribute::updateImpl(...).
 441   ChangeStatus updateImpl(Attributor &A) override;
 442
 443   /// See AANoUnwind::isAssumedNoUnwind().
 444   bool isAssumedNoUnwind() const override { return getAssumed(); }
 445
 446   /// See AANoUnwind::isKnownNoUnwind().
 447   bool isKnownNoUnwind() const override { return getKnown(); }
 448 };
 449
 450 ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
 451   Function &F = getAnchorScope();
 452
 453   // The map from instruction opcodes to those instructions in the function.
 454   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 455   auto Opcodes = {
 456       (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
 457       (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
 458       (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
 459
 460   for (unsigned Opcode : Opcodes) {
 461     for (Instruction *I : OpcodeInstMap[Opcode]) {
 462       if (!I->mayThrow())
 463         continue;
 464
 465       auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
 466
 467       if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
 468         indicatePessimisticFixpoint();
 469         return ChangeStatus::CHANGED;
 470       }
 471     }
 472   }
 473   return ChangeStatus::UNCHANGED;
 474 }
 475
 476 /// --------------------- Function Return Values -------------------------------
 477
 478 /// "Attribute" that collects all potential returned values and the return
 479 /// instructions that they arise from.
 480 ///
 481 /// If there is a unique returned value R, the manifest method will:
 482 ///   - mark R with the "returned" attribute, if R is an argument.
 483 class AAReturnedValuesImpl final : public AAReturnedValues, AbstractState {
 484
 485   /// Mapping of values potentially returned by the associated function to the
 486   /// return instructions that might return them.
 487   DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> ReturnedValues;
 488
 489   /// State flags
 490   ///
 491   ///{
 492   bool IsFixed;
 493   bool IsValidState;
 494   bool HasOverdefinedReturnedCalls;
 495   ///}
 496
 497   /// Collect values that could become \p V in the set \p Values, each mapped to
 498   /// \p ReturnInsts.
 499   void collectValuesRecursively(
 500       Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
 501       DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> &Values) {
 502
 503     visitValueCB_t<bool> VisitValueCB = [&](Value *Val, bool &) {
 504       assert(!isa<Instruction>(Val) ||
 505              &getAnchorScope() == cast<Instruction>(Val)->getFunction());
 506       Values[Val].insert(ReturnInsts.begin(), ReturnInsts.end());
 507     };
 508
 509     bool UnusedBool;
 510     bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
 511
 512     // If we did abort the above traversal we haven't see all the values.
 513     // Consequently, we cannot know if the information we would derive is
 514     // accurate so we give up early.
 515     if (!Success)
 516       indicatePessimisticFixpoint();
 517   }
 518
 519 public:
 520   /// See AbstractAttribute::AbstractAttribute(...).
 521   AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
 522       : AAReturnedValues(F, InfoCache) {
 523     // We do not have an associated argument yet.
 524     AssociatedVal = nullptr;
 525   }
 526
 527   /// See AbstractAttribute::initialize(...).
 528   void initialize(Attributor &A) override {
 529     // Reset the state.
 530     AssociatedVal = nullptr;
 531     IsFixed = false;
 532     IsValidState = true;
 533     HasOverdefinedReturnedCalls = false;
 534     ReturnedValues.clear();
 535
 536     Function &F = cast<Function>(getAnchoredValue());
 537
 538     // The map from instruction opcodes to those instructions in the function.
 539     auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 540
 541     // Look through all arguments, if one is marked as returned we are done.
 542     for (Argument &Arg : F.args()) {
 543       if (Arg.hasReturnedAttr()) {
 544
 545         auto &ReturnInstSet = ReturnedValues[&Arg];
 546         for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
 547           ReturnInstSet.insert(cast<ReturnInst>(RI));
 548
 549         indicateOptimisticFixpoint();
 550         return;
 551       }
 552     }
 553
 554     // If no argument was marked as returned we look at all return instructions
 555     // and collect potentially returned values.
 556     for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) {
 557       SmallPtrSet<ReturnInst *, 1> RISet({cast<ReturnInst>(RI)});
 558       collectValuesRecursively(A, cast<ReturnInst>(RI)->getReturnValue(), RISet,
 559                                ReturnedValues);
 560     }
 561   }
 562
 563   /// See AbstractAttribute::manifest(...).
 564   ChangeStatus manifest(Attributor &A) override;
 565
 566   /// See AbstractAttribute::getState(...).
 567   AbstractState &getState() override { return *this; }
 568
 569   /// See AbstractAttribute::getState(...).
 570   const AbstractState &getState() const override { return *this; }
 571
 572   /// See AbstractAttribute::getManifestPosition().
 573   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
 574
 575   /// See AbstractAttribute::updateImpl(Attributor &A).
 576   ChangeStatus updateImpl(Attributor &A) override;
 577
 578   /// Return the number of potential return values, -1 if unknown.
 579   size_t getNumReturnValues() const {
 580     return isValidState() ? ReturnedValues.size() : -1;
 581   }
 582
 583   /// Return an assumed unique return value if a single candidate is found. If
 584   /// there cannot be one, return a nullptr. If it is not clear yet, return the
 585   /// Optional::NoneType.
 586   Optional<Value *> getAssumedUniqueReturnValue() const;
 587
 588   /// See AbstractState::checkForallReturnedValues(...).
 589   bool
 590   checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
 591
 592   /// Pretty print the attribute similar to the IR representation.
 593   const std::string getAsStr() const override;
 594
 595   /// See AbstractState::isAtFixpoint().
 596   bool isAtFixpoint() const override { return IsFixed; }
 597
 598   /// See AbstractState::isValidState().
 599   bool isValidState() const override { return IsValidState; }
 600
 601   /// See AbstractState::indicateOptimisticFixpoint(...).
 602   void indicateOptimisticFixpoint() override {
 603     IsFixed = true;
 604     IsValidState &= true;
 605   }
 606   void indicatePessimisticFixpoint() override {
 607     IsFixed = true;
 608     IsValidState = false;
 609   }
 610 };
 611
 612 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
 613   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 614
 615   // Bookkeeping.
 616   assert(isValidState());
 617   NumFnKnownReturns++;
 618
 619   // Check if we have an assumed unique return value that we could manifest.
 620   Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
 621
 622   if (!UniqueRV.hasValue() || !UniqueRV.getValue())
 623     return Changed;
 624
 625   // Bookkeeping.
 626   NumFnUniqueReturned++;
 627
 628   // If the assumed unique return value is an argument, annotate it.
 629   if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
 630     AssociatedVal = UniqueRVArg;
 631     Changed = AbstractAttribute::manifest(A) | Changed;
 632   }
 633
 634   return Changed;
 635 }
 636
 637 const std::string AAReturnedValuesImpl::getAsStr() const {
 638   return (isAtFixpoint() ? "returns(#" : "may-return(#") +
 639          (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
 640 }
 641
 642 Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue() const {
 643   // If checkForallReturnedValues provides a unique value, ignoring potential
 644   // undef values that can also be present, it is assumed to be the actual
 645   // return value and forwarded to the caller of this method. If there are
 646   // multiple, a nullptr is returned indicating there cannot be a unique
 647   // returned value.
 648   Optional<Value *> UniqueRV;
 649
 650   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
 651     // If we found a second returned value and neither the current nor the saved
 652     // one is an undef, there is no unique returned value. Undefs are special
 653     // since we can pretend they have any value.
 654     if (UniqueRV.hasValue() && UniqueRV != &RV &&
 655         !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
 656       UniqueRV = nullptr;
 657       return false;
 658     }
 659
 660     // Do not overwrite a value with an undef.
 661     if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
 662       UniqueRV = &RV;
 663
 664     return true;
 665   };
 666
 667   if (!checkForallReturnedValues(Pred))
 668     UniqueRV = nullptr;
 669
 670   return UniqueRV;
 671 }
 672
 673 bool AAReturnedValuesImpl::checkForallReturnedValues(
 674     std::function<bool(Value &)> &Pred) const {
 675   if (!isValidState())
 676     return false;
 677
 678   // Check all returned values but ignore call sites as long as we have not
 679   // encountered an overdefined one during an update.
 680   for (auto &It : ReturnedValues) {
 681     Value *RV = It.first;
 682
 683     ImmutableCallSite ICS(RV);
 684     if (ICS && !HasOverdefinedReturnedCalls)
 685       continue;
 686
 687     if (!Pred(*RV))
 688       return false;
 689   }
 690
 691   return true;
 692 }
 693
 694 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
 695
 696   // Check if we know of any values returned by the associated function,
 697   // if not, we are done.
 698   if (getNumReturnValues() == 0) {
 699     indicateOptimisticFixpoint();
 700     return ChangeStatus::UNCHANGED;
 701   }
 702
 703   // Check if any of the returned values is a call site we can refine.
 704   decltype(ReturnedValues) AddRVs;
 705   bool HasCallSite = false;
 706
 707   // Look at all returned call sites.
 708   for (auto &It : ReturnedValues) {
 709     SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
 710     Value *RV = It.first;
 711     LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
 712                       << "\n");
 713
 714     // Only call sites can change during an update, ignore the rest.
 715     CallSite RetCS(RV);
 716     if (!RetCS)
 717       continue;
 718
 719     // For now, any call site we see will prevent us from directly fixing the
 720     // state. However, if the information on the callees is fixed, the call
 721     // sites will be removed and we will fix the information for this state.
 722     HasCallSite = true;
 723
 724     // Try to find a assumed unique return value for the called function.
 725     auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
 726     if (!RetCSAA) {
 727       HasOverdefinedReturnedCalls = true;
 728       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
 729                         << ") with " << (RetCSAA ? "invalid" : "no")
 730                         << " associated state\n");
 731       continue;
 732     }
 733
 734     // Try to find a assumed unique return value for the called function.
 735     Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
 736
 737     // If no assumed unique return value was found due to the lack of
 738     // candidates, we may need to resolve more calls (through more update
 739     // iterations) or the called function will not return. Either way, we simply
 740     // stick with the call sites as return values. Because there were not
 741     // multiple possibilities, we do not treat it as overdefined.
 742     if (!AssumedUniqueRV.hasValue())
 743       continue;
 744
 745     // If multiple, non-refinable values were found, there cannot be a unique
 746     // return value for the called function. The returned call is overdefined!
 747     if (!AssumedUniqueRV.getValue()) {
 748       HasOverdefinedReturnedCalls = true;
 749       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
 750                            "potentially returned values\n");
 751       continue;
 752     }
 753
 754     LLVM_DEBUG({
 755       bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
 756       dbgs() << "[AAReturnedValues] Returned call site "
 757              << (UniqueRVIsKnown ? "known" : "assumed")
 758              << " unique return value: " << *AssumedUniqueRV << "\n";
 759     });
 760
 761     // The assumed unique return value.
 762     Value *AssumedRetVal = AssumedUniqueRV.getValue();
 763
 764     // If the assumed unique return value is an argument, lookup the matching
 765     // call site operand and recursively collect new returned values.
 766     // If it is not an argument, it is just put into the set of returned values
 767     // as we would have already looked through casts, phis, and similar values.
 768     if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
 769       collectValuesRecursively(A,
 770                                RetCS.getArgOperand(AssumedRetArg->getArgNo()),
 771                                ReturnInsts, AddRVs);
 772     else
 773       AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
 774   }
 775
 776   // Keep track of any change to trigger updates on dependent attributes.
 777   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 778
 779   for (auto &It : AddRVs) {
 780     assert(!It.second.empty() && "Entry does not add anything.");
 781     auto &ReturnInsts = ReturnedValues[It.first];
 782     for (ReturnInst *RI : It.second)
 783       if (ReturnInsts.insert(RI).second) {
 784         LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
 785                           << *It.first << " => " << *RI << "\n");
 786         Changed = ChangeStatus::CHANGED;
 787       }
 788   }
 789
 790   // If there is no call site in the returned values we are done.
 791   if (!HasCallSite) {
 792     indicateOptimisticFixpoint();
 793     return ChangeStatus::CHANGED;
 794   }
 795
 796   return Changed;
 797 }
 798
 799 /// ------------------------ NoSync Function Attribute -------------------------
 800
 801 struct AANoSyncFunction : AANoSync, BooleanState {
 802
 803   AANoSyncFunction(Function &F, InformationCache &InfoCache)
 804       : AANoSync(F, InfoCache) {}
 805
 806   /// See AbstractAttribute::getState()
 807   /// {
 808   AbstractState &getState() override { return *this; }
 809   const AbstractState &getState() const override { return *this; }
 810   /// }
 811
 812   /// See AbstractAttribute::getManifestPosition().
 813   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 814
 815   const std::string getAsStr() const override {
 816     return getAssumed() ? "nosync" : "may-sync";
 817   }
 818
 819   /// See AbstractAttribute::updateImpl(...).
 820   ChangeStatus updateImpl(Attributor &A) override;
 821
 822   /// See AANoSync::isAssumedNoSync()
 823   bool isAssumedNoSync() const override { return getAssumed(); }
 824
 825   /// See AANoSync::isKnownNoSync()
 826   bool isKnownNoSync() const override { return getKnown(); }
 827
 828   /// Helper function used to determine whether an instruction is non-relaxed
 829   /// atomic. In other words, if an atomic instruction does not have unordered
 830   /// or monotonic ordering
 831   static bool isNonRelaxedAtomic(Instruction *I);
 832
 833   /// Helper function used to determine whether an instruction is volatile.
 834   static bool isVolatile(Instruction *I);
 835
 836   /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
 837   /// memset).
 838   static bool isNoSyncIntrinsic(Instruction *I);
 839 };
 840
 841 bool AANoSyncFunction::isNonRelaxedAtomic(Instruction *I) {
 842   if (!I->isAtomic())
 843     return false;
 844
 845   AtomicOrdering Ordering;
 846   switch (I->getOpcode()) {
 847   case Instruction::AtomicRMW:
 848     Ordering = cast<AtomicRMWInst>(I)->getOrdering();
 849     break;
 850   case Instruction::Store:
 851     Ordering = cast<StoreInst>(I)->getOrdering();
 852     break;
 853   case Instruction::Load:
 854     Ordering = cast<LoadInst>(I)->getOrdering();
 855     break;
 856   case Instruction::Fence: {
 857     auto *FI = cast<FenceInst>(I);
 858     if (FI->getSyncScopeID() == SyncScope::SingleThread)
 859       return false;
 860     Ordering = FI->getOrdering();
 861     break;
 862   }
 863   case Instruction::AtomicCmpXchg: {
 864     AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
 865     AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
 866     // Only if both are relaxed, than it can be treated as relaxed.
 867     // Otherwise it is non-relaxed.
 868     if (Success != AtomicOrdering::Unordered &&
 869         Success != AtomicOrdering::Monotonic)
 870       return true;
 871     if (Failure != AtomicOrdering::Unordered &&
 872         Failure != AtomicOrdering::Monotonic)
 873       return true;
 874     return false;
 875   }
 876   default:
 877     llvm_unreachable(
 878         "New atomic operations need to be known in the attributor.");
 879   }
 880
 881   // Relaxed.
 882   if (Ordering == AtomicOrdering::Unordered ||
 883       Ordering == AtomicOrdering::Monotonic)
 884     return false;
 885   return true;
 886 }
 887
 888 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
 889 /// FIXME: We should ipmrove the handling of intrinsics.
 890 bool AANoSyncFunction::isNoSyncIntrinsic(Instruction *I) {
 891   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
 892     switch (II->getIntrinsicID()) {
 893     /// Element wise atomic memory intrinsics are can only be unordered,
 894     /// therefore nosync.
 895     case Intrinsic::memset_element_unordered_atomic:
 896     case Intrinsic::memmove_element_unordered_atomic:
 897     case Intrinsic::memcpy_element_unordered_atomic:
 898       return true;
 899     case Intrinsic::memset:
 900     case Intrinsic::memmove:
 901     case Intrinsic::memcpy:
 902       if (!cast<MemIntrinsic>(II)->isVolatile())
 903         return true;
 904       return false;
 905     default:
 906       return false;
 907     }
 908   }
 909   return false;
 910 }
 911
 912 bool AANoSyncFunction::isVolatile(Instruction *I) {
 913   assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
 914          "Calls should not be checked here");
 915
 916   switch (I->getOpcode()) {
 917   case Instruction::AtomicRMW:
 918     return cast<AtomicRMWInst>(I)->isVolatile();
 919   case Instruction::Store:
 920     return cast<StoreInst>(I)->isVolatile();
 921   case Instruction::Load:
 922     return cast<LoadInst>(I)->isVolatile();
 923   case Instruction::AtomicCmpXchg:
 924     return cast<AtomicCmpXchgInst>(I)->isVolatile();
 925   default:
 926     return false;
 927   }
 928 }
 929
 930 ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
 931   Function &F = getAnchorScope();
 932
 933   /// We are looking for volatile instructions or Non-Relaxed atomics.
 934   /// FIXME: We should ipmrove the handling of intrinsics.
 935   for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) {
 936     ImmutableCallSite ICS(I);
 937     auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
 938
 939     if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
 940       continue;
 941
 942     if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
 943         !ICS.hasFnAttr(Attribute::NoSync)) {
 944       indicatePessimisticFixpoint();
 945       return ChangeStatus::CHANGED;
 946     }
 947
 948     if (ICS)
 949       continue;
 950
 951     if (!isVolatile(I) && !isNonRelaxedAtomic(I))
 952       continue;
 953
 954     indicatePessimisticFixpoint();
 955     return ChangeStatus::CHANGED;
 956   }
 957
 958   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 959   auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
 960                   (unsigned)Instruction::Call};
 961
 962   for (unsigned Opcode : Opcodes) {
 963     for (Instruction *I : OpcodeInstMap[Opcode]) {
 964       // At this point we handled all read/write effects and they are all
 965       // nosync, so they can be skipped.
 966       if (I->mayReadOrWriteMemory())
 967         continue;
 968
 969       ImmutableCallSite ICS(I);
 970
 971       // non-convergent and readnone imply nosync.
 972       if (!ICS.isConvergent())
 973         continue;
 974
 975       indicatePessimisticFixpoint();
 976       return ChangeStatus::CHANGED;
 977     }
 978   }
 979
 980   return ChangeStatus::UNCHANGED;
 981 }
 982
 983 /// ------------------------ No-Free Attributes ----------------------------
 984
 985 struct AANoFreeFunction : AbstractAttribute, BooleanState {
 986
 987   /// See AbstractAttribute::AbstractAttribute(...).
 988   AANoFreeFunction(Function &F, InformationCache &InfoCache)
 989       : AbstractAttribute(F, InfoCache) {}
 990
 991   /// See AbstractAttribute::getState()
 992   ///{
 993   AbstractState &getState() override { return *this; }
 994   const AbstractState &getState() const override { return *this; }
 995   ///}
 996
 997   /// See AbstractAttribute::getManifestPosition().
 998   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
 999
1000   /// See AbstractAttribute::getAsStr().
1001   const std::string getAsStr() const override {
1002     return getAssumed() ? "nofree" : "may-free";
1003   }
1004
1005   /// See AbstractAttribute::updateImpl(...).
1006   ChangeStatus updateImpl(Attributor &A) override;
1007
1008   /// See AbstractAttribute::getAttrKind().
1009   Attribute::AttrKind getAttrKind() const override { return ID; }
1010
1011   /// Return true if "nofree" is assumed.
1012   bool isAssumedNoFree() const { return getAssumed(); }
1013
1014   /// Return true if "nofree" is known.
1015   bool isKnownNoFree() const { return getKnown(); }
1016
1017   /// The identifier used by the Attributor for this class of attributes.
1018   static constexpr Attribute::AttrKind ID = Attribute::NoFree;
1019 };
1020
1021 ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
1022   Function &F = getAnchorScope();
1023
1024   // The map from instruction opcodes to those instructions in the function.
1025   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1026
1027   for (unsigned Opcode :
1028        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1029         (unsigned)Instruction::Call}) {
1030     for (Instruction *I : OpcodeInstMap[Opcode]) {
1031
1032       auto ICS = ImmutableCallSite(I);
1033       auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
1034
1035       if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
1036           !ICS.hasFnAttr(Attribute::NoFree)) {
1037         indicatePessimisticFixpoint();
1038         return ChangeStatus::CHANGED;
1039       }
1040     }
1041   }
1042   return ChangeStatus::UNCHANGED;
1043 }
1044
1045 /// ------------------------ NonNull Argument Attribute ------------------------
1046 struct AANonNullImpl : AANonNull, BooleanState {
1047
1048   AANonNullImpl(Value &V, InformationCache &InfoCache)
1049       : AANonNull(V, InfoCache) {}
1050
1051   AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue,
1052                 InformationCache &InfoCache)
1053       : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1054
1055   /// See AbstractAttribute::getState()
1056   /// {
1057   AbstractState &getState() override { return *this; }
1058   const AbstractState &getState() const override { return *this; }
1059   /// }
1060
1061   /// See AbstractAttribute::getAsStr().
1062   const std::string getAsStr() const override {
1063     return getAssumed() ? "nonnull" : "may-null";
1064   }
1065
1066   /// See AANonNull::isAssumedNonNull().
1067   bool isAssumedNonNull() const override { return getAssumed(); }
1068
1069   /// See AANonNull::isKnownNonNull().
1070   bool isKnownNonNull() const override { return getKnown(); }
1071
1072   /// Generate a predicate that checks if a given value is assumed nonnull.
1073   /// The generated function returns true if a value satisfies any of
1074   /// following conditions.
1075   /// (i) A value is known nonZero(=nonnull).
1076   /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
1077   /// true.
1078   std::function<bool(Value &)> generatePredicate(Attributor &);
1079 };
1080
1081 std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
1082   // FIXME: The `AAReturnedValues` should provide the predicate with the
1083   // `ReturnInst` vector as well such that we can use the control flow sensitive
1084   // version of `isKnownNonZero`. This should fix `test11` in
1085   // `test/Transforms/FunctionAttrs/nonnull.ll`
1086
1087   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1088     if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1089       return true;
1090
1091     auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1092
1093     ImmutableCallSite ICS(&RV);
1094
1095     if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
1096         (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
1097       return false;
1098
1099     return true;
1100   };
1101
1102   return Pred;
1103 }
1104
1105 /// NonNull attribute for function return value.
1106 struct AANonNullReturned : AANonNullImpl {
1107
1108   AANonNullReturned(Function &F, InformationCache &InfoCache)
1109       : AANonNullImpl(F, InfoCache) {}
1110
1111   /// See AbstractAttribute::getManifestPosition().
1112   ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1113
1114   /// See AbstractAttriubute::initialize(...).
1115   void initialize(Attributor &A) override {
1116     Function &F = getAnchorScope();
1117
1118     // Already nonnull.
1119     if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1120                                        Attribute::NonNull) ||
1121         F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1122                                        Attribute::Dereferenceable))
1123       indicateOptimisticFixpoint();
1124   }
1125
1126   /// See AbstractAttribute::updateImpl(...).
1127   ChangeStatus updateImpl(Attributor &A) override;
1128 };
1129
1130 ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
1131   Function &F = getAnchorScope();
1132
1133   auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1134   if (!AARetVal) {
1135     indicatePessimisticFixpoint();
1136     return ChangeStatus::CHANGED;
1137   }
1138
1139   std::function<bool(Value &)> Pred = this->generatePredicate(A);
1140   if (!AARetVal->checkForallReturnedValues(Pred)) {
1141     indicatePessimisticFixpoint();
1142     return ChangeStatus::CHANGED;
1143   }
1144   return ChangeStatus::UNCHANGED;
1145 }
1146
1147 /// NonNull attribute for function argument.
1148 struct AANonNullArgument : AANonNullImpl {
1149
1150   AANonNullArgument(Argument &A, InformationCache &InfoCache)
1151       : AANonNullImpl(A, InfoCache) {}
1152
1153   /// See AbstractAttribute::getManifestPosition().
1154   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1155
1156   /// See AbstractAttriubute::initialize(...).
1157   void initialize(Attributor &A) override {
1158     Argument *Arg = cast<Argument>(getAssociatedValue());
1159     if (Arg->hasNonNullAttr())
1160       indicateOptimisticFixpoint();
1161   }
1162
1163   /// See AbstractAttribute::updateImpl(...).
1164   ChangeStatus updateImpl(Attributor &A) override;
1165 };
1166
1167 /// NonNull attribute for a call site argument.
1168 struct AANonNullCallSiteArgument : AANonNullImpl {
1169
1170   /// See AANonNullImpl::AANonNullImpl(...).
1171   AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
1172                             InformationCache &InfoCache)
1173       : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1174         ArgNo(ArgNo) {}
1175
1176   /// See AbstractAttribute::initialize(...).
1177   void initialize(Attributor &A) override {
1178     CallSite CS(&getAnchoredValue());
1179     if (CS.paramHasAttr(ArgNo, getAttrKind()) ||
1180         CS.paramHasAttr(ArgNo, Attribute::Dereferenceable) ||
1181         isKnownNonZero(getAssociatedValue(),
1182                        getAnchorScope().getParent()->getDataLayout()))
1183       indicateOptimisticFixpoint();
1184   }
1185
1186   /// See AbstractAttribute::updateImpl(Attributor &A).
1187   ChangeStatus updateImpl(Attributor &A) override;
1188
1189   /// See AbstractAttribute::getManifestPosition().
1190   ManifestPosition getManifestPosition() const override {
1191     return MP_CALL_SITE_ARGUMENT;
1192   };
1193
1194   // Return argument index of associated value.
1195   int getArgNo() const { return ArgNo; }
1196
1197 private:
1198   unsigned ArgNo;
1199 };
1200 ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
1201   Function &F = getAnchorScope();
1202   Argument &Arg = cast<Argument>(getAnchoredValue());
1203
1204   unsigned ArgNo = Arg.getArgNo();
1205
1206   // Callback function
1207   std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1208     assert(CS && "Sanity check: Call site was not initialized properly!");
1209
1210     auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1211
1212     // Check that NonNullAA is AANonNullCallSiteArgument.
1213     if (NonNullAA) {
1214       ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1215       if (ICS && CS.getInstruction() == ICS.getInstruction())
1216         return NonNullAA->isAssumedNonNull();
1217       return false;
1218     }
1219
1220     if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1221       return true;
1222
1223     Value *V = CS.getArgOperand(ArgNo);
1224     if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1225       return true;
1226
1227     return false;
1228   };
1229   if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1230     indicatePessimisticFixpoint();
1231     return ChangeStatus::CHANGED;
1232   }
1233   return ChangeStatus::UNCHANGED;
1234 }
1235
1236 ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
1237   // NOTE: Never look at the argument of the callee in this method.
1238   //       If we do this, "nonnull" is always deduced because of the assumption.
1239
1240   Value &V = *getAssociatedValue();
1241
1242   auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1243
1244   if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
1245     indicatePessimisticFixpoint();
1246     return ChangeStatus::CHANGED;
1247   }
1248
1249   return ChangeStatus::UNCHANGED;
1250 }
1251
1252 /// ------------------------ Will-Return Attributes ----------------------------
1253
1254 struct AAWillReturnImpl : public AAWillReturn, BooleanState {
1255
1256   /// See AbstractAttribute::AbstractAttribute(...).
1257   AAWillReturnImpl(Function &F, InformationCache &InfoCache)
1258       : AAWillReturn(F, InfoCache) {}
1259
1260   /// See AAWillReturn::isKnownWillReturn().
1261   bool isKnownWillReturn() const override { return getKnown(); }
1262
1263   /// See AAWillReturn::isAssumedWillReturn().
1264   bool isAssumedWillReturn() const override { return getAssumed(); }
1265
1266   /// See AbstractAttribute::getState(...).
1267   AbstractState &getState() override { return *this; }
1268
1269   /// See AbstractAttribute::getState(...).
1270   const AbstractState &getState() const override { return *this; }
1271
1272   /// See AbstractAttribute::getAsStr()
1273   const std::string getAsStr() const override {
1274     return getAssumed() ? "willreturn" : "may-noreturn";
1275   }
1276 };
1277
1278 struct AAWillReturnFunction final : AAWillReturnImpl {
1279
1280   /// See AbstractAttribute::AbstractAttribute(...).
1281   AAWillReturnFunction(Function &F, InformationCache &InfoCache)
1282       : AAWillReturnImpl(F, InfoCache) {}
1283
1284   /// See AbstractAttribute::getManifestPosition().
1285   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
1286
1287   /// See AbstractAttribute::initialize(...).
1288   void initialize(Attributor &A) override;
1289
1290   /// See AbstractAttribute::updateImpl(...).
1291   ChangeStatus updateImpl(Attributor &A) override;
1292 };
1293
1294 // Helper function that checks whether a function has any cycle.
1295 // TODO: Replace with more efficent code
1296 bool containsCycle(Function &F) {
1297   SmallPtrSet<BasicBlock *, 32> Visited;
1298
1299   // Traverse BB by dfs and check whether successor is already visited.
1300   for (BasicBlock *BB : depth_first(&F)) {
1301     Visited.insert(BB);
1302     for (auto *SuccBB : successors(BB)) {
1303       if (Visited.count(SuccBB))
1304         return true;
1305     }
1306   }
1307   return false;
1308 }
1309
1310 // Helper function that checks the function have a loop which might become an
1311 // endless loop
1312 // FIXME: Any cycle is regarded as endless loop for now.
1313 //        We have to allow some patterns.
1314 bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); }
1315
1316 void AAWillReturnFunction::initialize(Attributor &A) {
1317   Function &F = getAnchorScope();
1318
1319   if (containsPossiblyEndlessLoop(F))
1320     indicatePessimisticFixpoint();
1321 }
1322
1323 ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
1324   Function &F = getAnchorScope();
1325
1326   // The map from instruction opcodes to those instructions in the function.
1327   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1328
1329   for (unsigned Opcode :
1330        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1331         (unsigned)Instruction::Call}) {
1332     for (Instruction *I : OpcodeInstMap[Opcode]) {
1333       auto ICS = ImmutableCallSite(I);
1334
1335       if (ICS.hasFnAttr(Attribute::WillReturn))
1336         continue;
1337
1338       auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1339       if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
1340         indicatePessimisticFixpoint();
1341         return ChangeStatus::CHANGED;
1342       }
1343
1344       auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1345
1346       // FIXME: (i) Prohibit any recursion for now.
1347       //        (ii) AANoRecurse isn't implemented yet so currently any call is
1348       //        regarded as having recursion.
1349       //       Code below should be
1350       //       if ((!NoRecurseAA || !NoRecurseAA->isAssumedNoRecurse()) &&
1351       if (!NoRecurseAA && !ICS.hasFnAttr(Attribute::NoRecurse)) {
1352         indicatePessimisticFixpoint();
1353         return ChangeStatus::CHANGED;
1354       }
1355     }
1356   }
1357
1358   return ChangeStatus::UNCHANGED;
1359 }
1360
1361 /// ------------------------ NoAlias Argument Attribute ------------------------
1362
1363 struct AANoAliasImpl : AANoAlias, BooleanState {
1364
1365   AANoAliasImpl(Value &V, InformationCache &InfoCache)
1366       : AANoAlias(V, InfoCache) {}
1367
1368   /// See AbstractAttribute::getState()
1369   /// {
1370   AbstractState &getState() override { return *this; }
1371   const AbstractState &getState() const override { return *this; }
1372   /// }
1373
1374   const std::string getAsStr() const override {
1375     return getAssumed() ? "noalias" : "may-alias";
1376   }
1377
1378   /// See AANoAlias::isAssumedNoAlias().
1379   bool isAssumedNoAlias() const override { return getAssumed(); }
1380
1381   /// See AANoAlias::isKnowndNoAlias().
1382   bool isKnownNoAlias() const override { return getKnown(); }
1383 };
1384
1385 /// NoAlias attribute for function return value.
1386 struct AANoAliasReturned : AANoAliasImpl {
1387
1388   AANoAliasReturned(Function &F, InformationCache &InfoCache)
1389       : AANoAliasImpl(F, InfoCache) {}
1390
1391   /// See AbstractAttribute::getManifestPosition().
1392   virtual ManifestPosition getManifestPosition() const override {
1393     return MP_RETURNED;
1394   }
1395
1396   /// See AbstractAttriubute::initialize(...).
1397   void initialize(Attributor &A) override {
1398     Function &F = getAnchorScope();
1399
1400     // Already noalias.
1401     if (F.returnDoesNotAlias()) {
1402       indicateOptimisticFixpoint();
1403       return;
1404     }
1405   }
1406
1407   /// See AbstractAttribute::updateImpl(...).
1408   virtual ChangeStatus updateImpl(Attributor &A) override;
1409 };
1410
1411 ChangeStatus AANoAliasReturned::updateImpl(Attributor &A) {
1412   Function &F = getAnchorScope();
1413
1414   auto *AARetValImpl = A.getAAFor<AAReturnedValuesImpl>(*this, F);
1415   if (!AARetValImpl) {
1416     indicatePessimisticFixpoint();
1417     return ChangeStatus::CHANGED;
1418   }
1419
1420   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1421     if (Constant *C = dyn_cast<Constant>(&RV))
1422       if (C->isNullValue() || isa<UndefValue>(C))
1423         return true;
1424
1425     /// For now, we can only deduce noalias if we have call sites.
1426     /// FIXME: add more support.
1427     ImmutableCallSite ICS(&RV);
1428     if (!ICS)
1429       return false;
1430
1431     auto *NoAliasAA = A.getAAFor<AANoAlias>(*this, RV);
1432
1433     if (!ICS.returnDoesNotAlias() &&
1434         (!NoAliasAA || !NoAliasAA->isAssumedNoAlias()))
1435       return false;
1436
1437     /// FIXME: We can improve capture check in two ways:
1438     /// 1. Use the AANoCapture facilities.
1439     /// 2. Use the location of return insts for escape queries.
1440     if (PointerMayBeCaptured(&RV, /* ReturnCaptures */ false,
1441                              /* StoreCaptures */ true))
1442       return false;
1443
1444     return true;
1445   };
1446
1447   if (!AARetValImpl->checkForallReturnedValues(Pred)) {
1448     indicatePessimisticFixpoint();
1449     return ChangeStatus::CHANGED;
1450   }
1451
1452   return ChangeStatus::UNCHANGED;
1453 }
1454
1455 /// -------------------AAIsDead Function Attribute-----------------------
1456
1457 struct AAIsDeadFunction : AAIsDead, BooleanState {
1458
1459   AAIsDeadFunction(Function &F, InformationCache &InfoCache)
1460       : AAIsDead(F, InfoCache) {}
1461
1462   /// See AbstractAttribute::getState()
1463   /// {
1464   AbstractState &getState() override { return *this; }
1465   const AbstractState &getState() const override { return *this; }
1466   /// }
1467
1468   /// See AbstractAttribute::getManifestPosition().
1469   ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
1470
1471   void initialize(Attributor &A) override {
1472     Function &F = getAnchorScope();
1473
1474     ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
1475     AssumedLiveBlocks.insert(&(F.getEntryBlock()));
1476     for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
1477       explorePath(A, ToBeExploredPaths[i]);
1478   }
1479
1480   /// Explores new instructions starting from \p I. If instruction is dead, stop
1481   /// and return true if it discovered a new instruction.
1482   bool explorePath(Attributor &A, Instruction *I);
1483
1484   const std::string getAsStr() const override {
1485     return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" +
1486            std::to_string(getAnchorScope().size()) + ")";
1487   }
1488
1489   /// See AbstractAttribute::manifest(...).
1490   ChangeStatus manifest(Attributor &A) override {
1491     assert(getState().isValidState() &&
1492            "Attempted to manifest an invalid state!");
1493
1494     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
1495
1496     for (Instruction *I : NoReturnCalls) {
1497       BasicBlock *BB = I->getParent();
1498
1499       /// Invoke is replaced with a call and unreachable is placed after it.
1500       if (auto *II = dyn_cast<InvokeInst>(I)) {
1501         changeToCall(II);
1502         changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1503         LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n");
1504         continue;
1505       }
1506
1507       SplitBlock(BB, I->getNextNode());
1508       changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1509       HasChanged = ChangeStatus::CHANGED;
1510     }
1511
1512     return HasChanged;
1513   }
1514
1515   /// See AbstractAttribute::updateImpl(...).
1516   ChangeStatus updateImpl(Attributor &A) override;
1517
1518   /// See AAIsDead::isAssumedDead().
1519   bool isAssumedDead(BasicBlock *BB) const override {
1520     if (!getAssumed())
1521       return false;
1522     return !AssumedLiveBlocks.count(BB);
1523   }
1524
1525   /// See AAIsDead::isKnownDead().
1526   bool isKnownDead(BasicBlock *BB) const override {
1527     if (!getKnown())
1528       return false;
1529     return !AssumedLiveBlocks.count(BB);
1530   }
1531
1532   /// Collection of to be explored paths.
1533   SmallSetVector<Instruction *, 8> ToBeExploredPaths;
1534
1535   /// Collection of all assumed live BasicBlocks.
1536   DenseSet<BasicBlock *> AssumedLiveBlocks;
1537
1538   /// Collection of calls with noreturn attribute, assumed or knwon.
1539   SmallSetVector<Instruction *, 4> NoReturnCalls;
1540 };
1541
1542 bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) {
1543   BasicBlock *BB = I->getParent();
1544
1545   while (I) {
1546     ImmutableCallSite ICS(I);
1547
1548     if (ICS) {
1549       auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
1550
1551       if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) {
1552         if (!NoReturnCalls.insert(I))
1553           // If I is already in the NoReturnCalls set, then it stayed noreturn
1554           // and we didn't discover any new instructions.
1555           return false;
1556
1557         // Discovered new noreturn call, return true to indicate that I is not
1558         // noreturn anymore and should be deleted from NoReturnCalls.
1559         return true;
1560       }
1561
1562       if (ICS.hasFnAttr(Attribute::NoReturn)) {
1563         if (!NoReturnCalls.insert(I))
1564           return false;
1565
1566         return true;
1567       }
1568     }
1569
1570     I = I->getNextNode();
1571   }
1572
1573   // get new paths (reachable blocks).
1574   for (BasicBlock *SuccBB : successors(BB)) {
1575     Instruction *Inst = &(SuccBB->front());
1576     AssumedLiveBlocks.insert(SuccBB);
1577     ToBeExploredPaths.insert(Inst);
1578   }
1579
1580   return true;
1581 }
1582
1583 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
1584   // Temporary collection to iterate over existing noreturn instructions. This
1585   // will alow easier modification of NoReturnCalls collection
1586   SmallVector<Instruction *, 8> NoReturnChanged;
1587   ChangeStatus Status = ChangeStatus::UNCHANGED;
1588
1589   for (Instruction *I : NoReturnCalls)
1590     NoReturnChanged.push_back(I);
1591
1592   for (Instruction *I : NoReturnChanged) {
1593     size_t Size = ToBeExploredPaths.size();
1594
1595     // Still noreturn.
1596     if (!explorePath(A, I))
1597       continue;
1598
1599     NoReturnCalls.remove(I);
1600
1601     // No new paths.
1602     if (Size == ToBeExploredPaths.size())
1603       continue;
1604
1605     // At least one new path.
1606     Status = ChangeStatus::CHANGED;
1607
1608     // explore new paths.
1609     while (Size != ToBeExploredPaths.size())
1610       explorePath(A, ToBeExploredPaths[Size++]);
1611   }
1612
1613   LLVM_DEBUG(
1614       dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size()
1615              << "Total number of blocks: " << getAnchorScope().size() << "\n");
1616
1617   return Status;
1618 }
1619
1620 /// -------------------- Dereferenceable Argument Attribute --------------------
1621
1622 struct DerefState : AbstractState {
1623
1624   /// State representing for dereferenceable bytes.
1625   IntegerState DerefBytesState;
1626
1627   /// State representing that whether the value is nonnull or global.
1628   IntegerState NonNullGlobalState;
1629
1630   /// Bits encoding for NonNullGlobalState.
1631   enum {
1632     DEREF_NONNULL = 1 << 0,
1633     DEREF_GLOBAL = 1 << 1,
1634   };
1635
1636   /// See AbstractState::isValidState()
1637   bool isValidState() const override { return DerefBytesState.isValidState(); }
1638
1639   // See AbstractState::isAtFixpoint()
1640   bool isAtFixpoint() const override {
1641     return DerefBytesState.isAtFixpoint() && NonNullGlobalState.isAtFixpoint();
1642   }
1643
1644   /// See AbstractState::indicateOptimisticFixpoint(...)
1645   void indicateOptimisticFixpoint() override {
1646     DerefBytesState.indicateOptimisticFixpoint();
1647     NonNullGlobalState.indicateOptimisticFixpoint();
1648   }
1649
1650   /// See AbstractState::indicatePessimisticFixpoint(...)
1651   void indicatePessimisticFixpoint() override {
1652     DerefBytesState.indicatePessimisticFixpoint();
1653     NonNullGlobalState.indicatePessimisticFixpoint();
1654   }
1655
1656   /// Update known dereferenceable bytes.
1657   void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1658     DerefBytesState.takeKnownMaximum(Bytes);
1659   }
1660
1661   /// Update assumed dereferenceable bytes.
1662   void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1663     DerefBytesState.takeAssumedMinimum(Bytes);
1664   }
1665
1666   /// Update assumed NonNullGlobalState
1667   void updateAssumedNonNullGlobalState(bool IsNonNull, bool IsGlobal) {
1668     if (!IsNonNull)
1669       NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1670     if (!IsGlobal)
1671       NonNullGlobalState.removeAssumedBits(DEREF_GLOBAL);
1672   }
1673
1674   /// Equality for DerefState.
1675   bool operator==(const DerefState &R) {
1676     return this->DerefBytesState == R.DerefBytesState &&
1677            this->NonNullGlobalState == R.NonNullGlobalState;
1678   }
1679 };
1680 struct AADereferenceableImpl : AADereferenceable, DerefState {
1681
1682   AADereferenceableImpl(Value &V, InformationCache &InfoCache)
1683       : AADereferenceable(V, InfoCache) {}
1684
1685   AADereferenceableImpl(Value *AssociatedVal, Value &AnchoredValue,
1686                         InformationCache &InfoCache)
1687       : AADereferenceable(AssociatedVal, AnchoredValue, InfoCache) {}
1688
1689   /// See AbstractAttribute::getState()
1690   /// {
1691   AbstractState &getState() override { return *this; }
1692   const AbstractState &getState() const override { return *this; }
1693   /// }
1694
1695   /// See AADereferenceable::getAssumedDereferenceableBytes().
1696   uint32_t getAssumedDereferenceableBytes() const override {
1697     return DerefBytesState.getAssumed();
1698   }
1699
1700   /// See AADereferenceable::getKnownDereferenceableBytes().
1701   uint32_t getKnownDereferenceableBytes() const override {
1702     return DerefBytesState.getKnown();
1703   }
1704
1705   // Helper function for syncing nonnull state.
1706   void syncNonNull(const AANonNull *NonNullAA) {
1707     if (!NonNullAA) {
1708       NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1709       return;
1710     }
1711
1712     if (NonNullAA->isKnownNonNull())
1713       NonNullGlobalState.addKnownBits(DEREF_NONNULL);
1714
1715     if (!NonNullAA->isAssumedNonNull())
1716       NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1717   }
1718
1719   /// See AADereferenceable::isAssumedGlobal().
1720   bool isAssumedGlobal() const override {
1721     return NonNullGlobalState.isAssumed(DEREF_GLOBAL);
1722   }
1723
1724   /// See AADereferenceable::isKnownGlobal().
1725   bool isKnownGlobal() const override {
1726     return NonNullGlobalState.isKnown(DEREF_GLOBAL);
1727   }
1728
1729   /// See AADereferenceable::isAssumedNonNull().
1730   bool isAssumedNonNull() const override {
1731     return NonNullGlobalState.isAssumed(DEREF_NONNULL);
1732   }
1733
1734   /// See AADereferenceable::isKnownNonNull().
1735   bool isKnownNonNull() const override {
1736     return NonNullGlobalState.isKnown(DEREF_NONNULL);
1737   }
1738
1739   void getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
1740     LLVMContext &Ctx = AnchoredVal.getContext();
1741
1742     // TODO: Add *_globally support
1743     if (isAssumedNonNull())
1744       Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
1745           Ctx, getAssumedDereferenceableBytes()));
1746     else
1747       Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
1748           Ctx, getAssumedDereferenceableBytes()));
1749   }
1750   uint64_t computeAssumedDerefenceableBytes(Attributor &A, Value &V,
1751                                             bool &IsNonNull, bool &IsGlobal);
1752
1753   void initialize(Attributor &A) override {
1754     Function &F = getAnchorScope();
1755     unsigned AttrIdx =
1756         getAttrIndex(getManifestPosition(), getArgNo(getAnchoredValue()));
1757
1758     for (Attribute::AttrKind AK :
1759          {Attribute::Dereferenceable, Attribute::DereferenceableOrNull})
1760       if (F.getAttributes().hasAttribute(AttrIdx, AK))
1761         takeKnownDerefBytesMaximum(F.getAttribute(AttrIdx, AK).getValueAsInt());
1762   }
1763
1764   /// See AbstractAttribute::getAsStr().
1765   const std::string getAsStr() const override {
1766     if (!getAssumedDereferenceableBytes())
1767       return "unknown-dereferenceable";
1768     return std::string("dereferenceable") +
1769            (isAssumedNonNull() ? "" : "_or_null") +
1770            (isAssumedGlobal() ? "_globally" : "") + "<" +
1771            std::to_string(getKnownDereferenceableBytes()) + "-" +
1772            std::to_string(getAssumedDereferenceableBytes()) + ">";
1773   }
1774 };
1775
1776 struct AADereferenceableReturned : AADereferenceableImpl {
1777   AADereferenceableReturned(Function &F, InformationCache &InfoCache)
1778       : AADereferenceableImpl(F, InfoCache) {}
1779
1780   /// See AbstractAttribute::getManifestPosition().
1781   ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1782
1783   /// See AbstractAttribute::updateImpl(...).
1784   ChangeStatus updateImpl(Attributor &A) override;
1785 };
1786
1787 // Helper function that returns dereferenceable bytes.
1788 static uint64_t calcDifferenceIfBaseIsNonNull(int64_t DerefBytes,
1789                                               int64_t Offset, bool IsNonNull) {
1790   if (!IsNonNull)
1791     return 0;
1792   return std::max((int64_t)0, DerefBytes - Offset);
1793 }
1794
1795 uint64_t AADereferenceableImpl::computeAssumedDerefenceableBytes(
1796     Attributor &A, Value &V, bool &IsNonNull, bool &IsGlobal) {
1797   // TODO: Tracking the globally flag.
1798   IsGlobal = false;
1799
1800   // First, we try to get information about V from Attributor.
1801   if (auto *DerefAA = A.getAAFor<AADereferenceable>(*this, V)) {
1802     IsNonNull &= DerefAA->isAssumedNonNull();
1803     return DerefAA->getAssumedDereferenceableBytes();
1804   }
1805
1806   // Otherwise, we try to compute assumed bytes from base pointer.
1807   const DataLayout &DL = getAnchorScope().getParent()->getDataLayout();
1808   unsigned IdxWidth =
1809       DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
1810   APInt Offset(IdxWidth, 0);
1811   Value *Base = V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1812
1813   if (auto *BaseDerefAA = A.getAAFor<AADereferenceable>(*this, *Base)) {
1814     IsNonNull &= Offset != 0;
1815     return calcDifferenceIfBaseIsNonNull(
1816         BaseDerefAA->getAssumedDereferenceableBytes(), Offset.getSExtValue(),
1817         Offset != 0 || BaseDerefAA->isAssumedNonNull());
1818   }
1819
1820   // Then, use IR information.
1821
1822   if (isDereferenceablePointer(Base, Base->getType(), DL))
1823     return calcDifferenceIfBaseIsNonNull(
1824         DL.getTypeStoreSize(Base->getType()->getPointerElementType()),
1825         Offset.getSExtValue(),
1826         !NullPointerIsDefined(&getAnchorScope(),
1827                               V.getType()->getPointerAddressSpace()));
1828
1829   IsNonNull = false;
1830   return 0;
1831 }
1832 ChangeStatus AADereferenceableReturned::updateImpl(Attributor &A) {
1833   Function &F = getAnchorScope();
1834   auto BeforeState = static_cast<DerefState>(*this);
1835
1836   syncNonNull(A.getAAFor<AANonNull>(*this, F));
1837
1838   auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1839   if (!AARetVal) {
1840     indicatePessimisticFixpoint();
1841     return ChangeStatus::CHANGED;
1842   }
1843
1844   bool IsNonNull = isAssumedNonNull();
1845   bool IsGlobal = isAssumedGlobal();
1846
1847   std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1848     takeAssumedDerefBytesMinimum(
1849         computeAssumedDerefenceableBytes(A, RV, IsNonNull, IsGlobal));
1850     return isValidState();
1851   };
1852
1853   if (AARetVal->checkForallReturnedValues(Pred)) {
1854     updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1855     return BeforeState == static_cast<DerefState>(*this)
1856                ? ChangeStatus::UNCHANGED
1857                : ChangeStatus::CHANGED;
1858   }
1859   indicatePessimisticFixpoint();
1860   return ChangeStatus::CHANGED;
1861 }
1862
1863 struct AADereferenceableArgument : AADereferenceableImpl {
1864   AADereferenceableArgument(Argument &A, InformationCache &InfoCache)
1865       : AADereferenceableImpl(A, InfoCache) {}
1866
1867   /// See AbstractAttribute::getManifestPosition().
1868   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1869
1870   /// See AbstractAttribute::updateImpl(...).
1871   ChangeStatus updateImpl(Attributor &A) override;
1872 };
1873
1874 ChangeStatus AADereferenceableArgument::updateImpl(Attributor &A) {
1875   Function &F = getAnchorScope();
1876   Argument &Arg = cast<Argument>(getAnchoredValue());
1877
1878   auto BeforeState = static_cast<DerefState>(*this);
1879
1880   unsigned ArgNo = Arg.getArgNo();
1881
1882   syncNonNull(A.getAAFor<AANonNull>(*this, F, ArgNo));
1883
1884   bool IsNonNull = isAssumedNonNull();
1885   bool IsGlobal = isAssumedGlobal();
1886
1887   // Callback function
1888   std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
1889     assert(CS && "Sanity check: Call site was not initialized properly!");
1890
1891     // Check that DereferenceableAA is AADereferenceableCallSiteArgument.
1892     if (auto *DereferenceableAA =
1893             A.getAAFor<AADereferenceable>(*this, *CS.getInstruction(), ArgNo)) {
1894       ImmutableCallSite ICS(&DereferenceableAA->getAnchoredValue());
1895       if (ICS && CS.getInstruction() == ICS.getInstruction()) {
1896         takeAssumedDerefBytesMinimum(
1897             DereferenceableAA->getAssumedDereferenceableBytes());
1898         IsNonNull &= DereferenceableAA->isAssumedNonNull();
1899         IsGlobal &= DereferenceableAA->isAssumedGlobal();
1900         return isValidState();
1901       }
1902     }
1903
1904     takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(
1905         A, *CS.getArgOperand(ArgNo), IsNonNull, IsGlobal));
1906
1907     return isValidState();
1908   };
1909
1910   if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1911     indicatePessimisticFixpoint();
1912     return ChangeStatus::CHANGED;
1913   }
1914
1915   updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1916
1917   return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
1918                                                        : ChangeStatus::CHANGED;
1919 }
1920
1921 /// Dereferenceable attribute for a call site argument.
1922 struct AADereferenceableCallSiteArgument : AADereferenceableImpl {
1923
1924   /// See AADereferenceableImpl::AADereferenceableImpl(...).
1925   AADereferenceableCallSiteArgument(CallSite CS, unsigned ArgNo,
1926                                     InformationCache &InfoCache)
1927       : AADereferenceableImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(),
1928                               InfoCache),
1929         ArgNo(ArgNo) {}
1930
1931   /// See AbstractAttribute::initialize(...).
1932   void initialize(Attributor &A) override {
1933     CallSite CS(&getAnchoredValue());
1934     if (CS.paramHasAttr(ArgNo, Attribute::Dereferenceable))
1935       takeKnownDerefBytesMaximum(CS.getDereferenceableBytes(ArgNo));
1936
1937     if (CS.paramHasAttr(ArgNo, Attribute::DereferenceableOrNull))
1938       takeKnownDerefBytesMaximum(CS.getDereferenceableOrNullBytes(ArgNo));
1939   }
1940
1941   /// See AbstractAttribute::updateImpl(Attributor &A).
1942   ChangeStatus updateImpl(Attributor &A) override;
1943
1944   /// See AbstractAttribute::getManifestPosition().
1945   ManifestPosition getManifestPosition() const override {
1946     return MP_CALL_SITE_ARGUMENT;
1947   };
1948
1949   // Return argument index of associated value.
1950   int getArgNo() const { return ArgNo; }
1951
1952 private:
1953   unsigned ArgNo;
1954 };
1955
1956 ChangeStatus AADereferenceableCallSiteArgument::updateImpl(Attributor &A) {
1957   // NOTE: Never look at the argument of the callee in this method.
1958   //       If we do this, "dereferenceable" is always deduced because of the
1959   //       assumption.
1960
1961   Value &V = *getAssociatedValue();
1962
1963   auto BeforeState = static_cast<DerefState>(*this);
1964
1965   syncNonNull(A.getAAFor<AANonNull>(*this, getAnchoredValue(), ArgNo));
1966   bool IsNonNull = isAssumedNonNull();
1967   bool IsGlobal = isKnownGlobal();
1968
1969   takeAssumedDerefBytesMinimum(
1970       computeAssumedDerefenceableBytes(A, V, IsNonNull, IsGlobal));
1971   updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1972
1973   return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
1974                                                        : ChangeStatus::CHANGED;
1975 }
1976
1977 /// ----------------------------------------------------------------------------
1978 ///                               Attributor
1979 /// ----------------------------------------------------------------------------
1980
1981 bool Attributor::checkForAllCallSites(Function &F,
1982                                       std::function<bool(CallSite)> &Pred,
1983                                       bool RequireAllCallSites) {
1984   // We can try to determine information from
1985   // the call sites. However, this is only possible all call sites are known,
1986   // hence the function has internal linkage.
1987   if (RequireAllCallSites && !F.hasInternalLinkage()) {
1988     LLVM_DEBUG(
1989         dbgs()
1990         << "Attributor: Function " << F.getName()
1991         << " has no internal linkage, hence not all call sites are known\n");
1992     return false;
1993   }
1994
1995   for (const Use &U : F.uses()) {
1996
1997     CallSite CS(U.getUser());
1998     if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1999       if (!RequireAllCallSites)
2000         continue;
2001
2002       LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
2003                         << " is an invalid use of " << F.getName() << "\n");
2004       return false;
2005     }
2006
2007     if (Pred(CS))
2008       continue;
2009
2010     LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
2011                       << *CS.getInstruction() << "\n");
2012     return false;
2013   }
2014
2015   return true;
2016 }
2017
2018 ChangeStatus Attributor::run() {
2019   // Initialize all abstract attributes.
2020   for (AbstractAttribute *AA : AllAbstractAttributes)
2021     AA->initialize(*this);
2022
2023   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
2024                     << AllAbstractAttributes.size()
2025                     << " abstract attributes.\n");
2026
2027   // Now that all abstract attributes are collected and initialized we start
2028   // the abstract analysis.
2029
2030   unsigned IterationCounter = 1;
2031
2032   SmallVector<AbstractAttribute *, 64> ChangedAAs;
2033   SetVector<AbstractAttribute *> Worklist;
2034   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
2035
2036   do {
2037     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
2038                       << ", Worklist size: " << Worklist.size() << "\n");
2039
2040     // Add all abstract attributes that are potentially dependent on one that
2041     // changed to the work list.
2042     for (AbstractAttribute *ChangedAA : ChangedAAs) {
2043       auto &QuerriedAAs = QueryMap[ChangedAA];
2044       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
2045     }
2046
2047     // Reset the changed set.
2048     ChangedAAs.clear();
2049
2050     // Update all abstract attribute in the work list and record the ones that
2051     // changed.
2052     for (AbstractAttribute *AA : Worklist)
2053       if (AA->update(*this) == ChangeStatus::CHANGED)
2054         ChangedAAs.push_back(AA);
2055
2056     // Reset the work list and repopulate with the changed abstract attributes.
2057     // Note that dependent ones are added above.
2058     Worklist.clear();
2059     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
2060
2061   } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
2062
2063   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
2064                     << IterationCounter << "/" << MaxFixpointIterations
2065                     << " iterations\n");
2066
2067   bool FinishedAtFixpoint = Worklist.empty();
2068
2069   // Reset abstract arguments not settled in a sound fixpoint by now. This
2070   // happens when we stopped the fixpoint iteration early. Note that only the
2071   // ones marked as "changed" *and* the ones transitively depending on them
2072   // need to be reverted to a pessimistic state. Others might not be in a
2073   // fixpoint state but we can use the optimistic results for them anyway.
2074   SmallPtrSet<AbstractAttribute *, 32> Visited;
2075   for (unsigned u = 0; u < ChangedAAs.size(); u++) {
2076     AbstractAttribute *ChangedAA = ChangedAAs[u];
2077     if (!Visited.insert(ChangedAA).second)
2078       continue;
2079
2080     AbstractState &State = ChangedAA->getState();
2081     if (!State.isAtFixpoint()) {
2082       State.indicatePessimisticFixpoint();
2083
2084       NumAttributesTimedOut++;
2085     }
2086
2087     auto &QuerriedAAs = QueryMap[ChangedAA];
2088     ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
2089   }
2090
2091   LLVM_DEBUG({
2092     if (!Visited.empty())
2093       dbgs() << "\n[Attributor] Finalized " << Visited.size()
2094              << " abstract attributes.\n";
2095   });
2096
2097   unsigned NumManifested = 0;
2098   unsigned NumAtFixpoint = 0;
2099   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
2100   for (AbstractAttribute *AA : AllAbstractAttributes) {
2101     AbstractState &State = AA->getState();
2102
2103     // If there is not already a fixpoint reached, we can now take the
2104     // optimistic state. This is correct because we enforced a pessimistic one
2105     // on abstract attributes that were transitively dependent on a changed one
2106     // already above.
2107     if (!State.isAtFixpoint())
2108       State.indicateOptimisticFixpoint();
2109
2110     // If the state is invalid, we do not try to manifest it.
2111     if (!State.isValidState())
2112       continue;
2113
2114     // Manifest the state and record if we changed the IR.
2115     ChangeStatus LocalChange = AA->manifest(*this);
2116     ManifestChange = ManifestChange | LocalChange;
2117
2118     NumAtFixpoint++;
2119     NumManifested += (LocalChange == ChangeStatus::CHANGED);
2120   }
2121
2122   (void)NumManifested;
2123   (void)NumAtFixpoint;
2124   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
2125                     << " arguments while " << NumAtFixpoint
2126                     << " were in a valid fixpoint state\n");
2127
2128   // If verification is requested, we finished this run at a fixpoint, and the
2129   // IR was changed, we re-run the whole fixpoint analysis, starting at
2130   // re-initialization of the arguments. This re-run should not result in an IR
2131   // change. Though, the (virtual) state of attributes at the end of the re-run
2132   // might be more optimistic than the known state or the IR state if the better
2133   // state cannot be manifested.
2134   if (VerifyAttributor && FinishedAtFixpoint &&
2135       ManifestChange == ChangeStatus::CHANGED) {
2136     VerifyAttributor = false;
2137     ChangeStatus VerifyStatus = run();
2138     if (VerifyStatus != ChangeStatus::UNCHANGED)
2139       llvm_unreachable(
2140           "Attributor verification failed, re-run did result in an IR change "
2141           "even after a fixpoint was reached in the original run. (False "
2142           "positives possible!)");
2143     VerifyAttributor = true;
2144   }
2145
2146   NumAttributesManifested += NumManifested;
2147   NumAttributesValidFixpoint += NumAtFixpoint;
2148
2149   return ManifestChange;
2150 }
2151
2152 void Attributor::identifyDefaultAbstractAttributes(
2153     Function &F, InformationCache &InfoCache,
2154     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
2155
2156   // Every function can be nounwind.
2157   registerAA(*new AANoUnwindFunction(F, InfoCache));
2158
2159   // Every function might be marked "nosync"
2160   registerAA(*new AANoSyncFunction(F, InfoCache));
2161
2162   // Every function might be "no-free".
2163   registerAA(*new AANoFreeFunction(F, InfoCache));
2164
2165   // Return attributes are only appropriate if the return type is non void.
2166   Type *ReturnType = F.getReturnType();
2167   if (!ReturnType->isVoidTy()) {
2168     // Argument attribute "returned" --- Create only one per function even
2169     // though it is an argument attribute.
2170     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
2171       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
2172
2173     if (ReturnType->isPointerTy()) {
2174       // Every function with pointer return type might be marked nonnull.
2175       if (!Whitelist || Whitelist->count(AANonNullReturned::ID))
2176         registerAA(*new AANonNullReturned(F, InfoCache));
2177
2178       // Every function with pointer return type might be marked noalias.
2179       if (!Whitelist || Whitelist->count(AANoAliasReturned::ID))
2180         registerAA(*new AANoAliasReturned(F, InfoCache));
2181
2182       // Every function with pointer return type might be marked
2183       // dereferenceable.
2184       if (ReturnType->isPointerTy() &&
2185           (!Whitelist || Whitelist->count(AADereferenceableReturned::ID)))
2186         registerAA(*new AADereferenceableReturned(F, InfoCache));
2187     }
2188   }
2189
2190   for (Argument &Arg : F.args()) {
2191     if (Arg.getType()->isPointerTy()) {
2192       // Every argument with pointer type might be marked nonnull.
2193       if (!Whitelist || Whitelist->count(AANonNullArgument::ID))
2194         registerAA(*new AANonNullArgument(Arg, InfoCache));
2195
2196       // Every argument with pointer type might be marked dereferenceable.
2197       if (!Whitelist || Whitelist->count(AADereferenceableArgument::ID))
2198         registerAA(*new AADereferenceableArgument(Arg, InfoCache));
2199     }
2200   }
2201
2202   // Every function might be "will-return".
2203   registerAA(*new AAWillReturnFunction(F, InfoCache));
2204
2205   // Check for dead BasicBlocks in every function.
2206   registerAA(*new AAIsDeadFunction(F, InfoCache));
2207
2208   // Walk all instructions to find more attribute opportunities and also
2209   // interesting instructions that might be queried by abstract attributes
2210   // during their initialization or update.
2211   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
2212   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
2213
2214   for (Instruction &I : instructions(&F)) {
2215     bool IsInterestingOpcode = false;
2216
2217     // To allow easy access to all instructions in a function with a given
2218     // opcode we store them in the InfoCache. As not all opcodes are interesting
2219     // to concrete attributes we only cache the ones that are as identified in
2220     // the following switch.
2221     // Note: There are no concrete attributes now so this is initially empty.
2222     switch (I.getOpcode()) {
2223     default:
2224       assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
2225              "New call site/base instruction type needs to be known int the "
2226              "attributor.");
2227       break;
2228     case Instruction::Call:
2229     case Instruction::CallBr:
2230     case Instruction::Invoke:
2231     case Instruction::CleanupRet:
2232     case Instruction::CatchSwitch:
2233     case Instruction::Resume:
2234     case Instruction::Ret:
2235       IsInterestingOpcode = true;
2236     }
2237     if (IsInterestingOpcode)
2238       InstOpcodeMap[I.getOpcode()].push_back(&I);
2239     if (I.mayReadOrWriteMemory())
2240       ReadOrWriteInsts.push_back(&I);
2241
2242     CallSite CS(&I);
2243     if (CS && CS.getCalledFunction()) {
2244       for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
2245         if (!CS.getArgument(i)->getType()->isPointerTy())
2246           continue;
2247
2248         // Call site argument attribute "non-null".
2249         if (!Whitelist || Whitelist->count(AANonNullCallSiteArgument::ID))
2250           registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
2251
2252         // Call site argument attribute "dereferenceable".
2253         if (!Whitelist ||
2254             Whitelist->count(AADereferenceableCallSiteArgument::ID))
2255           registerAA(*new AADereferenceableCallSiteArgument(CS, i, InfoCache),
2256                      i);
2257       }
2258     }
2259   }
2260 }
2261
2262 /// Helpers to ease debugging through output streams and print calls.
2263 ///
2264 ///{
2265 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
2266   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2267 }
2268
2269 raw_ostream &llvm::operator<<(raw_ostream &OS,
2270                               AbstractAttribute::ManifestPosition AP) {
2271   switch (AP) {
2272   case AbstractAttribute::MP_ARGUMENT:
2273     return OS << "arg";
2274   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
2275     return OS << "cs_arg";
2276   case AbstractAttribute::MP_FUNCTION:
2277     return OS << "fn";
2278   case AbstractAttribute::MP_RETURNED:
2279     return OS << "fn_ret";
2280   }
2281   llvm_unreachable("Unknown attribute position!");
2282 }
2283
2284 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
2285   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2286 }
2287
2288 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
2289   AA.print(OS);
2290   return OS;
2291 }
2292
2293 void AbstractAttribute::print(raw_ostream &OS) const {
2294   OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
2295      << AnchoredVal.getName() << "]";
2296 }
2297 ///}
2298
2299 /// ----------------------------------------------------------------------------
2300 ///                       Pass (Manager) Boilerplate
2301 /// ----------------------------------------------------------------------------
2302
2303 static bool runAttributorOnModule(Module &M) {
2304   if (DisableAttributor)
2305     return false;
2306
2307   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
2308                     << " functions.\n");
2309
2310   // Create an Attributor and initially empty information cache that is filled
2311   // while we identify default attribute opportunities.
2312   Attributor A;
2313   InformationCache InfoCache;
2314
2315   for (Function &F : M) {
2316     // TODO: Not all attributes require an exact definition. Find a way to
2317     //       enable deduction for some but not all attributes in case the
2318     //       definition might be changed at runtime, see also
2319     //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
2320     // TODO: We could always determine abstract attributes and if sufficient
2321     //       information was found we could duplicate the functions that do not
2322     //       have an exact definition.
2323     if (!F.hasExactDefinition()) {
2324       NumFnWithoutExactDefinition++;
2325       continue;
2326     }
2327
2328     // For now we ignore naked and optnone functions.
2329     if (F.hasFnAttribute(Attribute::Naked) ||
2330         F.hasFnAttribute(Attribute::OptimizeNone))
2331       continue;
2332
2333     NumFnWithExactDefinition++;
2334
2335     // Populate the Attributor with abstract attribute opportunities in the
2336     // function and the information cache with IR information.
2337     A.identifyDefaultAbstractAttributes(F, InfoCache);
2338   }
2339
2340   return A.run() == ChangeStatus::CHANGED;
2341 }
2342
2343 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
2344   if (runAttributorOnModule(M)) {
2345     // FIXME: Think about passes we will preserve and add them here.
2346     return PreservedAnalyses::none();
2347   }
2348   return PreservedAnalyses::all();
2349 }
2350
2351 namespace {
2352
2353 struct AttributorLegacyPass : public ModulePass {
2354   static char ID;
2355
2356   AttributorLegacyPass() : ModulePass(ID) {
2357     initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
2358   }
2359
2360   bool runOnModule(Module &M) override {
2361     if (skipModule(M))
2362       return false;
2363     return runAttributorOnModule(M);
2364   }
2365
2366   void getAnalysisUsage(AnalysisUsage &AU) const override {
2367     // FIXME: Think about passes we will preserve and add them here.
2368     AU.setPreservesCFG();
2369   }
2370 };
2371
2372 } // end anonymous namespace
2373
2374 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
2375
2376 char AttributorLegacyPass::ID = 0;
2377 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
2378                       "Deduce and propagate attributes", false, false)
2379 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
2380                     "Deduce and propagate attributes", false, false)