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 // AttributeSetImpl, and AttributeSet classes.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/IR/Attributes.h"
  17 #include "AttributeImpl.h"
  18 #include "LLVMContextImpl.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/StringExtras.h"
  21 #include "llvm/IR/Type.h"
  22 #include "llvm/Support/Atomic.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/ManagedStatic.h"
  25 #include "llvm/Support/Mutex.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 //===----------------------------------------------------------------------===//
  31 // Attribute Implementation
  32 //===----------------------------------------------------------------------===//
  33
  34 Attribute Attribute::get(LLVMContext &Context, ArrayRef<AttrKind> Kinds) {
  35   AttrBuilder B;
  36   for (ArrayRef<AttrKind>::iterator I = Kinds.begin(), E = Kinds.end();
  37        I != E; ++I)
  38     B.addAttribute(*I);
  39   return Attribute::get(Context, B);
  40 }
  41
  42 Attribute Attribute::get(LLVMContext &Context, AttrBuilder &B) {
  43   // If there are no attributes, return an empty Attribute class.
  44   if (!B.hasAttributes())
  45     return Attribute();
  46
  47   // Otherwise, build a key to look up the existing attributes.
  48   LLVMContextImpl *pImpl = Context.pImpl;
  49   FoldingSetNodeID ID;
  50   ID.AddInteger(B.Raw());
  51
  52   void *InsertPoint;
  53   AttributeImpl *PA = pImpl->AttrsSet.FindNodeOrInsertPos(ID, InsertPoint);
  54
  55   if (!PA) {
  56     // If we didn't find any existing attributes of the same shape then create a
  57     // new one and insert it.
  58     PA = new AttributeImpl(Context, B.Raw());
  59     pImpl->AttrsSet.InsertNode(PA, InsertPoint);
  60   }
  61
  62   // Return the AttributesList that we found or created.
  63   return Attribute(PA);
  64 }
  65
  66 Attribute Attribute::getWithAlignment(LLVMContext &Context, uint64_t Align) {
  67   AttrBuilder B;
  68   return get(Context, B.addAlignmentAttr(Align));
  69 }
  70
  71 Attribute Attribute::getWithStackAlignment(LLVMContext &Context,
  72                                            uint64_t Align) {
  73   AttrBuilder B;
  74   return get(Context, B.addStackAlignmentAttr(Align));
  75 }
  76
  77 bool Attribute::hasAttribute(AttrKind Val) const {
  78   return pImpl && pImpl->hasAttribute(Val);
  79 }
  80
  81 bool Attribute::hasAttributes() const {
  82   return pImpl && pImpl->hasAttributes();
  83 }
  84
  85 /// This returns the alignment field of an attribute as a byte alignment value.
  86 unsigned Attribute::getAlignment() const {
  87   if (!hasAttribute(Attribute::Alignment))
  88     return 0;
  89   return pImpl->getAlignment();
  90 }
  91
  92 /// This returns the stack alignment field of an attribute as a byte alignment
  93 /// value.
  94 unsigned Attribute::getStackAlignment() const {
  95   if (!hasAttribute(Attribute::StackAlignment))
  96     return 0;
  97   return pImpl->getStackAlignment();
  98 }
  99
 100 bool Attribute::operator==(AttrKind K) const {
 101   return pImpl && *pImpl == K;
 102 }
 103 bool Attribute::operator!=(AttrKind K) const {
 104   return !(*this == K);
 105 }
 106
 107 bool Attribute::operator<(Attribute A) const {
 108   if (!pImpl && !A.pImpl) return false;
 109   if (!pImpl) return true;
 110   if (!A.pImpl) return false;
 111   return *pImpl < *A.pImpl;
 112 }
 113
 114 uint64_t Attribute::Raw() const {
 115   return pImpl ? pImpl->Raw() : 0;
 116 }
 117
 118 std::string Attribute::getAsString() const {
 119   std::string Result;
 120   if (hasAttribute(Attribute::ZExt))
 121     Result += "zeroext ";
 122   if (hasAttribute(Attribute::SExt))
 123     Result += "signext ";
 124   if (hasAttribute(Attribute::NoReturn))
 125     Result += "noreturn ";
 126   if (hasAttribute(Attribute::NoUnwind))
 127     Result += "nounwind ";
 128   if (hasAttribute(Attribute::UWTable))
 129     Result += "uwtable ";
 130   if (hasAttribute(Attribute::ReturnsTwice))
 131     Result += "returns_twice ";
 132   if (hasAttribute(Attribute::InReg))
 133     Result += "inreg ";
 134   if (hasAttribute(Attribute::NoAlias))
 135     Result += "noalias ";
 136   if (hasAttribute(Attribute::NoCapture))
 137     Result += "nocapture ";
 138   if (hasAttribute(Attribute::StructRet))
 139     Result += "sret ";
 140   if (hasAttribute(Attribute::ByVal))
 141     Result += "byval ";
 142   if (hasAttribute(Attribute::Nest))
 143     Result += "nest ";
 144   if (hasAttribute(Attribute::ReadNone))
 145     Result += "readnone ";
 146   if (hasAttribute(Attribute::ReadOnly))
 147     Result += "readonly ";
 148   if (hasAttribute(Attribute::OptimizeForSize))
 149     Result += "optsize ";
 150   if (hasAttribute(Attribute::NoInline))
 151     Result += "noinline ";
 152   if (hasAttribute(Attribute::InlineHint))
 153     Result += "inlinehint ";
 154   if (hasAttribute(Attribute::AlwaysInline))
 155     Result += "alwaysinline ";
 156   if (hasAttribute(Attribute::StackProtect))
 157     Result += "ssp ";
 158   if (hasAttribute(Attribute::StackProtectReq))
 159     Result += "sspreq ";
 160   if (hasAttribute(Attribute::StackProtectStrong))
 161     Result += "sspstrong ";
 162   if (hasAttribute(Attribute::NoRedZone))
 163     Result += "noredzone ";
 164   if (hasAttribute(Attribute::NoImplicitFloat))
 165     Result += "noimplicitfloat ";
 166   if (hasAttribute(Attribute::Naked))
 167     Result += "naked ";
 168   if (hasAttribute(Attribute::NonLazyBind))
 169     Result += "nonlazybind ";
 170   if (hasAttribute(Attribute::AddressSafety))
 171     Result += "address_safety ";
 172   if (hasAttribute(Attribute::MinSize))
 173     Result += "minsize ";
 174   if (hasAttribute(Attribute::StackAlignment)) {
 175     Result += "alignstack(";
 176     Result += utostr(getStackAlignment());
 177     Result += ") ";
 178   }
 179   if (hasAttribute(Attribute::Alignment)) {
 180     Result += "align ";
 181     Result += utostr(getAlignment());
 182     Result += " ";
 183   }
 184   if (hasAttribute(Attribute::NoDuplicate))
 185     Result += "noduplicate ";
 186   // Trim the trailing space.
 187   assert(!Result.empty() && "Unknown attribute!");
 188   Result.erase(Result.end()-1);
 189   return Result;
 190 }
 191
 192 //===----------------------------------------------------------------------===//
 193 // AttrBuilder Method Implementations
 194 //===----------------------------------------------------------------------===//
 195
 196 AttrBuilder::AttrBuilder(AttributeSet AS, unsigned Idx)
 197   : Alignment(0), StackAlignment(0) {
 198   AttributeSetImpl *pImpl = AS.pImpl;
 199   if (!pImpl) return;
 200
 201   AttrBuilder B;
 202
 203   for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I) {
 204     if (pImpl->getSlotIndex(I) != Idx) continue;
 205
 206     for (AttributeSetNode::const_iterator II = pImpl->begin(I),
 207            IE = pImpl->end(I); II != IE; ++II)
 208       B.addAttributes(*II);
 209
 210     break;
 211   }
 212
 213   if (!B.hasAttributes()) return;
 214
 215   uint64_t Mask = B.Raw();
 216
 217   for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
 218        I = Attribute::AttrKind(I + 1)) {
 219     if (uint64_t A = (Mask & AttributeImpl::getAttrMask(I))) {
 220       Attrs.insert(I);
 221
 222       if (I == Attribute::Alignment)
 223         Alignment = 1ULL << ((A >> 16) - 1);
 224       else if (I == Attribute::StackAlignment)
 225         StackAlignment = 1ULL << ((A >> 26)-1);
 226     }
 227   }
 228 }
 229
 230 void AttrBuilder::clear() {
 231   Attrs.clear();
 232   Alignment = StackAlignment = 0;
 233 }
 234
 235 AttrBuilder &AttrBuilder::addAttribute(Attribute::AttrKind Val) {
 236   Attrs.insert(Val);
 237   return *this;
 238 }
 239
 240 AttrBuilder &AttrBuilder::removeAttribute(Attribute::AttrKind Val) {
 241   Attrs.erase(Val);
 242   if (Val == Attribute::Alignment)
 243     Alignment = 0;
 244   else if (Val == Attribute::StackAlignment)
 245     StackAlignment = 0;
 246
 247   return *this;
 248 }
 249
 250 AttrBuilder &AttrBuilder::addAttributes(Attribute Attr) {
 251   uint64_t Mask = Attr.Raw();
 252
 253   for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
 254        I = Attribute::AttrKind(I + 1))
 255     if ((Mask & AttributeImpl::getAttrMask(I)) != 0)
 256       Attrs.insert(I);
 257
 258   if (Attr.getAlignment())
 259     Alignment = Attr.getAlignment();
 260   if (Attr.getStackAlignment())
 261     StackAlignment = Attr.getStackAlignment();
 262   return *this;
 263 }
 264
 265 AttrBuilder &AttrBuilder::removeAttributes(Attribute A) {
 266   uint64_t Mask = A.Raw();
 267
 268   for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
 269        I = Attribute::AttrKind(I + 1)) {
 270     if (Mask & AttributeImpl::getAttrMask(I)) {
 271       Attrs.erase(I);
 272
 273       if (I == Attribute::Alignment)
 274         Alignment = 0;
 275       else if (I == Attribute::StackAlignment)
 276         StackAlignment = 0;
 277     }
 278   }
 279
 280   return *this;
 281 }
 282
 283 AttrBuilder &AttrBuilder::addAlignmentAttr(unsigned Align) {
 284   if (Align == 0) return *this;
 285
 286   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
 287   assert(Align <= 0x40000000 && "Alignment too large.");
 288
 289   Attrs.insert(Attribute::Alignment);
 290   Alignment = Align;
 291   return *this;
 292 }
 293
 294 AttrBuilder &AttrBuilder::addStackAlignmentAttr(unsigned Align) {
 295   // Default alignment, allow the target to define how to align it.
 296   if (Align == 0) return *this;
 297
 298   assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
 299   assert(Align <= 0x100 && "Alignment too large.");
 300
 301   Attrs.insert(Attribute::StackAlignment);
 302   StackAlignment = Align;
 303   return *this;
 304 }
 305
 306 AttrBuilder &AttrBuilder::addRawValue(uint64_t Val) {
 307   for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
 308        I = Attribute::AttrKind(I + 1)) {
 309     if (uint64_t A = (Val & AttributeImpl::getAttrMask(I))) {
 310       Attrs.insert(I);
 311
 312       if (I == Attribute::Alignment)
 313         Alignment = 1ULL << ((A >> 16) - 1);
 314       else if (I == Attribute::StackAlignment)
 315         StackAlignment = 1ULL << ((A >> 26)-1);
 316     }
 317   }
 318
 319   return *this;
 320 }
 321
 322 bool AttrBuilder::contains(Attribute::AttrKind A) const {
 323   return Attrs.count(A);
 324 }
 325
 326 bool AttrBuilder::hasAttributes() const {
 327   return !Attrs.empty();
 328 }
 329
 330 bool AttrBuilder::hasAttributes(const Attribute &A) const {
 331   return Raw() & A.Raw();
 332 }
 333
 334 bool AttrBuilder::hasAlignmentAttr() const {
 335   return Alignment != 0;
 336 }
 337
 338 uint64_t AttrBuilder::Raw() const {
 339   uint64_t Mask = 0;
 340
 341   for (DenseSet<Attribute::AttrKind>::const_iterator I = Attrs.begin(),
 342          E = Attrs.end(); I != E; ++I) {
 343     Attribute::AttrKind Kind = *I;
 344
 345     if (Kind == Attribute::Alignment)
 346       Mask |= (Log2_32(Alignment) + 1) << 16;
 347     else if (Kind == Attribute::StackAlignment)
 348       Mask |= (Log2_32(StackAlignment) + 1) << 26;
 349     else
 350       Mask |= AttributeImpl::getAttrMask(Kind);
 351   }
 352
 353   return Mask;
 354 }
 355
 356 bool AttrBuilder::operator==(const AttrBuilder &B) {
 357   SmallVector<Attribute::AttrKind, 8> This(Attrs.begin(), Attrs.end());
 358   SmallVector<Attribute::AttrKind, 8> That(B.Attrs.begin(), B.Attrs.end());
 359   return This == That;
 360 }
 361
 362 //===----------------------------------------------------------------------===//
 363 // AttributeImpl Definition
 364 //===----------------------------------------------------------------------===//
 365
 366 AttributeImpl::AttributeImpl(LLVMContext &C, uint64_t data)
 367   : Context(C) {
 368   Data = ConstantInt::get(Type::getInt64Ty(C), data);
 369 }
 370 AttributeImpl::AttributeImpl(LLVMContext &C, Attribute::AttrKind data)
 371   : Context(C) {
 372   Data = ConstantInt::get(Type::getInt64Ty(C), data);
 373 }
 374 AttributeImpl::AttributeImpl(LLVMContext &C, Attribute::AttrKind data,
 375                              ArrayRef<Constant*> values)
 376   : Context(C) {
 377   Data = ConstantInt::get(Type::getInt64Ty(C), data);
 378   Vals.reserve(values.size());
 379   Vals.append(values.begin(), values.end());
 380 }
 381 AttributeImpl::AttributeImpl(LLVMContext &C, StringRef data)
 382   : Context(C) {
 383   Data = ConstantDataArray::getString(C, data);
 384 }
 385
 386 bool AttributeImpl::operator==(Attribute::AttrKind Kind) const {
 387   if (ConstantInt *CI = dyn_cast<ConstantInt>(Data))
 388     return CI->getZExtValue() == Kind;
 389   return false;
 390 }
 391 bool AttributeImpl::operator!=(Attribute::AttrKind Kind) const {
 392   return !(*this == Kind);
 393 }
 394
 395 bool AttributeImpl::operator==(StringRef Kind) const {
 396   if (ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(Data))
 397     if (CDA->isString())
 398       return CDA->getAsString() == Kind;
 399   return false;
 400 }
 401
 402 bool AttributeImpl::operator!=(StringRef Kind) const {
 403   return !(*this == Kind);
 404 }
 405
 406 bool AttributeImpl::operator<(const AttributeImpl &AI) const {
 407   if (!Data && !AI.Data) return false;
 408   if (!Data && AI.Data) return true;
 409   if (Data && !AI.Data) return false;
 410
 411   ConstantInt *ThisCI = dyn_cast<ConstantInt>(Data);
 412   ConstantInt *ThatCI = dyn_cast<ConstantInt>(AI.Data);
 413
 414   ConstantDataArray *ThisCDA = dyn_cast<ConstantDataArray>(Data);
 415   ConstantDataArray *ThatCDA = dyn_cast<ConstantDataArray>(AI.Data);
 416
 417   if (ThisCI && ThatCI)
 418     return ThisCI->getZExtValue() < ThatCI->getZExtValue();
 419
 420   if (ThisCI && ThatCDA)
 421     return true;
 422
 423   if (ThisCDA && ThatCI)
 424     return false;
 425
 426   return ThisCDA->getAsString() < ThatCDA->getAsString();
 427 }
 428
 429 uint64_t AttributeImpl::Raw() const {
 430   // FIXME: Remove this.
 431   return cast<ConstantInt>(Data)->getZExtValue();
 432 }
 433
 434 uint64_t AttributeImpl::getAttrMask(Attribute::AttrKind Val) {
 435   switch (Val) {
 436   case Attribute::EndAttrKinds:
 437   case Attribute::AttrKindEmptyKey:
 438   case Attribute::AttrKindTombstoneKey:
 439     llvm_unreachable("Synthetic enumerators which should never get here");
 440
 441   case Attribute::None:            return 0;
 442   case Attribute::ZExt:            return 1 << 0;
 443   case Attribute::SExt:            return 1 << 1;
 444   case Attribute::NoReturn:        return 1 << 2;
 445   case Attribute::InReg:           return 1 << 3;
 446   case Attribute::StructRet:       return 1 << 4;
 447   case Attribute::NoUnwind:        return 1 << 5;
 448   case Attribute::NoAlias:         return 1 << 6;
 449   case Attribute::ByVal:           return 1 << 7;
 450   case Attribute::Nest:            return 1 << 8;
 451   case Attribute::ReadNone:        return 1 << 9;
 452   case Attribute::ReadOnly:        return 1 << 10;
 453   case Attribute::NoInline:        return 1 << 11;
 454   case Attribute::AlwaysInline:    return 1 << 12;
 455   case Attribute::OptimizeForSize: return 1 << 13;
 456   case Attribute::StackProtect:    return 1 << 14;
 457   case Attribute::StackProtectReq: return 1 << 15;
 458   case Attribute::Alignment:       return 31 << 16;
 459   case Attribute::NoCapture:       return 1 << 21;
 460   case Attribute::NoRedZone:       return 1 << 22;
 461   case Attribute::NoImplicitFloat: return 1 << 23;
 462   case Attribute::Naked:           return 1 << 24;
 463   case Attribute::InlineHint:      return 1 << 25;
 464   case Attribute::StackAlignment:  return 7 << 26;
 465   case Attribute::ReturnsTwice:    return 1 << 29;
 466   case Attribute::UWTable:         return 1 << 30;
 467   case Attribute::NonLazyBind:     return 1U << 31;
 468   case Attribute::AddressSafety:   return 1ULL << 32;
 469   case Attribute::MinSize:         return 1ULL << 33;
 470   case Attribute::NoDuplicate:     return 1ULL << 34;
 471   case Attribute::StackProtectStrong: return 1ULL << 35;
 472   }
 473   llvm_unreachable("Unsupported attribute type");
 474 }
 475
 476 bool AttributeImpl::hasAttribute(Attribute::AttrKind A) const {
 477   return (Raw() & getAttrMask(A)) != 0;
 478 }
 479
 480 bool AttributeImpl::hasAttributes() const {
 481   return Raw() != 0;
 482 }
 483
 484 uint64_t AttributeImpl::getAlignment() const {
 485   uint64_t Mask = Raw() & getAttrMask(Attribute::Alignment);
 486   return 1ULL << ((Mask >> 16) - 1);
 487 }
 488
 489 uint64_t AttributeImpl::getStackAlignment() const {
 490   uint64_t Mask = Raw() & getAttrMask(Attribute::StackAlignment);
 491   return 1ULL << ((Mask >> 26) - 1);
 492 }
 493
 494 void AttributeImpl::Profile(FoldingSetNodeID &ID, Constant *Data,
 495                             ArrayRef<Constant*> Vals) {
 496   ID.AddInteger(cast<ConstantInt>(Data)->getZExtValue());
 497 #if 0
 498   // FIXME: Not yet supported.
 499   for (ArrayRef<Constant*>::iterator I = Vals.begin(), E = Vals.end();
 500        I != E; ++I)
 501     ID.AddPointer(*I);
 502 #endif
 503 }
 504
 505 //===----------------------------------------------------------------------===//
 506 // AttributeSetNode Definition
 507 //===----------------------------------------------------------------------===//
 508
 509 AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
 510                                         ArrayRef<Attribute> Attrs) {
 511   if (Attrs.empty())
 512     return 0;
 513
 514   // Otherwise, build a key to look up the existing attributes.
 515   LLVMContextImpl *pImpl = C.pImpl;
 516   FoldingSetNodeID ID;
 517
 518   SmallVector<Attribute, 8> SortedAttrs(Attrs.begin(), Attrs.end());
 519   std::sort(SortedAttrs.begin(), SortedAttrs.end());
 520
 521   for (SmallVectorImpl<Attribute>::iterator I = SortedAttrs.begin(),
 522          E = SortedAttrs.end(); I != E; ++I)
 523     I->Profile(ID);
 524
 525   void *InsertPoint;
 526   AttributeSetNode *PA =
 527     pImpl->AttrsSetNodes.FindNodeOrInsertPos(ID, InsertPoint);
 528
 529   // If we didn't find any existing attributes of the same shape then create a
 530   // new one and insert it.
 531   if (!PA) {
 532     PA = new AttributeSetNode(SortedAttrs);
 533     pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint);
 534   }
 535
 536   // Return the AttributesListNode that we found or created.
 537   return PA;
 538 }
 539
 540 //===----------------------------------------------------------------------===//
 541 // AttributeSetImpl Definition
 542 //===----------------------------------------------------------------------===//
 543
 544 uint64_t AttributeSetImpl::Raw(uint64_t Index) const {
 545   for (unsigned I = 0, E = getNumAttributes(); I != E; ++I) {
 546     if (getSlotIndex(I) != Index) continue;
 547     const AttributeSetNode *ASN = AttrNodes[I].second;
 548     AttrBuilder B;
 549
 550     for (AttributeSetNode::const_iterator II = ASN->begin(),
 551            IE = ASN->end(); II != IE; ++II)
 552       B.addAttributes(*II);
 553     return B.Raw();
 554   }
 555
 556   return 0;
 557 }
 558
 559 //===----------------------------------------------------------------------===//
 560 // AttributeSet Method Implementations
 561 //===----------------------------------------------------------------------===//
 562
 563 AttributeSet AttributeSet::getParamAttributes(unsigned Idx) const {
 564   // FIXME: Remove.
 565   return pImpl && hasAttributes(Idx) ?
 566     AttributeSet::get(pImpl->getContext(),
 567                       ArrayRef<std::pair<uint64_t, Attribute> >(
 568                         std::make_pair(Idx, getAttributes(Idx)))) :
 569     AttributeSet();
 570 }
 571
 572 AttributeSet AttributeSet::getRetAttributes() const {
 573   // FIXME: Remove.
 574   return pImpl && hasAttributes(ReturnIndex) ?
 575     AttributeSet::get(pImpl->getContext(),
 576                       ArrayRef<std::pair<uint64_t, Attribute> >(
 577                         std::make_pair(ReturnIndex,
 578                                        getAttributes(ReturnIndex)))) :
 579     AttributeSet();
 580 }
 581
 582 AttributeSet AttributeSet::getFnAttributes() const {
 583   // FIXME: Remove.
 584   return pImpl && hasAttributes(FunctionIndex) ?
 585     AttributeSet::get(pImpl->getContext(),
 586                       ArrayRef<std::pair<uint64_t, Attribute> >(
 587                         std::make_pair(FunctionIndex,
 588                                        getAttributes(FunctionIndex)))) :
 589     AttributeSet();
 590 }
 591
 592 AttributeSet AttributeSet::getImpl(LLVMContext &C,
 593                                    ArrayRef<std::pair<uint64_t,
 594                                                    AttributeSetNode*> > Attrs) {
 595   LLVMContextImpl *pImpl = C.pImpl;
 596   FoldingSetNodeID ID;
 597   AttributeSetImpl::Profile(ID, Attrs);
 598
 599   void *InsertPoint;
 600   AttributeSetImpl *PA = pImpl->AttrsLists.FindNodeOrInsertPos(ID, InsertPoint);
 601
 602   // If we didn't find any existing attributes of the same shape then
 603   // create a new one and insert it.
 604   if (!PA) {
 605     PA = new AttributeSetImpl(C, Attrs);
 606     pImpl->AttrsLists.InsertNode(PA, InsertPoint);
 607   }
 608
 609   // Return the AttributesList that we found or created.
 610   return AttributeSet(PA);
 611 }
 612
 613 AttributeSet AttributeSet::get(LLVMContext &C,
 614                                ArrayRef<std::pair<uint64_t, Attribute> > Attrs){
 615   // If there are no attributes then return a null AttributesList pointer.
 616   if (Attrs.empty())
 617     return AttributeSet();
 618
 619 #ifndef NDEBUG
 620   for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
 621     assert((!i || Attrs[i-1].first <= Attrs[i].first) &&
 622            "Misordered Attributes list!");
 623     assert(Attrs[i].second.hasAttributes() &&
 624            "Pointless attribute!");
 625   }
 626 #endif
 627
 628   // Create a vector if (uint64_t, AttributeSetNode*) pairs from the attributes
 629   // list.
 630   SmallVector<std::pair<uint64_t, AttributeSetNode*>, 8> AttrPairVec;
 631   for (ArrayRef<std::pair<uint64_t, Attribute> >::iterator I = Attrs.begin(),
 632          E = Attrs.end(); I != E; ) {
 633     uint64_t Index = I->first;
 634     SmallVector<Attribute, 4> AttrVec;
 635     while (I->first == Index && I != E) {
 636       AttrVec.push_back(I->second);
 637       ++I;
 638     }
 639
 640     AttrPairVec.push_back(std::make_pair(Index,
 641                                          AttributeSetNode::get(C, AttrVec)));
 642   }
 643
 644   return getImpl(C, AttrPairVec);
 645 }
 646
 647 AttributeSet AttributeSet::get(LLVMContext &C,
 648                                ArrayRef<std::pair<uint64_t,
 649                                                   AttributeSetNode*> > Attrs) {
 650   // If there are no attributes then return a null AttributesList pointer.
 651   if (Attrs.empty())
 652     return AttributeSet();
 653
 654   return getImpl(C, Attrs);
 655 }
 656
 657 AttributeSet AttributeSet::get(LLVMContext &C, unsigned Idx, AttrBuilder &B) {
 658   if (!B.hasAttributes())
 659     return AttributeSet();
 660   return get(C, ArrayRef<std::pair<uint64_t, Attribute> >(
 661                std::make_pair(Idx, Attribute::get(C, B))));
 662 }
 663
 664 AttributeSet AttributeSet::get(LLVMContext &C, unsigned Idx,
 665                                ArrayRef<Attribute::AttrKind> Kind) {
 666   SmallVector<std::pair<uint64_t, Attribute>, 8> Attrs;
 667   for (ArrayRef<Attribute::AttrKind>::iterator I = Kind.begin(),
 668          E = Kind.end(); I != E; ++I)
 669     Attrs.push_back(std::make_pair(Idx, Attribute::get(C, *I)));
 670   return get(C, Attrs);
 671 }
 672
 673 AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef<AttributeSet> Attrs) {
 674   SmallVector<std::pair<uint64_t, AttributeSetNode*>, 8> AttrNodeVec;
 675   for (unsigned I = 0, E = Attrs.size(); I != E; ++I) {
 676     AttributeSet AS = Attrs[I];
 677     if (!AS.pImpl) continue;
 678     AttrNodeVec.append(AS.pImpl->AttrNodes.begin(), AS.pImpl->AttrNodes.end());
 679   }
 680
 681   return get(C, AttrNodeVec);
 682 }
 683
 684 /// \brief Return the number of slots used in this attribute list.  This is the
 685 /// number of arguments that have an attribute set on them (including the
 686 /// function itself).
 687 unsigned AttributeSet::getNumSlots() const {
 688   return pImpl ? pImpl->getNumAttributes() : 0;
 689 }
 690
 691 uint64_t AttributeSet::getSlotIndex(unsigned Slot) const {
 692   assert(pImpl && Slot < pImpl->getNumAttributes() &&
 693          "Slot # out of range!");
 694   return pImpl->getSlotIndex(Slot);
 695 }
 696
 697 AttributeSet AttributeSet::getSlotAttributes(unsigned Slot) const {
 698   assert(pImpl && Slot < pImpl->getNumAttributes() &&
 699          "Slot # out of range!");
 700   return pImpl->getSlotAttributes(Slot);
 701 }
 702
 703 bool AttributeSet::hasAttribute(unsigned Index, Attribute::AttrKind Kind) const{
 704   return getAttributes(Index).hasAttribute(Kind);
 705 }
 706
 707 bool AttributeSet::hasAttributes(unsigned Index) const {
 708   return getAttributes(Index).hasAttributes();
 709 }
 710
 711 std::string AttributeSet::getAsString(unsigned Index) const {
 712   return getAttributes(Index).getAsString();
 713 }
 714
 715 unsigned AttributeSet::getParamAlignment(unsigned Idx) const {
 716   return getAttributes(Idx).getAlignment();
 717 }
 718
 719 unsigned AttributeSet::getStackAlignment(unsigned Index) const {
 720   return getAttributes(Index).getStackAlignment();
 721 }
 722
 723 uint64_t AttributeSet::Raw(unsigned Index) const {
 724   // FIXME: Remove this.
 725   return pImpl ? pImpl->Raw(Index) : 0;
 726 }
 727
 728 /// \brief The attributes for the specified index are returned.
 729 ///
 730 /// FIXME: This shouldn't return 'Attribute'.
 731 Attribute AttributeSet::getAttributes(unsigned Idx) const {
 732   if (pImpl == 0) return Attribute();
 733
 734   // Loop through to find the attribute we want.
 735   for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I) {
 736     if (pImpl->getSlotIndex(I) != Idx) continue;
 737
 738     AttrBuilder B;
 739     for (AttributeSetImpl::const_iterator II = pImpl->begin(I),
 740            IE = pImpl->end(I); II != IE; ++II)
 741       B.addAttributes(*II);
 742     return Attribute::get(pImpl->getContext(), B);
 743   }
 744
 745   return Attribute();
 746 }
 747
 748 /// hasAttrSomewhere - Return true if the specified attribute is set for at
 749 /// least one parameter or for the return value.
 750 bool AttributeSet::hasAttrSomewhere(Attribute::AttrKind Attr) const {
 751   if (pImpl == 0) return false;
 752
 753   for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I)
 754     for (AttributeSetImpl::const_iterator II = pImpl->begin(I),
 755            IE = pImpl->end(I); II != IE; ++II)
 756       if (II->hasAttribute(Attr))
 757         return true;
 758
 759   return false;
 760 }
 761
 762 AttributeSet AttributeSet::addAttribute(LLVMContext &C, unsigned Idx,
 763                                         Attribute::AttrKind Attr) const {
 764   return addAttributes(C, Idx, AttributeSet::get(C, Idx, Attr));
 765 }
 766
 767 AttributeSet AttributeSet::addAttributes(LLVMContext &C, unsigned Idx,
 768                                          AttributeSet Attrs) const {
 769   if (!pImpl) return Attrs;
 770   if (!Attrs.pImpl) return *this;
 771
 772 #ifndef NDEBUG
 773   // FIXME it is not obvious how this should work for alignment. For now, say
 774   // we can't change a known alignment.
 775   unsigned OldAlign = getParamAlignment(Idx);
 776   unsigned NewAlign = Attrs.getParamAlignment(Idx);
 777   assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
 778          "Attempt to change alignment!");
 779 #endif
 780
 781   // Add the attribute slots before the one we're trying to add.
 782   SmallVector<AttributeSet, 4> AttrSet;
 783   uint64_t NumAttrs = pImpl->getNumAttributes();
 784   AttributeSet AS;
 785   uint64_t LastIndex = 0;
 786   for (unsigned I = 0, E = NumAttrs; I != E; ++I) {
 787     if (getSlotIndex(I) >= Idx) {
 788       if (getSlotIndex(I) == Idx) AS = getSlotAttributes(LastIndex++);
 789       break;
 790     }
 791     LastIndex = I + 1;
 792     AttrSet.push_back(getSlotAttributes(I));
 793   }
 794
 795   // Now add the attribute into the correct slot. There may already be an
 796   // AttributeSet there.
 797   AttrBuilder B(AS, Idx);
 798
 799   for (unsigned I = 0, E = Attrs.pImpl->getNumAttributes(); I != E; ++I)
 800     if (Attrs.getSlotIndex(I) == Idx) {
 801       for (AttributeSetImpl::const_iterator II = Attrs.pImpl->begin(I),
 802              IE = Attrs.pImpl->end(I); II != IE; ++II)
 803         B.addAttributes(*II);
 804       break;
 805     }
 806
 807   AttrSet.push_back(AttributeSet::get(C, Idx, B));
 808
 809   // Add the remaining attribute slots.
 810   for (unsigned I = LastIndex, E = NumAttrs; I < E; ++I)
 811     AttrSet.push_back(getSlotAttributes(I));
 812
 813   return get(C, AttrSet);
 814 }
 815
 816 AttributeSet AttributeSet::removeAttribute(LLVMContext &C, unsigned Idx,
 817                                            Attribute::AttrKind Attr) const {
 818   return removeAttributes(C, Idx, AttributeSet::get(C, Idx, Attr));
 819 }
 820
 821 AttributeSet AttributeSet::removeAttributes(LLVMContext &C, unsigned Idx,
 822                                             AttributeSet Attrs) const {
 823   if (!pImpl) return AttributeSet();
 824   if (!Attrs.pImpl) return *this;
 825
 826 #ifndef NDEBUG
 827   // FIXME it is not obvious how this should work for alignment.
 828   // For now, say we can't pass in alignment, which no current use does.
 829   assert(!Attrs.hasAttribute(Idx, Attribute::Alignment) &&
 830          "Attempt to change alignment!");
 831 #endif
 832
 833   // Add the attribute slots before the one we're trying to add.
 834   SmallVector<AttributeSet, 4> AttrSet;
 835   uint64_t NumAttrs = pImpl->getNumAttributes();
 836   AttributeSet AS;
 837   uint64_t LastIndex = 0;
 838   for (unsigned I = 0, E = NumAttrs; I != E; ++I) {
 839     if (getSlotIndex(I) >= Idx) {
 840       if (getSlotIndex(I) == Idx) AS = getSlotAttributes(LastIndex++);
 841       break;
 842     }
 843     LastIndex = I + 1;
 844     AttrSet.push_back(getSlotAttributes(I));
 845   }
 846
 847   // Now add the attribute into the correct slot. There may already be an
 848   // AttributeSet there.
 849   AttrBuilder B(AS, Idx);
 850
 851   for (unsigned I = 0, E = Attrs.pImpl->getNumAttributes(); I != E; ++I)
 852     if (Attrs.getSlotIndex(I) == Idx) {
 853       for (AttributeSetImpl::const_iterator II = Attrs.pImpl->begin(I),
 854              IE = Attrs.pImpl->end(I); II != IE; ++II)
 855         B.removeAttributes(*II);
 856       break;
 857     }
 858
 859   AttrSet.push_back(AttributeSet::get(C, Idx, B));
 860
 861   // Add the remaining attribute slots.
 862   for (unsigned I = LastIndex, E = NumAttrs; I < E; ++I)
 863     AttrSet.push_back(getSlotAttributes(I));
 864
 865   return get(C, AttrSet);
 866 }
 867
 868 void AttributeSet::dump() const {
 869   dbgs() << "PAL[\n";
 870   for (unsigned i = 0, e = getNumSlots(); i < e; ++i) {
 871     uint64_t Index = getSlotIndex(i);
 872     dbgs() << "  { ";
 873     if (Index == ~0U)
 874       dbgs() << "~0U";
 875     else
 876       dbgs() << Index;
 877     dbgs() << " => " << getAsString(Index) << " }\n";
 878   }
 879
 880   dbgs() << "]\n";
 881 }
 882
 883 //===----------------------------------------------------------------------===//
 884 // AttributeFuncs Function Defintions
 885 //===----------------------------------------------------------------------===//
 886
 887 Attribute AttributeFuncs::typeIncompatible(Type *Ty) {
 888   AttrBuilder Incompatible;
 889
 890   if (!Ty->isIntegerTy())
 891     // Attribute that only apply to integers.
 892     Incompatible.addAttribute(Attribute::SExt)
 893       .addAttribute(Attribute::ZExt);
 894
 895   if (!Ty->isPointerTy())
 896     // Attribute that only apply to pointers.
 897     Incompatible.addAttribute(Attribute::ByVal)
 898       .addAttribute(Attribute::Nest)
 899       .addAttribute(Attribute::NoAlias)
 900       .addAttribute(Attribute::NoCapture)
 901       .addAttribute(Attribute::StructRet);
 902
 903   return Attribute::get(Ty->getContext(), Incompatible);
 904 }
 905
 906 /// encodeLLVMAttributesForBitcode - This returns an integer containing an
 907 /// encoding of all the LLVM attributes found in the given attribute bitset.
 908 /// Any change to this encoding is a breaking change to bitcode compatibility.
 909 uint64_t AttributeFuncs::encodeLLVMAttributesForBitcode(AttributeSet Attrs,
 910                                                         unsigned Index) {
 911   // FIXME: It doesn't make sense to store the alignment information as an
 912   // expanded out value, we should store it as a log2 value.  However, we can't
 913   // just change that here without breaking bitcode compatibility.  If this ever
 914   // becomes a problem in practice, we should introduce new tag numbers in the
 915   // bitcode file and have those tags use a more efficiently encoded alignment
 916   // field.
 917
 918   // Store the alignment in the bitcode as a 16-bit raw value instead of a 5-bit
 919   // log2 encoded value. Shift the bits above the alignment up by 11 bits.
 920   uint64_t EncodedAttrs = Attrs.Raw(Index) & 0xffff;
 921   if (Attrs.hasAttribute(Index, Attribute::Alignment))
 922     EncodedAttrs |= Attrs.getParamAlignment(Index) << 16;
 923   EncodedAttrs |= (Attrs.Raw(Index) & (0xffffULL << 21)) << 11;
 924   return EncodedAttrs;
 925 }
 926
 927 /// decodeLLVMAttributesForBitcode - This returns an attribute bitset containing
 928 /// the LLVM attributes that have been decoded from the given integer.  This
 929 /// function must stay in sync with 'encodeLLVMAttributesForBitcode'.
 930 Attribute AttributeFuncs::decodeLLVMAttributesForBitcode(LLVMContext &C,
 931                                                          uint64_t EncodedAttrs){
 932   // The alignment is stored as a 16-bit raw value from bits 31--16.  We shift
 933   // the bits above 31 down by 11 bits.
 934   unsigned Alignment = (EncodedAttrs & (0xffffULL << 16)) >> 16;
 935   assert((!Alignment || isPowerOf2_32(Alignment)) &&
 936          "Alignment must be a power of two.");
 937
 938   AttrBuilder B(EncodedAttrs & 0xffff);
 939   if (Alignment)
 940     B.addAlignmentAttr(Alignment);
 941   B.addRawValue((EncodedAttrs & (0xffffULL << 32)) >> 11);
 942   return Attribute::get(C, B);
 943 }
 944