contrib/llvm/lib/IR/Attributes.cpp

   1 //===- Attributes.cpp - Implement AttributesList --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // \file
  11 // \brief This file implements the Attribute, AttributeImpl, AttrBuilder,
  12 // AttributeListImpl, and AttributeList classes.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "AttributeImpl.h"
  17 #include "LLVMContextImpl.h"
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/Optional.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/ADT/StringExtras.h"
  24 #include "llvm/ADT/StringRef.h"
  25 #include "llvm/ADT/Twine.h"
  26 #include "llvm/IR/Attributes.h"
  27 #include "llvm/IR/Function.h"
  28 #include "llvm/IR/LLVMContext.h"
  29 #include "llvm/IR/Type.h"
  30 #include "llvm/Support/Compiler.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include <algorithm>
  36 #include <cassert>
  37 #include <climits>
  38 #include <cstddef>
  39 #include <cstdint>
  40 #include <limits>
  41 #include <map>
  42 #include <string>
  43 #include <tuple>
  44 #include <utility>
  45
  46 using namespace llvm;
  47
  48 //===----------------------------------------------------------------------===//
  49 // Attribute Construction Methods
  50 //===----------------------------------------------------------------------===//
  51
  52 // allocsize has two integer arguments, but because they're both 32 bits, we can
  53 // pack them into one 64-bit value, at the cost of making said value
  54 // nonsensical.
  55 //
  56 // In order to do this, we need to reserve one value of the second (optional)
  57 // allocsize argument to signify "not present."
  58 static const unsigned AllocSizeNumElemsNotPresent = -1;
  59
  60 static uint64_t packAllocSizeArgs(unsigned ElemSizeArg,
  61                                   const Optional<unsigned> &NumElemsArg) {
  62   assert((!NumElemsArg.hasValue() ||
  63           *NumElemsArg != AllocSizeNumElemsNotPresent) &&
  64          "Attempting to pack a reserved value");
  65
  66   return uint64_t(ElemSizeArg) << 32 |
  67          NumElemsArg.getValueOr(AllocSizeNumElemsNotPresent);
  68 }
  69
  70 static std::pair<unsigned, Optional<unsigned>>
  71 unpackAllocSizeArgs(uint64_t Num) {
  72   unsigned NumElems = Num & std::numeric_limits<unsigned>::max();
  73   unsigned ElemSizeArg = Num >> 32;
  74
  75   Optional<unsigned> NumElemsArg;
  76   if (NumElems != AllocSizeNumElemsNotPresent)
  77     NumElemsArg = NumElems;
  78   return std::make_pair(ElemSizeArg, NumElemsArg);
  79 }
  80
  81 Attribute Attribute::get(LLVMContext &Context, Attribute::AttrKind Kind,
  82                          uint64_t Val) {
  83   LLVMContextImpl *pImpl = Context.pImpl;
  84   FoldingSetNodeID ID;
  85   ID.AddInteger(Kind);
  86   if (Val) ID.AddInteger(Val);
  87
  88   void *InsertPoint;
  89   AttributeImpl *PA = pImpl->AttrsSet.FindNodeOrInsertPos(ID, InsertPoint);
  90
  91   if (!PA) {
  92     // If we didn't find any existing attributes of the same shape then create a
  93     // new one and insert it.
  94     if (!Val)
  95       PA = new EnumAttributeImpl(Kind);
  96     else
  97       PA = new IntAttributeImpl(Kind, Val);
  98     pImpl->AttrsSet.InsertNode(PA, InsertPoint);
  99   }
 100
 101   // Return the Attribute that we found or created.
 102   return Attribute(PA);
 103 }
 104
 105 Attribute Attribute::get(LLVMContext &Context, StringRef Kind, StringRef Val) {
 106   LLVMContextImpl *pImpl = Context.pImpl;
 107   FoldingSetNodeID ID;
 108   ID.AddString(Kind);
 109   if (!Val.empty()) ID.AddString(Val);
 110
 111   void *InsertPoint;
 112   AttributeImpl *PA = pImpl->AttrsSet.FindNodeOrInsertPos(ID, InsertPoint);
 113
 114   if (!PA) {
 115     // If we didn't find any existing attributes of the same shape then create a
 116     // new one and insert it.
 117     PA = new StringAttributeImpl(Kind, Val);
 118     pImpl->AttrsSet.InsertNode(PA, InsertPoint);
 119   }
 120
 121   // Return the Attribute that we found or created.
 122   return Attribute(PA);
 123 }
 124
 125 Attribute Attribute::getWithAlignment(LLVMContext &Context, uint64_t Align) {
 126   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
 127   assert(Align <= 0x40000000 && "Alignment too large.");
 128   return get(Context, Alignment, Align);
 129 }
 130
 131 Attribute Attribute::getWithStackAlignment(LLVMContext &Context,
 132                                            uint64_t Align) {
 133   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
 134   assert(Align <= 0x100 && "Alignment too large.");
 135   return get(Context, StackAlignment, Align);
 136 }
 137
 138 Attribute Attribute::getWithDereferenceableBytes(LLVMContext &Context,
 139                                                 uint64_t Bytes) {
 140   assert(Bytes && "Bytes must be non-zero.");
 141   return get(Context, Dereferenceable, Bytes);
 142 }
 143
 144 Attribute Attribute::getWithDereferenceableOrNullBytes(LLVMContext &Context,
 145                                                        uint64_t Bytes) {
 146   assert(Bytes && "Bytes must be non-zero.");
 147   return get(Context, DereferenceableOrNull, Bytes);
 148 }
 149
 150 Attribute
 151 Attribute::getWithAllocSizeArgs(LLVMContext &Context, unsigned ElemSizeArg,
 152                                 const Optional<unsigned> &NumElemsArg) {
 153   assert(!(ElemSizeArg == 0 && NumElemsArg && *NumElemsArg == 0) &&
 154          "Invalid allocsize arguments -- given allocsize(0, 0)");
 155   return get(Context, AllocSize, packAllocSizeArgs(ElemSizeArg, NumElemsArg));
 156 }
 157
 158 //===----------------------------------------------------------------------===//
 159 // Attribute Accessor Methods
 160 //===----------------------------------------------------------------------===//
 161
 162 bool Attribute::isEnumAttribute() const {
 163   return pImpl && pImpl->isEnumAttribute();
 164 }
 165
 166 bool Attribute::isIntAttribute() const {
 167   return pImpl && pImpl->isIntAttribute();
 168 }
 169
 170 bool Attribute::isStringAttribute() const {
 171   return pImpl && pImpl->isStringAttribute();
 172 }
 173
 174 Attribute::AttrKind Attribute::getKindAsEnum() const {
 175   if (!pImpl) return None;
 176   assert((isEnumAttribute() || isIntAttribute()) &&
 177          "Invalid attribute type to get the kind as an enum!");
 178   return pImpl->getKindAsEnum();
 179 }
 180
 181 uint64_t Attribute::getValueAsInt() const {
 182   if (!pImpl) return 0;
 183   assert(isIntAttribute() &&
 184          "Expected the attribute to be an integer attribute!");
 185   return pImpl->getValueAsInt();
 186 }
 187
 188 StringRef Attribute::getKindAsString() const {
 189   if (!pImpl) return StringRef();
 190   assert(isStringAttribute() &&
 191          "Invalid attribute type to get the kind as a string!");
 192   return pImpl->getKindAsString();
 193 }
 194
 195 StringRef Attribute::getValueAsString() const {
 196   if (!pImpl) return StringRef();
 197   assert(isStringAttribute() &&
 198          "Invalid attribute type to get the value as a string!");
 199   return pImpl->getValueAsString();
 200 }
 201
 202 bool Attribute::hasAttribute(AttrKind Kind) const {
 203   return (pImpl && pImpl->hasAttribute(Kind)) || (!pImpl && Kind == None);
 204 }
 205
 206 bool Attribute::hasAttribute(StringRef Kind) const {
 207   if (!isStringAttribute()) return false;
 208   return pImpl && pImpl->hasAttribute(Kind);
 209 }
 210
 211 unsigned Attribute::getAlignment() const {
 212   assert(hasAttribute(Attribute::Alignment) &&
 213          "Trying to get alignment from non-alignment attribute!");
 214   return pImpl->getValueAsInt();
 215 }
 216
 217 unsigned Attribute::getStackAlignment() const {
 218   assert(hasAttribute(Attribute::StackAlignment) &&
 219          "Trying to get alignment from non-alignment attribute!");
 220   return pImpl->getValueAsInt();
 221 }
 222
 223 uint64_t Attribute::getDereferenceableBytes() const {
 224   assert(hasAttribute(Attribute::Dereferenceable) &&
 225          "Trying to get dereferenceable bytes from "
 226          "non-dereferenceable attribute!");
 227   return pImpl->getValueAsInt();
 228 }
 229
 230 uint64_t Attribute::getDereferenceableOrNullBytes() const {
 231   assert(hasAttribute(Attribute::DereferenceableOrNull) &&
 232          "Trying to get dereferenceable bytes from "
 233          "non-dereferenceable attribute!");
 234   return pImpl->getValueAsInt();
 235 }
 236
 237 std::pair<unsigned, Optional<unsigned>> Attribute::getAllocSizeArgs() const {
 238   assert(hasAttribute(Attribute::AllocSize) &&
 239          "Trying to get allocsize args from non-allocsize attribute");
 240   return unpackAllocSizeArgs(pImpl->getValueAsInt());
 241 }
 242
 243 std::string Attribute::getAsString(bool InAttrGrp) const {
 244   if (!pImpl) return "";
 245
 246   if (hasAttribute(Attribute::SanitizeAddress))
 247     return "sanitize_address";
 248   if (hasAttribute(Attribute::AlwaysInline))
 249     return "alwaysinline";
 250   if (hasAttribute(Attribute::ArgMemOnly))
 251     return "argmemonly";
 252   if (hasAttribute(Attribute::Builtin))
 253     return "builtin";
 254   if (hasAttribute(Attribute::ByVal))
 255     return "byval";
 256   if (hasAttribute(Attribute::Convergent))
 257     return "convergent";
 258   if (hasAttribute(Attribute::SwiftError))
 259     return "swifterror";
 260   if (hasAttribute(Attribute::SwiftSelf))
 261     return "swiftself";
 262   if (hasAttribute(Attribute::InaccessibleMemOnly))
 263     return "inaccessiblememonly";
 264   if (hasAttribute(Attribute::InaccessibleMemOrArgMemOnly))
 265     return "inaccessiblemem_or_argmemonly";
 266   if (hasAttribute(Attribute::InAlloca))
 267     return "inalloca";
 268   if (hasAttribute(Attribute::InlineHint))
 269     return "inlinehint";
 270   if (hasAttribute(Attribute::InReg))
 271     return "inreg";
 272   if (hasAttribute(Attribute::JumpTable))
 273     return "jumptable";
 274   if (hasAttribute(Attribute::MinSize))
 275     return "minsize";
 276   if (hasAttribute(Attribute::Naked))
 277     return "naked";
 278   if (hasAttribute(Attribute::Nest))
 279     return "nest";
 280   if (hasAttribute(Attribute::NoAlias))
 281     return "noalias";
 282   if (hasAttribute(Attribute::NoBuiltin))
 283     return "nobuiltin";
 284   if (hasAttribute(Attribute::NoCapture))
 285     return "nocapture";
 286   if (hasAttribute(Attribute::NoDuplicate))
 287     return "noduplicate";
 288   if (hasAttribute(Attribute::NoImplicitFloat))
 289     return "noimplicitfloat";
 290   if (hasAttribute(Attribute::NoInline))
 291     return "noinline";
 292   if (hasAttribute(Attribute::NonLazyBind))
 293     return "nonlazybind";
 294   if (hasAttribute(Attribute::NonNull))
 295     return "nonnull";
 296   if (hasAttribute(Attribute::NoRedZone))
 297     return "noredzone";
 298   if (hasAttribute(Attribute::NoReturn))
 299     return "noreturn";
 300   if (hasAttribute(Attribute::NoRecurse))
 301     return "norecurse";
 302   if (hasAttribute(Attribute::NoUnwind))
 303     return "nounwind";
 304   if (hasAttribute(Attribute::OptimizeNone))
 305     return "optnone";
 306   if (hasAttribute(Attribute::OptimizeForSize))
 307     return "optsize";
 308   if (hasAttribute(Attribute::ReadNone))
 309     return "readnone";
 310   if (hasAttribute(Attribute::ReadOnly))
 311     return "readonly";
 312   if (hasAttribute(Attribute::WriteOnly))
 313     return "writeonly";
 314   if (hasAttribute(Attribute::Returned))
 315     return "returned";
 316   if (hasAttribute(Attribute::ReturnsTwice))
 317     return "returns_twice";
 318   if (hasAttribute(Attribute::SExt))
 319     return "signext";
 320   if (hasAttribute(Attribute::Speculatable))
 321     return "speculatable";
 322   if (hasAttribute(Attribute::StackProtect))
 323     return "ssp";
 324   if (hasAttribute(Attribute::StackProtectReq))
 325     return "sspreq";
 326   if (hasAttribute(Attribute::StackProtectStrong))
 327     return "sspstrong";
 328   if (hasAttribute(Attribute::SafeStack))
 329     return "safestack";
 330   if (hasAttribute(Attribute::StructRet))
 331     return "sret";
 332   if (hasAttribute(Attribute::SanitizeThread))
 333     return "sanitize_thread";
 334   if (hasAttribute(Attribute::SanitizeMemory))
 335     return "sanitize_memory";
 336   if (hasAttribute(Attribute::UWTable))
 337     return "uwtable";
 338   if (hasAttribute(Attribute::ZExt))
 339     return "zeroext";
 340   if (hasAttribute(Attribute::Cold))
 341     return "cold";
 342
 343   // FIXME: These should be output like this:
 344   //
 345   //   align=4
 346   //   alignstack=8
 347   //
 348   if (hasAttribute(Attribute::Alignment)) {
 349     std::string Result;
 350     Result += "align";
 351     Result += (InAttrGrp) ? "=" : " ";
 352     Result += utostr(getValueAsInt());
 353     return Result;
 354   }
 355
 356   auto AttrWithBytesToString = [&](const char *Name) {
 357     std::string Result;
 358     Result += Name;
 359     if (InAttrGrp) {
 360       Result += "=";
 361       Result += utostr(getValueAsInt());
 362     } else {
 363       Result += "(";
 364       Result += utostr(getValueAsInt());
 365       Result += ")";
 366     }
 367     return Result;
 368   };
 369
 370   if (hasAttribute(Attribute::StackAlignment))
 371     return AttrWithBytesToString("alignstack");
 372
 373   if (hasAttribute(Attribute::Dereferenceable))
 374     return AttrWithBytesToString("dereferenceable");
 375
 376   if (hasAttribute(Attribute::DereferenceableOrNull))
 377     return AttrWithBytesToString("dereferenceable_or_null");
 378
 379   if (hasAttribute(Attribute::AllocSize)) {
 380     unsigned ElemSize;
 381     Optional<unsigned> NumElems;
 382     std::tie(ElemSize, NumElems) = getAllocSizeArgs();
 383
 384     std::string Result = "allocsize(";
 385     Result += utostr(ElemSize);
 386     if (NumElems.hasValue()) {
 387       Result += ',';
 388       Result += utostr(*NumElems);
 389     }
 390     Result += ')';
 391     return Result;
 392   }
 393
 394   // Convert target-dependent attributes to strings of the form:
 395   //
 396   //   "kind"
 397   //   "kind" = "value"
 398   //
 399   if (isStringAttribute()) {
 400     std::string Result;
 401     Result += (Twine('"') + getKindAsString() + Twine('"')).str();
 402
 403     std::string AttrVal = pImpl->getValueAsString();
 404     if (AttrVal.empty()) return Result;
 405
 406     // Since some attribute strings contain special characters that cannot be
 407     // printable, those have to be escaped to make the attribute value printable
 408     // as is.  e.g. "\01__gnu_mcount_nc"
 409     {
 410       raw_string_ostream OS(Result);
 411       OS << "=\"";
 412       PrintEscapedString(AttrVal, OS);
 413       OS << "\"";
 414     }
 415     return Result;
 416   }
 417
 418   llvm_unreachable("Unknown attribute");
 419 }
 420
 421 bool Attribute::operator<(Attribute A) const {
 422   if (!pImpl && !A.pImpl) return false;
 423   if (!pImpl) return true;
 424   if (!A.pImpl) return false;
 425   return *pImpl < *A.pImpl;
 426 }
 427
 428 //===----------------------------------------------------------------------===//
 429 // AttributeImpl Definition
 430 //===----------------------------------------------------------------------===//
 431
 432 // Pin the vtables to this file.
 433 AttributeImpl::~AttributeImpl() = default;
 434
 435 void EnumAttributeImpl::anchor() {}
 436
 437 void IntAttributeImpl::anchor() {}
 438
 439 void StringAttributeImpl::anchor() {}
 440
 441 bool AttributeImpl::hasAttribute(Attribute::AttrKind A) const {
 442   if (isStringAttribute()) return false;
 443   return getKindAsEnum() == A;
 444 }
 445
 446 bool AttributeImpl::hasAttribute(StringRef Kind) const {
 447   if (!isStringAttribute()) return false;
 448   return getKindAsString() == Kind;
 449 }
 450
 451 Attribute::AttrKind AttributeImpl::getKindAsEnum() const {
 452   assert(isEnumAttribute() || isIntAttribute());
 453   return static_cast<const EnumAttributeImpl *>(this)->getEnumKind();
 454 }
 455
 456 uint64_t AttributeImpl::getValueAsInt() const {
 457   assert(isIntAttribute());
 458   return static_cast<const IntAttributeImpl *>(this)->getValue();
 459 }
 460
 461 StringRef AttributeImpl::getKindAsString() const {
 462   assert(isStringAttribute());
 463   return static_cast<const StringAttributeImpl *>(this)->getStringKind();
 464 }
 465
 466 StringRef AttributeImpl::getValueAsString() const {
 467   assert(isStringAttribute());
 468   return static_cast<const StringAttributeImpl *>(this)->getStringValue();
 469 }
 470
 471 bool AttributeImpl::operator<(const AttributeImpl &AI) const {
 472   // This sorts the attributes with Attribute::AttrKinds coming first (sorted
 473   // relative to their enum value) and then strings.
 474   if (isEnumAttribute()) {
 475     if (AI.isEnumAttribute()) return getKindAsEnum() < AI.getKindAsEnum();
 476     if (AI.isIntAttribute()) return true;
 477     if (AI.isStringAttribute()) return true;
 478   }
 479
 480   if (isIntAttribute()) {
 481     if (AI.isEnumAttribute()) return false;
 482     if (AI.isIntAttribute()) {
 483       if (getKindAsEnum() == AI.getKindAsEnum())
 484         return getValueAsInt() < AI.getValueAsInt();
 485       return getKindAsEnum() < AI.getKindAsEnum();
 486     }
 487     if (AI.isStringAttribute()) return true;
 488   }
 489
 490   if (AI.isEnumAttribute()) return false;
 491   if (AI.isIntAttribute()) return false;
 492   if (getKindAsString() == AI.getKindAsString())
 493     return getValueAsString() < AI.getValueAsString();
 494   return getKindAsString() < AI.getKindAsString();
 495 }
 496
 497 //===----------------------------------------------------------------------===//
 498 // AttributeSet Definition
 499 //===----------------------------------------------------------------------===//
 500
 501 AttributeSet AttributeSet::get(LLVMContext &C, const AttrBuilder &B) {
 502   return AttributeSet(AttributeSetNode::get(C, B));
 503 }
 504
 505 AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef<Attribute> Attrs) {
 506   return AttributeSet(AttributeSetNode::get(C, Attrs));
 507 }
 508
 509 AttributeSet AttributeSet::addAttribute(LLVMContext &C,
 510                                         Attribute::AttrKind Kind) const {
 511   if (hasAttribute(Kind)) return *this;
 512   AttrBuilder B;
 513   B.addAttribute(Kind);
 514   return addAttributes(C, AttributeSet::get(C, B));
 515 }
 516
 517 AttributeSet AttributeSet::addAttribute(LLVMContext &C, StringRef Kind,
 518                                         StringRef Value) const {
 519   AttrBuilder B;
 520   B.addAttribute(Kind, Value);
 521   return addAttributes(C, AttributeSet::get(C, B));
 522 }
 523
 524 AttributeSet AttributeSet::addAttributes(LLVMContext &C,
 525                                          const AttributeSet AS) const {
 526   if (!hasAttributes())
 527     return AS;
 528
 529   if (!AS.hasAttributes())
 530     return *this;
 531
 532   AttrBuilder B(AS);
 533   for (Attribute I : *this)
 534     B.addAttribute(I);
 535
 536  return get(C, B);
 537 }
 538
 539 AttributeSet AttributeSet::removeAttribute(LLVMContext &C,
 540                                              Attribute::AttrKind Kind) const {
 541   if (!hasAttribute(Kind)) return *this;
 542   AttrBuilder B;
 543   B.addAttribute(Kind);
 544   return removeAttributes(C, B);
 545 }
 546
 547 AttributeSet AttributeSet::removeAttribute(LLVMContext &C,
 548                                              StringRef Kind) const {
 549   if (!hasAttribute(Kind)) return *this;
 550   AttrBuilder B;
 551   B.addAttribute(Kind);
 552   return removeAttributes(C, B);
 553 }
 554
 555 AttributeSet AttributeSet::removeAttributes(LLVMContext &C,
 556                                               const AttrBuilder &Attrs) const {
 557
 558   // FIXME it is not obvious how this should work for alignment.
 559   // For now, say we can't pass in alignment, which no current use does.
 560   assert(!Attrs.hasAlignmentAttr() && "Attempt to change alignment!");
 561
 562   AttrBuilder B(*this);
 563   B.remove(Attrs);
 564   return get(C, B);
 565 }
 566
 567 unsigned AttributeSet::getNumAttributes() const {
 568   return SetNode ? SetNode->getNumAttributes() : 0;
 569 }
 570
 571 bool AttributeSet::hasAttribute(Attribute::AttrKind Kind) const {
 572   return SetNode ? SetNode->hasAttribute(Kind) : false;
 573 }
 574
 575 bool AttributeSet::hasAttribute(StringRef Kind) const {
 576   return SetNode ? SetNode->hasAttribute(Kind) : false;
 577 }
 578
 579 Attribute AttributeSet::getAttribute(Attribute::AttrKind Kind) const {
 580   return SetNode ? SetNode->getAttribute(Kind) : Attribute();
 581 }
 582
 583 Attribute AttributeSet::getAttribute(StringRef Kind) const {
 584   return SetNode ? SetNode->getAttribute(Kind) : Attribute();
 585 }
 586
 587 unsigned AttributeSet::getAlignment() const {
 588   return SetNode ? SetNode->getAlignment() : 0;
 589 }
 590
 591 unsigned AttributeSet::getStackAlignment() const {
 592   return SetNode ? SetNode->getStackAlignment() : 0;
 593 }
 594
 595 uint64_t AttributeSet::getDereferenceableBytes() const {
 596   return SetNode ? SetNode->getDereferenceableBytes() : 0;
 597 }
 598
 599 uint64_t AttributeSet::getDereferenceableOrNullBytes() const {
 600   return SetNode ? SetNode->getDereferenceableOrNullBytes() : 0;
 601 }
 602
 603 std::pair<unsigned, Optional<unsigned>> AttributeSet::getAllocSizeArgs() const {
 604   return SetNode ? SetNode->getAllocSizeArgs()
 605                  : std::pair<unsigned, Optional<unsigned>>(0, 0);
 606 }
 607
 608 std::string AttributeSet::getAsString(bool InAttrGrp) const {
 609   return SetNode ? SetNode->getAsString(InAttrGrp) : "";
 610 }
 611
 612 AttributeSet::iterator AttributeSet::begin() const {
 613   return SetNode ? SetNode->begin() : nullptr;
 614 }
 615
 616 AttributeSet::iterator AttributeSet::end() const {
 617   return SetNode ? SetNode->end() : nullptr;
 618 }
 619
 620 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 621 LLVM_DUMP_METHOD void AttributeSet::dump() const {
 622   dbgs() << "AS =\n";
 623     dbgs() << "  { ";
 624     dbgs() << getAsString(true) << " }\n";
 625 }
 626 #endif
 627
 628 //===----------------------------------------------------------------------===//
 629 // AttributeSetNode Definition
 630 //===----------------------------------------------------------------------===//
 631
 632 AttributeSetNode::AttributeSetNode(ArrayRef<Attribute> Attrs)
 633     : AvailableAttrs(0), NumAttrs(Attrs.size()) {
 634   // There's memory after the node where we can store the entries in.
 635   std::copy(Attrs.begin(), Attrs.end(), getTrailingObjects<Attribute>());
 636
 637   for (Attribute I : *this) {
 638     if (!I.isStringAttribute()) {
 639       AvailableAttrs |= ((uint64_t)1) << I.getKindAsEnum();
 640     }
 641   }
 642 }
 643
 644 AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
 645                                         ArrayRef<Attribute> Attrs) {
 646   if (Attrs.empty())
 647     return nullptr;
 648
 649   // Otherwise, build a key to look up the existing attributes.
 650   LLVMContextImpl *pImpl = C.pImpl;
 651   FoldingSetNodeID ID;
 652
 653   SmallVector<Attribute, 8> SortedAttrs(Attrs.begin(), Attrs.end());
 654   std::sort(SortedAttrs.begin(), SortedAttrs.end());
 655
 656   for (Attribute Attr : SortedAttrs)
 657     Attr.Profile(ID);
 658
 659   void *InsertPoint;
 660   AttributeSetNode *PA =
 661     pImpl->AttrsSetNodes.FindNodeOrInsertPos(ID, InsertPoint);
 662
 663   // If we didn't find any existing attributes of the same shape then create a
 664   // new one and insert it.
 665   if (!PA) {
 666     // Coallocate entries after the AttributeSetNode itself.
 667     void *Mem = ::operator new(totalSizeToAlloc<Attribute>(SortedAttrs.size()));
 668     PA = new (Mem) AttributeSetNode(SortedAttrs);
 669     pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint);
 670   }
 671
 672   // Return the AttributeSetNode that we found or created.
 673   return PA;
 674 }
 675
 676 AttributeSetNode *AttributeSetNode::get(LLVMContext &C, const AttrBuilder &B) {
 677   // Add target-independent attributes.
 678   SmallVector<Attribute, 8> Attrs;
 679   for (Attribute::AttrKind Kind = Attribute::None;
 680        Kind != Attribute::EndAttrKinds; Kind = Attribute::AttrKind(Kind + 1)) {
 681     if (!B.contains(Kind))
 682       continue;
 683
 684     Attribute Attr;
 685     switch (Kind) {
 686     case Attribute::Alignment:
 687       Attr = Attribute::getWithAlignment(C, B.getAlignment());
 688       break;
 689     case Attribute::StackAlignment:
 690       Attr = Attribute::getWithStackAlignment(C, B.getStackAlignment());
 691       break;
 692     case Attribute::Dereferenceable:
 693       Attr = Attribute::getWithDereferenceableBytes(
 694           C, B.getDereferenceableBytes());
 695       break;
 696     case Attribute::DereferenceableOrNull:
 697       Attr = Attribute::getWithDereferenceableOrNullBytes(
 698           C, B.getDereferenceableOrNullBytes());
 699       break;
 700     case Attribute::AllocSize: {
 701       auto A = B.getAllocSizeArgs();
 702       Attr = Attribute::getWithAllocSizeArgs(C, A.first, A.second);
 703       break;
 704     }
 705     default:
 706       Attr = Attribute::get(C, Kind);
 707     }
 708     Attrs.push_back(Attr);
 709   }
 710
 711   // Add target-dependent (string) attributes.
 712   for (const auto &TDA : B.td_attrs())
 713     Attrs.emplace_back(Attribute::get(C, TDA.first, TDA.second));
 714
 715   return get(C, Attrs);
 716 }
 717
 718 bool AttributeSetNode::hasAttribute(StringRef Kind) const {
 719   for (Attribute I : *this)
 720     if (I.hasAttribute(Kind))
 721       return true;
 722   return false;
 723 }
 724
 725 Attribute AttributeSetNode::getAttribute(Attribute::AttrKind Kind) const {
 726   if (hasAttribute(Kind)) {
 727     for (Attribute I : *this)
 728       if (I.hasAttribute(Kind))
 729         return I;
 730   }
 731   return Attribute();
 732 }
 733
 734 Attribute AttributeSetNode::getAttribute(StringRef Kind) const {
 735   for (Attribute I : *this)
 736     if (I.hasAttribute(Kind))
 737       return I;
 738   return Attribute();
 739 }
 740
 741 unsigned AttributeSetNode::getAlignment() const {
 742   for (Attribute I : *this)
 743     if (I.hasAttribute(Attribute::Alignment))
 744       return I.getAlignment();
 745   return 0;
 746 }
 747
 748 unsigned AttributeSetNode::getStackAlignment() const {
 749   for (Attribute I : *this)
 750     if (I.hasAttribute(Attribute::StackAlignment))
 751       return I.getStackAlignment();
 752   return 0;
 753 }
 754
 755 uint64_t AttributeSetNode::getDereferenceableBytes() const {
 756   for (Attribute I : *this)
 757     if (I.hasAttribute(Attribute::Dereferenceable))
 758       return I.getDereferenceableBytes();
 759   return 0;
 760 }
 761
 762 uint64_t AttributeSetNode::getDereferenceableOrNullBytes() const {
 763   for (Attribute I : *this)
 764     if (I.hasAttribute(Attribute::DereferenceableOrNull))
 765       return I.getDereferenceableOrNullBytes();
 766   return 0;
 767 }
 768
 769 std::pair<unsigned, Optional<unsigned>>
 770 AttributeSetNode::getAllocSizeArgs() const {
 771   for (Attribute I : *this)
 772     if (I.hasAttribute(Attribute::AllocSize))
 773       return I.getAllocSizeArgs();
 774   return std::make_pair(0, 0);
 775 }
 776
 777 std::string AttributeSetNode::getAsString(bool InAttrGrp) const {
 778   std::string Str;
 779   for (iterator I = begin(), E = end(); I != E; ++I) {
 780     if (I != begin())
 781       Str += ' ';
 782     Str += I->getAsString(InAttrGrp);
 783   }
 784   return Str;
 785 }
 786
 787 //===----------------------------------------------------------------------===//
 788 // AttributeListImpl Definition
 789 //===----------------------------------------------------------------------===//
 790
 791 /// Map from AttributeList index to the internal array index. Adding one works:
 792 ///   FunctionIndex: ~0U -> 0
 793 ///   ReturnIndex:    0  -> 1
 794 ///   FirstArgIndex: 1.. -> 2..
 795 static constexpr unsigned attrIdxToArrayIdx(unsigned Index) {
 796   // MSVC warns about '~0U + 1' wrapping around when this is called on
 797   // FunctionIndex, so cast to int first.
 798   return static_cast<int>(Index) + 1;
 799 }
 800
 801 AttributeListImpl::AttributeListImpl(LLVMContext &C,
 802                                      ArrayRef<AttributeSet> Sets)
 803     : AvailableFunctionAttrs(0), Context(C), NumAttrSets(Sets.size()) {
 804   assert(!Sets.empty() && "pointless AttributeListImpl");
 805
 806   // There's memory after the node where we can store the entries in.
 807   std::copy(Sets.begin(), Sets.end(), getTrailingObjects<AttributeSet>());
 808
 809   // Initialize AvailableFunctionAttrs summary bitset.
 810   static_assert(Attribute::EndAttrKinds <=
 811                     sizeof(AvailableFunctionAttrs) * CHAR_BIT,
 812                 "Too many attributes");
 813   static_assert(attrIdxToArrayIdx(AttributeList::FunctionIndex) == 0U,
 814                 "function should be stored in slot 0");
 815   for (Attribute I : Sets[0]) {
 816     if (!I.isStringAttribute())
 817       AvailableFunctionAttrs |= 1ULL << I.getKindAsEnum();
 818   }
 819 }
 820
 821 void AttributeListImpl::Profile(FoldingSetNodeID &ID) const {
 822   Profile(ID, makeArrayRef(begin(), end()));
 823 }
 824
 825 void AttributeListImpl::Profile(FoldingSetNodeID &ID,
 826                                 ArrayRef<AttributeSet> Sets) {
 827   for (const auto &Set : Sets)
 828     ID.AddPointer(Set.SetNode);
 829 }
 830
 831 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 832 LLVM_DUMP_METHOD void AttributeListImpl::dump() const {
 833   AttributeList(const_cast<AttributeListImpl *>(this)).dump();
 834 }
 835 #endif
 836
 837 //===----------------------------------------------------------------------===//
 838 // AttributeList Construction and Mutation Methods
 839 //===----------------------------------------------------------------------===//
 840
 841 AttributeList AttributeList::getImpl(LLVMContext &C,
 842                                      ArrayRef<AttributeSet> AttrSets) {
 843   assert(!AttrSets.empty() && "pointless AttributeListImpl");
 844
 845   LLVMContextImpl *pImpl = C.pImpl;
 846   FoldingSetNodeID ID;
 847   AttributeListImpl::Profile(ID, AttrSets);
 848
 849   void *InsertPoint;
 850   AttributeListImpl *PA =
 851       pImpl->AttrsLists.FindNodeOrInsertPos(ID, InsertPoint);
 852
 853   // If we didn't find any existing attributes of the same shape then
 854   // create a new one and insert it.
 855   if (!PA) {
 856     // Coallocate entries after the AttributeListImpl itself.
 857     void *Mem = ::operator new(
 858         AttributeListImpl::totalSizeToAlloc<AttributeSet>(AttrSets.size()));
 859     PA = new (Mem) AttributeListImpl(C, AttrSets);
 860     pImpl->AttrsLists.InsertNode(PA, InsertPoint);
 861   }
 862
 863   // Return the AttributesList that we found or created.
 864   return AttributeList(PA);
 865 }
 866
 867 AttributeList
 868 AttributeList::get(LLVMContext &C,
 869                    ArrayRef<std::pair<unsigned, Attribute>> Attrs) {
 870   // If there are no attributes then return a null AttributesList pointer.
 871   if (Attrs.empty())
 872     return AttributeList();
 873
 874   assert(std::is_sorted(Attrs.begin(), Attrs.end(),
 875                         [](const std::pair<unsigned, Attribute> &LHS,
 876                            const std::pair<unsigned, Attribute> &RHS) {
 877                           return LHS.first < RHS.first;
 878                         }) && "Misordered Attributes list!");
 879   assert(none_of(Attrs,
 880                  [](const std::pair<unsigned, Attribute> &Pair) {
 881                    return Pair.second.hasAttribute(Attribute::None);
 882                  }) &&
 883          "Pointless attribute!");
 884
 885   // Create a vector if (unsigned, AttributeSetNode*) pairs from the attributes
 886   // list.
 887   SmallVector<std::pair<unsigned, AttributeSet>, 8> AttrPairVec;
 888   for (ArrayRef<std::pair<unsigned, Attribute>>::iterator I = Attrs.begin(),
 889          E = Attrs.end(); I != E; ) {
 890     unsigned Index = I->first;
 891     SmallVector<Attribute, 4> AttrVec;
 892     while (I != E && I->first == Index) {
 893       AttrVec.push_back(I->second);
 894       ++I;
 895     }
 896
 897     AttrPairVec.emplace_back(Index, AttributeSet::get(C, AttrVec));
 898   }
 899
 900   return get(C, AttrPairVec);
 901 }
 902
 903 AttributeList
 904 AttributeList::get(LLVMContext &C,
 905                    ArrayRef<std::pair<unsigned, AttributeSet>> Attrs) {
 906   // If there are no attributes then return a null AttributesList pointer.
 907   if (Attrs.empty())
 908     return AttributeList();
 909
 910   assert(std::is_sorted(Attrs.begin(), Attrs.end(),
 911                         [](const std::pair<unsigned, AttributeSet> &LHS,
 912                            const std::pair<unsigned, AttributeSet> &RHS) {
 913                           return LHS.first < RHS.first;
 914                         }) &&
 915          "Misordered Attributes list!");
 916   assert(none_of(Attrs,
 917                  [](const std::pair<unsigned, AttributeSet> &Pair) {
 918                    return !Pair.second.hasAttributes();
 919                  }) &&
 920          "Pointless attribute!");
 921
 922   unsigned MaxIndex = Attrs.back().first;
 923
 924   SmallVector<AttributeSet, 4> AttrVec(attrIdxToArrayIdx(MaxIndex) + 1);
 925   for (auto Pair : Attrs)
 926     AttrVec[attrIdxToArrayIdx(Pair.first)] = Pair.second;
 927
 928   return getImpl(C, AttrVec);
 929 }
 930
 931 AttributeList AttributeList::get(LLVMContext &C, AttributeSet FnAttrs,
 932                                  AttributeSet RetAttrs,
 933                                  ArrayRef<AttributeSet> ArgAttrs) {
 934   // Scan from the end to find the last argument with attributes.  Most
 935   // arguments don't have attributes, so it's nice if we can have fewer unique
 936   // AttributeListImpls by dropping empty attribute sets at the end of the list.
 937   unsigned NumSets = 0;
 938   for (size_t I = ArgAttrs.size(); I != 0; --I) {
 939     if (ArgAttrs[I - 1].hasAttributes()) {
 940       NumSets = I + 2;
 941       break;
 942     }
 943   }
 944   if (NumSets == 0) {
 945     // Check function and return attributes if we didn't have argument
 946     // attributes.
 947     if (RetAttrs.hasAttributes())
 948       NumSets = 2;
 949     else if (FnAttrs.hasAttributes())
 950       NumSets = 1;
 951   }
 952
 953   // If all attribute sets were empty, we can use the empty attribute list.
 954   if (NumSets == 0)
 955     return AttributeList();
 956
 957   SmallVector<AttributeSet, 8> AttrSets;
 958   AttrSets.reserve(NumSets);
 959   // If we have any attributes, we always have function attributes.
 960   AttrSets.push_back(FnAttrs);
 961   if (NumSets > 1)
 962     AttrSets.push_back(RetAttrs);
 963   if (NumSets > 2) {
 964     // Drop the empty argument attribute sets at the end.
 965     ArgAttrs = ArgAttrs.take_front(NumSets - 2);
 966     AttrSets.insert(AttrSets.end(), ArgAttrs.begin(), ArgAttrs.end());
 967   }
 968
 969   return getImpl(C, AttrSets);
 970 }
 971
 972 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
 973                                  const AttrBuilder &B) {
 974   if (!B.hasAttributes())
 975     return AttributeList();
 976   Index = attrIdxToArrayIdx(Index);
 977   SmallVector<AttributeSet, 8> AttrSets(Index + 1);
 978   AttrSets[Index] = AttributeSet::get(C, B);
 979   return getImpl(C, AttrSets);
 980 }
 981
 982 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
 983                                  ArrayRef<Attribute::AttrKind> Kinds) {
 984   SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
 985   for (Attribute::AttrKind K : Kinds)
 986     Attrs.emplace_back(Index, Attribute::get(C, K));
 987   return get(C, Attrs);
 988 }
 989
 990 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
 991                                  ArrayRef<StringRef> Kinds) {
 992   SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
 993   for (StringRef K : Kinds)
 994     Attrs.emplace_back(Index, Attribute::get(C, K));
 995   return get(C, Attrs);
 996 }
 997
 998 AttributeList AttributeList::get(LLVMContext &C,
 999                                  ArrayRef<AttributeList> Attrs) {
1000   if (Attrs.empty())
1001     return AttributeList();
1002   if (Attrs.size() == 1)
1003     return Attrs[0];
1004
1005   unsigned MaxSize = 0;
1006   for (AttributeList List : Attrs)
1007     MaxSize = std::max(MaxSize, List.getNumAttrSets());
1008
1009   SmallVector<AttributeSet, 8> NewAttrSets(MaxSize);
1010   for (unsigned I = 0; I < MaxSize; ++I) {
1011     AttrBuilder CurBuilder;
1012     for (AttributeList List : Attrs)
1013       CurBuilder.merge(List.getAttributes(I - 1));
1014     NewAttrSets[I] = AttributeSet::get(C, CurBuilder);
1015   }
1016
1017   return getImpl(C, NewAttrSets);
1018 }
1019
1020 AttributeList AttributeList::addAttribute(LLVMContext &C, unsigned Index,
1021                                           Attribute::AttrKind Kind) const {
1022   if (hasAttribute(Index, Kind)) return *this;
1023   AttrBuilder B;
1024   B.addAttribute(Kind);
1025   return addAttributes(C, Index, B);
1026 }
1027
1028 AttributeList AttributeList::addAttribute(LLVMContext &C, unsigned Index,
1029                                           StringRef Kind,
1030                                           StringRef Value) const {
1031   AttrBuilder B;
1032   B.addAttribute(Kind, Value);
1033   return addAttributes(C, Index, B);
1034 }
1035
1036 AttributeList AttributeList::addAttribute(LLVMContext &C,
1037                                           ArrayRef<unsigned> Indices,
1038                                           Attribute A) const {
1039   assert(std::is_sorted(Indices.begin(), Indices.end()));
1040
1041   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
1042   unsigned MaxIndex = attrIdxToArrayIdx(Indices.back());
1043   if (MaxIndex >= AttrSets.size())
1044     AttrSets.resize(MaxIndex + 1);
1045
1046   for (unsigned Index : Indices) {
1047     Index = attrIdxToArrayIdx(Index);
1048     AttrBuilder B(AttrSets[Index]);
1049     B.addAttribute(A);
1050     AttrSets[Index] = AttributeSet::get(C, B);
1051   }
1052
1053   return getImpl(C, AttrSets);
1054 }
1055
1056 AttributeList AttributeList::addAttributes(LLVMContext &C, unsigned Index,
1057                                            const AttrBuilder &B) const {
1058   if (!B.hasAttributes())
1059     return *this;
1060
1061   if (!pImpl)
1062     return AttributeList::get(C, {{Index, AttributeSet::get(C, B)}});
1063
1064 #ifndef NDEBUG
1065   // FIXME it is not obvious how this should work for alignment. For now, say
1066   // we can't change a known alignment.
1067   unsigned OldAlign = getAttributes(Index).getAlignment();
1068   unsigned NewAlign = B.getAlignment();
1069   assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
1070          "Attempt to change alignment!");
1071 #endif
1072
1073   Index = attrIdxToArrayIdx(Index);
1074   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
1075   if (Index >= AttrSets.size())
1076     AttrSets.resize(Index + 1);
1077
1078   AttrBuilder Merged(AttrSets[Index]);
1079   Merged.merge(B);
1080   AttrSets[Index] = AttributeSet::get(C, Merged);
1081
1082   return getImpl(C, AttrSets);
1083 }
1084
1085 AttributeList AttributeList::removeAttribute(LLVMContext &C, unsigned Index,
1086                                              Attribute::AttrKind Kind) const {
1087   if (!hasAttribute(Index, Kind)) return *this;
1088   AttrBuilder B;
1089   B.addAttribute(Kind);
1090   return removeAttributes(C, Index, B);
1091 }
1092
1093 AttributeList AttributeList::removeAttribute(LLVMContext &C, unsigned Index,
1094                                              StringRef Kind) const {
1095   if (!hasAttribute(Index, Kind)) return *this;
1096   AttrBuilder B;
1097   B.addAttribute(Kind);
1098   return removeAttributes(C, Index, B);
1099 }
1100
1101 AttributeList
1102 AttributeList::removeAttributes(LLVMContext &C, unsigned Index,
1103                                 const AttrBuilder &AttrsToRemove) const {
1104   if (!pImpl)
1105     return AttributeList();
1106
1107   // FIXME it is not obvious how this should work for alignment.
1108   // For now, say we can't pass in alignment, which no current use does.
1109   assert(!AttrsToRemove.hasAlignmentAttr() && "Attempt to change alignment!");
1110
1111   Index = attrIdxToArrayIdx(Index);
1112   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
1113   if (Index >= AttrSets.size())
1114     AttrSets.resize(Index + 1);
1115
1116   AttrBuilder B(AttrSets[Index]);
1117   B.remove(AttrsToRemove);
1118   AttrSets[Index] = AttributeSet::get(C, B);
1119
1120   return getImpl(C, AttrSets);
1121 }
1122
1123 AttributeList AttributeList::removeAttributes(LLVMContext &C,
1124                                               unsigned WithoutIndex) const {
1125   if (!pImpl)
1126     return AttributeList();
1127   WithoutIndex = attrIdxToArrayIdx(WithoutIndex);
1128   if (WithoutIndex >= getNumAttrSets())
1129     return *this;
1130   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
1131   AttrSets[WithoutIndex] = AttributeSet();
1132   return getImpl(C, AttrSets);
1133 }
1134
1135 AttributeList AttributeList::addDereferenceableAttr(LLVMContext &C,
1136                                                     unsigned Index,
1137                                                     uint64_t Bytes) const {
1138   AttrBuilder B;
1139   B.addDereferenceableAttr(Bytes);
1140   return addAttributes(C, Index, B);
1141 }
1142
1143 AttributeList
1144 AttributeList::addDereferenceableOrNullAttr(LLVMContext &C, unsigned Index,
1145                                             uint64_t Bytes) const {
1146   AttrBuilder B;
1147   B.addDereferenceableOrNullAttr(Bytes);
1148   return addAttributes(C, Index, B);
1149 }
1150
1151 AttributeList
1152 AttributeList::addAllocSizeAttr(LLVMContext &C, unsigned Index,
1153                                 unsigned ElemSizeArg,
1154                                 const Optional<unsigned> &NumElemsArg) {
1155   AttrBuilder B;
1156   B.addAllocSizeAttr(ElemSizeArg, NumElemsArg);
1157   return addAttributes(C, Index, B);
1158 }
1159
1160 //===----------------------------------------------------------------------===//
1161 // AttributeList Accessor Methods
1162 //===----------------------------------------------------------------------===//
1163
1164 LLVMContext &AttributeList::getContext() const { return pImpl->getContext(); }
1165
1166 AttributeSet AttributeList::getParamAttributes(unsigned ArgNo) const {
1167   return getAttributes(ArgNo + FirstArgIndex);
1168 }
1169
1170 AttributeSet AttributeList::getRetAttributes() const {
1171   return getAttributes(ReturnIndex);
1172 }
1173
1174 AttributeSet AttributeList::getFnAttributes() const {
1175   return getAttributes(FunctionIndex);
1176 }
1177
1178 bool AttributeList::hasAttribute(unsigned Index,
1179                                  Attribute::AttrKind Kind) const {
1180   return getAttributes(Index).hasAttribute(Kind);
1181 }
1182
1183 bool AttributeList::hasAttribute(unsigned Index, StringRef Kind) const {
1184   return getAttributes(Index).hasAttribute(Kind);
1185 }
1186
1187 bool AttributeList::hasAttributes(unsigned Index) const {
1188   return getAttributes(Index).hasAttributes();
1189 }
1190
1191 bool AttributeList::hasFnAttribute(Attribute::AttrKind Kind) const {
1192   return pImpl && pImpl->hasFnAttribute(Kind);
1193 }
1194
1195 bool AttributeList::hasFnAttribute(StringRef Kind) const {
1196   return hasAttribute(AttributeList::FunctionIndex, Kind);
1197 }
1198
1199 bool AttributeList::hasParamAttribute(unsigned ArgNo,
1200                                       Attribute::AttrKind Kind) const {
1201   return hasAttribute(ArgNo + FirstArgIndex, Kind);
1202 }
1203
1204 bool AttributeList::hasAttrSomewhere(Attribute::AttrKind Attr,
1205                                      unsigned *Index) const {
1206   if (!pImpl) return false;
1207
1208   for (unsigned I = index_begin(), E = index_end(); I != E; ++I) {
1209     if (hasAttribute(I, Attr)) {
1210       if (Index)
1211         *Index = I;
1212       return true;
1213     }
1214   }
1215
1216   return false;
1217 }
1218
1219 Attribute AttributeList::getAttribute(unsigned Index,
1220                                       Attribute::AttrKind Kind) const {
1221   return getAttributes(Index).getAttribute(Kind);
1222 }
1223
1224 Attribute AttributeList::getAttribute(unsigned Index, StringRef Kind) const {
1225   return getAttributes(Index).getAttribute(Kind);
1226 }
1227
1228 unsigned AttributeList::getRetAlignment() const {
1229   return getAttributes(ReturnIndex).getAlignment();
1230 }
1231
1232 unsigned AttributeList::getParamAlignment(unsigned ArgNo) const {
1233   return getAttributes(ArgNo + FirstArgIndex).getAlignment();
1234 }
1235
1236 unsigned AttributeList::getStackAlignment(unsigned Index) const {
1237   return getAttributes(Index).getStackAlignment();
1238 }
1239
1240 uint64_t AttributeList::getDereferenceableBytes(unsigned Index) const {
1241   return getAttributes(Index).getDereferenceableBytes();
1242 }
1243
1244 uint64_t AttributeList::getDereferenceableOrNullBytes(unsigned Index) const {
1245   return getAttributes(Index).getDereferenceableOrNullBytes();
1246 }
1247
1248 std::pair<unsigned, Optional<unsigned>>
1249 AttributeList::getAllocSizeArgs(unsigned Index) const {
1250   return getAttributes(Index).getAllocSizeArgs();
1251 }
1252
1253 std::string AttributeList::getAsString(unsigned Index, bool InAttrGrp) const {
1254   return getAttributes(Index).getAsString(InAttrGrp);
1255 }
1256
1257 AttributeSet AttributeList::getAttributes(unsigned Index) const {
1258   Index = attrIdxToArrayIdx(Index);
1259   if (!pImpl || Index >= getNumAttrSets())
1260     return AttributeSet();
1261   return pImpl->begin()[Index];
1262 }
1263
1264 AttributeList::iterator AttributeList::begin() const {
1265   return pImpl ? pImpl->begin() : nullptr;
1266 }
1267
1268 AttributeList::iterator AttributeList::end() const {
1269   return pImpl ? pImpl->end() : nullptr;
1270 }
1271
1272 //===----------------------------------------------------------------------===//
1273 // AttributeList Introspection Methods
1274 //===----------------------------------------------------------------------===//
1275
1276 unsigned AttributeList::getNumAttrSets() const {
1277   return pImpl ? pImpl->NumAttrSets : 0;
1278 }
1279
1280 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1281 LLVM_DUMP_METHOD void AttributeList::dump() const {
1282   dbgs() << "PAL[\n";
1283
1284   for (unsigned i = index_begin(), e = index_end(); i != e; ++i) {
1285     if (getAttributes(i).hasAttributes())
1286       dbgs() << "  { " << i << " => " << getAsString(i) << " }\n";
1287   }
1288
1289   dbgs() << "]\n";
1290 }
1291 #endif
1292
1293 //===----------------------------------------------------------------------===//
1294 // AttrBuilder Method Implementations
1295 //===----------------------------------------------------------------------===//
1296
1297 // FIXME: Remove this ctor, use AttributeSet.
1298 AttrBuilder::AttrBuilder(AttributeList AL, unsigned Index) {
1299   AttributeSet AS = AL.getAttributes(Index);
1300   for (const Attribute &A : AS)
1301     addAttribute(A);
1302 }
1303
1304 AttrBuilder::AttrBuilder(AttributeSet AS) {
1305   for (const Attribute &A : AS)
1306     addAttribute(A);
1307 }
1308
1309 void AttrBuilder::clear() {
1310   Attrs.reset();
1311   TargetDepAttrs.clear();
1312   Alignment = StackAlignment = DerefBytes = DerefOrNullBytes = 0;
1313   AllocSizeArgs = 0;
1314 }
1315
1316 AttrBuilder &AttrBuilder::addAttribute(Attribute::AttrKind Val) {
1317   assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
1318   assert(Val != Attribute::Alignment && Val != Attribute::StackAlignment &&
1319          Val != Attribute::Dereferenceable && Val != Attribute::AllocSize &&
1320          "Adding integer attribute without adding a value!");
1321   Attrs[Val] = true;
1322   return *this;
1323 }
1324
1325 AttrBuilder &AttrBuilder::addAttribute(Attribute Attr) {
1326   if (Attr.isStringAttribute()) {
1327     addAttribute(Attr.getKindAsString(), Attr.getValueAsString());
1328     return *this;
1329   }
1330
1331   Attribute::AttrKind Kind = Attr.getKindAsEnum();
1332   Attrs[Kind] = true;
1333
1334   if (Kind == Attribute::Alignment)
1335     Alignment = Attr.getAlignment();
1336   else if (Kind == Attribute::StackAlignment)
1337     StackAlignment = Attr.getStackAlignment();
1338   else if (Kind == Attribute::Dereferenceable)
1339     DerefBytes = Attr.getDereferenceableBytes();
1340   else if (Kind == Attribute::DereferenceableOrNull)
1341     DerefOrNullBytes = Attr.getDereferenceableOrNullBytes();
1342   else if (Kind == Attribute::AllocSize)
1343     AllocSizeArgs = Attr.getValueAsInt();
1344   return *this;
1345 }
1346
1347 AttrBuilder &AttrBuilder::addAttribute(StringRef A, StringRef V) {
1348   TargetDepAttrs[A] = V;
1349   return *this;
1350 }
1351
1352 AttrBuilder &AttrBuilder::removeAttribute(Attribute::AttrKind Val) {
1353   assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
1354   Attrs[Val] = false;
1355
1356   if (Val == Attribute::Alignment)
1357     Alignment = 0;
1358   else if (Val == Attribute::StackAlignment)
1359     StackAlignment = 0;
1360   else if (Val == Attribute::Dereferenceable)
1361     DerefBytes = 0;
1362   else if (Val == Attribute::DereferenceableOrNull)
1363     DerefOrNullBytes = 0;
1364   else if (Val == Attribute::AllocSize)
1365     AllocSizeArgs = 0;
1366
1367   return *this;
1368 }
1369
1370 AttrBuilder &AttrBuilder::removeAttributes(AttributeList A, uint64_t Index) {
1371   remove(A.getAttributes(Index));
1372   return *this;
1373 }
1374
1375 AttrBuilder &AttrBuilder::removeAttribute(StringRef A) {
1376   std::map<std::string, std::string>::iterator I = TargetDepAttrs.find(A);
1377   if (I != TargetDepAttrs.end())
1378     TargetDepAttrs.erase(I);
1379   return *this;
1380 }
1381
1382 std::pair<unsigned, Optional<unsigned>> AttrBuilder::getAllocSizeArgs() const {
1383   return unpackAllocSizeArgs(AllocSizeArgs);
1384 }
1385
1386 AttrBuilder &AttrBuilder::addAlignmentAttr(unsigned Align) {
1387   if (Align == 0) return *this;
1388
1389   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
1390   assert(Align <= 0x40000000 && "Alignment too large.");
1391
1392   Attrs[Attribute::Alignment] = true;
1393   Alignment = Align;
1394   return *this;
1395 }
1396
1397 AttrBuilder &AttrBuilder::addStackAlignmentAttr(unsigned Align) {
1398   // Default alignment, allow the target to define how to align it.
1399   if (Align == 0) return *this;
1400
1401   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
1402   assert(Align <= 0x100 && "Alignment too large.");
1403
1404   Attrs[Attribute::StackAlignment] = true;
1405   StackAlignment = Align;
1406   return *this;
1407 }
1408
1409 AttrBuilder &AttrBuilder::addDereferenceableAttr(uint64_t Bytes) {
1410   if (Bytes == 0) return *this;
1411
1412   Attrs[Attribute::Dereferenceable] = true;
1413   DerefBytes = Bytes;
1414   return *this;
1415 }
1416
1417 AttrBuilder &AttrBuilder::addDereferenceableOrNullAttr(uint64_t Bytes) {
1418   if (Bytes == 0)
1419     return *this;
1420
1421   Attrs[Attribute::DereferenceableOrNull] = true;
1422   DerefOrNullBytes = Bytes;
1423   return *this;
1424 }
1425
1426 AttrBuilder &AttrBuilder::addAllocSizeAttr(unsigned ElemSize,
1427                                            const Optional<unsigned> &NumElems) {
1428   return addAllocSizeAttrFromRawRepr(packAllocSizeArgs(ElemSize, NumElems));
1429 }
1430
1431 AttrBuilder &AttrBuilder::addAllocSizeAttrFromRawRepr(uint64_t RawArgs) {
1432   // (0, 0) is our "not present" value, so we need to check for it here.
1433   assert(RawArgs && "Invalid allocsize arguments -- given allocsize(0, 0)");
1434
1435   Attrs[Attribute::AllocSize] = true;
1436   // Reuse existing machinery to store this as a single 64-bit integer so we can
1437   // save a few bytes over using a pair<unsigned, Optional<unsigned>>.
1438   AllocSizeArgs = RawArgs;
1439   return *this;
1440 }
1441
1442 AttrBuilder &AttrBuilder::merge(const AttrBuilder &B) {
1443   // FIXME: What if both have alignments, but they don't match?!
1444   if (!Alignment)
1445     Alignment = B.Alignment;
1446
1447   if (!StackAlignment)
1448     StackAlignment = B.StackAlignment;
1449
1450   if (!DerefBytes)
1451     DerefBytes = B.DerefBytes;
1452
1453   if (!DerefOrNullBytes)
1454     DerefOrNullBytes = B.DerefOrNullBytes;
1455
1456   if (!AllocSizeArgs)
1457     AllocSizeArgs = B.AllocSizeArgs;
1458
1459   Attrs |= B.Attrs;
1460
1461   for (auto I : B.td_attrs())
1462     TargetDepAttrs[I.first] = I.second;
1463
1464   return *this;
1465 }
1466
1467 AttrBuilder &AttrBuilder::remove(const AttrBuilder &B) {
1468   // FIXME: What if both have alignments, but they don't match?!
1469   if (B.Alignment)
1470     Alignment = 0;
1471
1472   if (B.StackAlignment)
1473     StackAlignment = 0;
1474
1475   if (B.DerefBytes)
1476     DerefBytes = 0;
1477
1478   if (B.DerefOrNullBytes)
1479     DerefOrNullBytes = 0;
1480
1481   if (B.AllocSizeArgs)
1482     AllocSizeArgs = 0;
1483
1484   Attrs &= ~B.Attrs;
1485
1486   for (auto I : B.td_attrs())
1487     TargetDepAttrs.erase(I.first);
1488
1489   return *this;
1490 }
1491
1492 bool AttrBuilder::overlaps(const AttrBuilder &B) const {
1493   // First check if any of the target independent attributes overlap.
1494   if ((Attrs & B.Attrs).any())
1495     return true;
1496
1497   // Then check if any target dependent ones do.
1498   for (const auto &I : td_attrs())
1499     if (B.contains(I.first))
1500       return true;
1501
1502   return false;
1503 }
1504
1505 bool AttrBuilder::contains(StringRef A) const {
1506   return TargetDepAttrs.find(A) != TargetDepAttrs.end();
1507 }
1508
1509 bool AttrBuilder::hasAttributes() const {
1510   return !Attrs.none() || !TargetDepAttrs.empty();
1511 }
1512
1513 bool AttrBuilder::hasAttributes(AttributeList AL, uint64_t Index) const {
1514   AttributeSet AS = AL.getAttributes(Index);
1515
1516   for (Attribute Attr : AS) {
1517     if (Attr.isEnumAttribute() || Attr.isIntAttribute()) {
1518       if (contains(Attr.getKindAsEnum()))
1519         return true;
1520     } else {
1521       assert(Attr.isStringAttribute() && "Invalid attribute kind!");
1522       return contains(Attr.getKindAsString());
1523     }
1524   }
1525
1526   return false;
1527 }
1528
1529 bool AttrBuilder::hasAlignmentAttr() const {
1530   return Alignment != 0;
1531 }
1532
1533 bool AttrBuilder::operator==(const AttrBuilder &B) {
1534   if (Attrs != B.Attrs)
1535     return false;
1536
1537   for (td_const_iterator I = TargetDepAttrs.begin(),
1538          E = TargetDepAttrs.end(); I != E; ++I)
1539     if (B.TargetDepAttrs.find(I->first) == B.TargetDepAttrs.end())
1540       return false;
1541
1542   return Alignment == B.Alignment && StackAlignment == B.StackAlignment &&
1543          DerefBytes == B.DerefBytes;
1544 }
1545
1546 //===----------------------------------------------------------------------===//
1547 // AttributeFuncs Function Defintions
1548 //===----------------------------------------------------------------------===//
1549
1550 /// \brief Which attributes cannot be applied to a type.
1551 AttrBuilder AttributeFuncs::typeIncompatible(Type *Ty) {
1552   AttrBuilder Incompatible;
1553
1554   if (!Ty->isIntegerTy())
1555     // Attribute that only apply to integers.
1556     Incompatible.addAttribute(Attribute::SExt)
1557       .addAttribute(Attribute::ZExt);
1558
1559   if (!Ty->isPointerTy())
1560     // Attribute that only apply to pointers.
1561     Incompatible.addAttribute(Attribute::ByVal)
1562       .addAttribute(Attribute::Nest)
1563       .addAttribute(Attribute::NoAlias)
1564       .addAttribute(Attribute::NoCapture)
1565       .addAttribute(Attribute::NonNull)
1566       .addDereferenceableAttr(1) // the int here is ignored
1567       .addDereferenceableOrNullAttr(1) // the int here is ignored
1568       .addAttribute(Attribute::ReadNone)
1569       .addAttribute(Attribute::ReadOnly)
1570       .addAttribute(Attribute::StructRet)
1571       .addAttribute(Attribute::InAlloca);
1572
1573   return Incompatible;
1574 }
1575
1576 template<typename AttrClass>
1577 static bool isEqual(const Function &Caller, const Function &Callee) {
1578   return Caller.getFnAttribute(AttrClass::getKind()) ==
1579          Callee.getFnAttribute(AttrClass::getKind());
1580 }
1581
1582 /// \brief Compute the logical AND of the attributes of the caller and the
1583 /// callee.
1584 ///
1585 /// This function sets the caller's attribute to false if the callee's attribute
1586 /// is false.
1587 template<typename AttrClass>
1588 static void setAND(Function &Caller, const Function &Callee) {
1589   if (AttrClass::isSet(Caller, AttrClass::getKind()) &&
1590       !AttrClass::isSet(Callee, AttrClass::getKind()))
1591     AttrClass::set(Caller, AttrClass::getKind(), false);
1592 }
1593
1594 /// \brief Compute the logical OR of the attributes of the caller and the
1595 /// callee.
1596 ///
1597 /// This function sets the caller's attribute to true if the callee's attribute
1598 /// is true.
1599 template<typename AttrClass>
1600 static void setOR(Function &Caller, const Function &Callee) {
1601   if (!AttrClass::isSet(Caller, AttrClass::getKind()) &&
1602       AttrClass::isSet(Callee, AttrClass::getKind()))
1603     AttrClass::set(Caller, AttrClass::getKind(), true);
1604 }
1605
1606 /// \brief If the inlined function had a higher stack protection level than the
1607 /// calling function, then bump up the caller's stack protection level.
1608 static void adjustCallerSSPLevel(Function &Caller, const Function &Callee) {
1609   // If upgrading the SSP attribute, clear out the old SSP Attributes first.
1610   // Having multiple SSP attributes doesn't actually hurt, but it adds useless
1611   // clutter to the IR.
1612   AttrBuilder OldSSPAttr;
1613   OldSSPAttr.addAttribute(Attribute::StackProtect)
1614       .addAttribute(Attribute::StackProtectStrong)
1615       .addAttribute(Attribute::StackProtectReq);
1616
1617   if (Callee.hasFnAttribute(Attribute::StackProtectReq)) {
1618     Caller.removeAttributes(AttributeList::FunctionIndex, OldSSPAttr);
1619     Caller.addFnAttr(Attribute::StackProtectReq);
1620   } else if (Callee.hasFnAttribute(Attribute::StackProtectStrong) &&
1621              !Caller.hasFnAttribute(Attribute::StackProtectReq)) {
1622     Caller.removeAttributes(AttributeList::FunctionIndex, OldSSPAttr);
1623     Caller.addFnAttr(Attribute::StackProtectStrong);
1624   } else if (Callee.hasFnAttribute(Attribute::StackProtect) &&
1625              !Caller.hasFnAttribute(Attribute::StackProtectReq) &&
1626              !Caller.hasFnAttribute(Attribute::StackProtectStrong))
1627     Caller.addFnAttr(Attribute::StackProtect);
1628 }
1629
1630 #define GET_ATTR_COMPAT_FUNC
1631 #include "AttributesCompatFunc.inc"
1632
1633 bool AttributeFuncs::areInlineCompatible(const Function &Caller,
1634                                          const Function &Callee) {
1635   return hasCompatibleFnAttrs(Caller, Callee);
1636 }
1637
1638 void AttributeFuncs::mergeAttributesForInlining(Function &Caller,
1639                                                 const Function &Callee) {
1640   mergeFnAttrs(Caller, Callee);
1641 }