Attributes.cpp revision 354362524a72b3fa43a6c09380b7ae3b2380cbba 
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/StringExtras.h"
20#include "llvm/IR/Type.h"
21#include "llvm/Support/Atomic.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/ManagedStatic.h"
24#include "llvm/Support/Mutex.h"
25#include "llvm/Support/raw_ostream.h"
26#include <algorithm>
27using namespace llvm;
28
29//===----------------------------------------------------------------------===//
30// Attribute Construction Methods
31//===----------------------------------------------------------------------===//
32
33Attribute Attribute::get(LLVMContext &Context, Attribute::AttrKind Kind,
34                         uint64_t Val) {
35  LLVMContextImpl *pImpl = Context.pImpl;
36  FoldingSetNodeID ID;
37  ID.AddInteger(Kind);
38  if (Val) ID.AddInteger(Val);
39
40  void *InsertPoint;
41  AttributeImpl *PA = pImpl->AttrsSet.FindNodeOrInsertPos(ID, InsertPoint);
42
43  if (!PA) {
44    // If we didn't find any existing attributes of the same shape then create a
45    // new one and insert it.
46    if (!Val)
47      PA = new EnumAttributeImpl(Kind);
48    else
49      PA = new AlignAttributeImpl(Kind, Val);
50    pImpl->AttrsSet.InsertNode(PA, InsertPoint);
51  }
52
53  // Return the Attribute that we found or created.
54  return Attribute(PA);
55}
56
57Attribute Attribute::get(LLVMContext &Context, StringRef Kind, StringRef Val) {
58  LLVMContextImpl *pImpl = Context.pImpl;
59  FoldingSetNodeID ID;
60  ID.AddString(Kind);
61  if (!Val.empty()) ID.AddString(Val);
62
63  void *InsertPoint;
64  AttributeImpl *PA = pImpl->AttrsSet.FindNodeOrInsertPos(ID, InsertPoint);
65
66  if (!PA) {
67    // If we didn't find any existing attributes of the same shape then create a
68    // new one and insert it.
69    PA = new StringAttributeImpl(Kind, Val);
70    pImpl->AttrsSet.InsertNode(PA, InsertPoint);
71  }
72
73  // Return the Attribute that we found or created.
74  return Attribute(PA);
75}
76
77Attribute Attribute::getWithAlignment(LLVMContext &Context, uint64_t Align) {
78  assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
79  assert(Align <= 0x40000000 && "Alignment too large.");
80  return get(Context, Alignment, Align);
81}
82
83Attribute Attribute::getWithStackAlignment(LLVMContext &Context,
84                                           uint64_t Align) {
85  assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
86  assert(Align <= 0x100 && "Alignment too large.");
87  return get(Context, StackAlignment, Align);
88}
89
90//===----------------------------------------------------------------------===//
91// Attribute Accessor Methods
92//===----------------------------------------------------------------------===//
93
94bool Attribute::isEnumAttribute() const {
95  return pImpl && pImpl->isEnumAttribute();
96}
97
98bool Attribute::isAlignAttribute() const {
99  return pImpl && pImpl->isAlignAttribute();
100}
101
102bool Attribute::isStringAttribute() const {
103  return pImpl && pImpl->isStringAttribute();
104}
105
106Attribute::AttrKind Attribute::getKindAsEnum() const {
107  if (!pImpl) return None;
108  assert((isEnumAttribute() || isAlignAttribute()) &&
109         "Invalid attribute type to get the kind as an enum!");
110  return pImpl ? pImpl->getKindAsEnum() : None;
111}
112
113uint64_t Attribute::getValueAsInt() const {
114  if (!pImpl) return 0;
115  assert(isAlignAttribute() &&
116         "Expected the attribute to be an alignment attribute!");
117  return pImpl ? pImpl->getValueAsInt() : 0;
118}
119
120StringRef Attribute::getKindAsString() const {
121  if (!pImpl) return StringRef();
122  assert(isStringAttribute() &&
123         "Invalid attribute type to get the kind as a string!");
124  return pImpl ? pImpl->getKindAsString() : StringRef();
125}
126
127StringRef Attribute::getValueAsString() const {
128  if (!pImpl) return StringRef();
129  assert(isStringAttribute() &&
130         "Invalid attribute type to get the value as a string!");
131  return pImpl ? pImpl->getValueAsString() : StringRef();
132}
133
134bool Attribute::hasAttribute(AttrKind Kind) const {
135  return (pImpl && pImpl->hasAttribute(Kind)) || (!pImpl && Kind == None);
136}
137
138bool Attribute::hasAttribute(StringRef Kind) const {
139  if (!isStringAttribute()) return false;
140  return pImpl && pImpl->hasAttribute(Kind);
141}
142
143/// This returns the alignment field of an attribute as a byte alignment value.
144unsigned Attribute::getAlignment() const {
145  assert(hasAttribute(Attribute::Alignment) &&
146         "Trying to get alignment from non-alignment attribute!");
147  return pImpl->getValueAsInt();
148}
149
150/// This returns the stack alignment field of an attribute as a byte alignment
151/// value.
152unsigned Attribute::getStackAlignment() const {
153  assert(hasAttribute(Attribute::StackAlignment) &&
154         "Trying to get alignment from non-alignment attribute!");
155  return pImpl->getValueAsInt();
156}
157
158std::string Attribute::getAsString(bool InAttrGrp) const {
159  if (!pImpl) return "";
160
161  if (hasAttribute(Attribute::SanitizeAddress))
162    return "sanitize_address";
163  if (hasAttribute(Attribute::AlwaysInline))
164    return "alwaysinline";
165  if (hasAttribute(Attribute::Builtin))
166    return "builtin";
167  if (hasAttribute(Attribute::ByVal))
168    return "byval";
169  if (hasAttribute(Attribute::InlineHint))
170    return "inlinehint";
171  if (hasAttribute(Attribute::InReg))
172    return "inreg";
173  if (hasAttribute(Attribute::MinSize))
174    return "minsize";
175  if (hasAttribute(Attribute::Naked))
176    return "naked";
177  if (hasAttribute(Attribute::Nest))
178    return "nest";
179  if (hasAttribute(Attribute::NoAlias))
180    return "noalias";
181  if (hasAttribute(Attribute::NoBuiltin))
182    return "nobuiltin";
183  if (hasAttribute(Attribute::NoCapture))
184    return "nocapture";
185  if (hasAttribute(Attribute::NoDuplicate))
186    return "noduplicate";
187  if (hasAttribute(Attribute::NoImplicitFloat))
188    return "noimplicitfloat";
189  if (hasAttribute(Attribute::NoInline))
190    return "noinline";
191  if (hasAttribute(Attribute::NonLazyBind))
192    return "nonlazybind";
193  if (hasAttribute(Attribute::NoRedZone))
194    return "noredzone";
195  if (hasAttribute(Attribute::NoReturn))
196    return "noreturn";
197  if (hasAttribute(Attribute::NoUnwind))
198    return "nounwind";
199  if (hasAttribute(Attribute::OptimizeNone))
200    return "optnone";
201  if (hasAttribute(Attribute::OptimizeForSize))
202    return "optsize";
203  if (hasAttribute(Attribute::ReadNone))
204    return "readnone";
205  if (hasAttribute(Attribute::ReadOnly))
206    return "readonly";
207  if (hasAttribute(Attribute::Returned))
208    return "returned";
209  if (hasAttribute(Attribute::ReturnsTwice))
210    return "returns_twice";
211  if (hasAttribute(Attribute::SExt))
212    return "signext";
213  if (hasAttribute(Attribute::StackProtect))
214    return "ssp";
215  if (hasAttribute(Attribute::StackProtectReq))
216    return "sspreq";
217  if (hasAttribute(Attribute::StackProtectStrong))
218    return "sspstrong";
219  if (hasAttribute(Attribute::StructRet))
220    return "sret";
221  if (hasAttribute(Attribute::SanitizeThread))
222    return "sanitize_thread";
223  if (hasAttribute(Attribute::SanitizeMemory))
224    return "sanitize_memory";
225  if (hasAttribute(Attribute::UWTable))
226    return "uwtable";
227  if (hasAttribute(Attribute::ZExt))
228    return "zeroext";
229  if (hasAttribute(Attribute::Cold))
230    return "cold";
231
232  // FIXME: These should be output like this:
233  //
234  //   align=4
235  //   alignstack=8
236  //
237  if (hasAttribute(Attribute::Alignment)) {
238    std::string Result;
239    Result += "align";
240    Result += (InAttrGrp) ? "=" : " ";
241    Result += utostr(getValueAsInt());
242    return Result;
243  }
244
245  if (hasAttribute(Attribute::StackAlignment)) {
246    std::string Result;
247    Result += "alignstack";
248    if (InAttrGrp) {
249      Result += "=";
250      Result += utostr(getValueAsInt());
251    } else {
252      Result += "(";
253      Result += utostr(getValueAsInt());
254      Result += ")";
255    }
256    return Result;
257  }
258
259  // Convert target-dependent attributes to strings of the form:
260  //
261  //   "kind"
262  //   "kind" = "value"
263  //
264  if (isStringAttribute()) {
265    std::string Result;
266    Result += '\"' + getKindAsString().str() + '"';
267
268    StringRef Val = pImpl->getValueAsString();
269    if (Val.empty()) return Result;
270
271    Result += "=\"" + Val.str() + '"';
272    return Result;
273  }
274
275  llvm_unreachable("Unknown attribute");
276}
277
278bool Attribute::operator<(Attribute A) const {
279  if (!pImpl && !A.pImpl) return false;
280  if (!pImpl) return true;
281  if (!A.pImpl) return false;
282  return *pImpl < *A.pImpl;
283}
284
285//===----------------------------------------------------------------------===//
286// AttributeImpl Definition
287//===----------------------------------------------------------------------===//
288
289// Pin the vtabels to this file.
290AttributeImpl::~AttributeImpl() {}
291void EnumAttributeImpl::anchor() {}
292void AlignAttributeImpl::anchor() {}
293void StringAttributeImpl::anchor() {}
294
295bool AttributeImpl::hasAttribute(Attribute::AttrKind A) const {
296  if (isStringAttribute()) return false;
297  return getKindAsEnum() == A;
298}
299
300bool AttributeImpl::hasAttribute(StringRef Kind) const {
301  if (!isStringAttribute()) return false;
302  return getKindAsString() == Kind;
303}
304
305Attribute::AttrKind AttributeImpl::getKindAsEnum() const {
306  assert(isEnumAttribute() || isAlignAttribute());
307  return static_cast<const EnumAttributeImpl *>(this)->getEnumKind();
308}
309
310uint64_t AttributeImpl::getValueAsInt() const {
311  assert(isAlignAttribute());
312  return static_cast<const AlignAttributeImpl *>(this)->getAlignment();
313}
314
315StringRef AttributeImpl::getKindAsString() const {
316  assert(isStringAttribute());
317  return static_cast<const StringAttributeImpl *>(this)->getStringKind();
318}
319
320StringRef AttributeImpl::getValueAsString() const {
321  assert(isStringAttribute());
322  return static_cast<const StringAttributeImpl *>(this)->getStringValue();
323}
324
325bool AttributeImpl::operator<(const AttributeImpl &AI) const {
326  // This sorts the attributes with Attribute::AttrKinds coming first (sorted
327  // relative to their enum value) and then strings.
328  if (isEnumAttribute()) {
329    if (AI.isEnumAttribute()) return getKindAsEnum() < AI.getKindAsEnum();
330    if (AI.isAlignAttribute()) return true;
331    if (AI.isStringAttribute()) return true;
332  }
333
334  if (isAlignAttribute()) {
335    if (AI.isEnumAttribute()) return false;
336    if (AI.isAlignAttribute()) return getValueAsInt() < AI.getValueAsInt();
337    if (AI.isStringAttribute()) return true;
338  }
339
340  if (AI.isEnumAttribute()) return false;
341  if (AI.isAlignAttribute()) return false;
342  if (getKindAsString() == AI.getKindAsString())
343    return getValueAsString() < AI.getValueAsString();
344  return getKindAsString() < AI.getKindAsString();
345}
346
347uint64_t AttributeImpl::getAttrMask(Attribute::AttrKind Val) {
348  // FIXME: Remove this.
349  switch (Val) {
350  case Attribute::EndAttrKinds:
351    llvm_unreachable("Synthetic enumerators which should never get here");
352
353  case Attribute::None:            return 0;
354  case Attribute::ZExt:            return 1 << 0;
355  case Attribute::SExt:            return 1 << 1;
356  case Attribute::NoReturn:        return 1 << 2;
357  case Attribute::InReg:           return 1 << 3;
358  case Attribute::StructRet:       return 1 << 4;
359  case Attribute::NoUnwind:        return 1 << 5;
360  case Attribute::NoAlias:         return 1 << 6;
361  case Attribute::ByVal:           return 1 << 7;
362  case Attribute::Nest:            return 1 << 8;
363  case Attribute::ReadNone:        return 1 << 9;
364  case Attribute::ReadOnly:        return 1 << 10;
365  case Attribute::NoInline:        return 1 << 11;
366  case Attribute::AlwaysInline:    return 1 << 12;
367  case Attribute::OptimizeForSize: return 1 << 13;
368  case Attribute::StackProtect:    return 1 << 14;
369  case Attribute::StackProtectReq: return 1 << 15;
370  case Attribute::Alignment:       return 31 << 16;
371  case Attribute::NoCapture:       return 1 << 21;
372  case Attribute::NoRedZone:       return 1 << 22;
373  case Attribute::NoImplicitFloat: return 1 << 23;
374  case Attribute::Naked:           return 1 << 24;
375  case Attribute::InlineHint:      return 1 << 25;
376  case Attribute::StackAlignment:  return 7 << 26;
377  case Attribute::ReturnsTwice:    return 1 << 29;
378  case Attribute::UWTable:         return 1 << 30;
379  case Attribute::NonLazyBind:     return 1U << 31;
380  case Attribute::SanitizeAddress: return 1ULL << 32;
381  case Attribute::MinSize:         return 1ULL << 33;
382  case Attribute::NoDuplicate:     return 1ULL << 34;
383  case Attribute::StackProtectStrong: return 1ULL << 35;
384  case Attribute::SanitizeThread:  return 1ULL << 36;
385  case Attribute::SanitizeMemory:  return 1ULL << 37;
386  case Attribute::NoBuiltin:       return 1ULL << 38;
387  case Attribute::Returned:        return 1ULL << 39;
388  case Attribute::Cold:            return 1ULL << 40;
389  case Attribute::Builtin:         return 1ULL << 41;
390  case Attribute::OptimizeNone:    return 1ULL << 42;
391  }
392  llvm_unreachable("Unsupported attribute type");
393}
394
395//===----------------------------------------------------------------------===//
396// AttributeSetNode Definition
397//===----------------------------------------------------------------------===//
398
399AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
400                                        ArrayRef<Attribute> Attrs) {
401  if (Attrs.empty())
402    return 0;
403
404  // Otherwise, build a key to look up the existing attributes.
405  LLVMContextImpl *pImpl = C.pImpl;
406  FoldingSetNodeID ID;
407
408  SmallVector<Attribute, 8> SortedAttrs(Attrs.begin(), Attrs.end());
409  array_pod_sort(SortedAttrs.begin(), SortedAttrs.end());
410
411  for (SmallVectorImpl<Attribute>::iterator I = SortedAttrs.begin(),
412         E = SortedAttrs.end(); I != E; ++I)
413    I->Profile(ID);
414
415  void *InsertPoint;
416  AttributeSetNode *PA =
417    pImpl->AttrsSetNodes.FindNodeOrInsertPos(ID, InsertPoint);
418
419  // If we didn't find any existing attributes of the same shape then create a
420  // new one and insert it.
421  if (!PA) {
422    // Coallocate entries after the AttributeSetNode itself.
423    void *Mem = ::operator new(sizeof(AttributeSetNode) +
424                               sizeof(Attribute) * SortedAttrs.size());
425    PA = new (Mem) AttributeSetNode(SortedAttrs);
426    pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint);
427  }
428
429  // Return the AttributesListNode that we found or created.
430  return PA;
431}
432
433bool AttributeSetNode::hasAttribute(Attribute::AttrKind Kind) const {
434  for (iterator I = begin(), E = end(); I != E; ++I)
435    if (I->hasAttribute(Kind))
436      return true;
437  return false;
438}
439
440bool AttributeSetNode::hasAttribute(StringRef Kind) const {
441  for (iterator I = begin(), E = end(); I != E; ++I)
442    if (I->hasAttribute(Kind))
443      return true;
444  return false;
445}
446
447Attribute AttributeSetNode::getAttribute(Attribute::AttrKind Kind) const {
448  for (iterator I = begin(), E = end(); I != E; ++I)
449    if (I->hasAttribute(Kind))
450      return *I;
451  return Attribute();
452}
453
454Attribute AttributeSetNode::getAttribute(StringRef Kind) const {
455  for (iterator I = begin(), E = end(); I != E; ++I)
456    if (I->hasAttribute(Kind))
457      return *I;
458  return Attribute();
459}
460
461unsigned AttributeSetNode::getAlignment() const {
462  for (iterator I = begin(), E = end(); I != E; ++I)
463    if (I->hasAttribute(Attribute::Alignment))
464      return I->getAlignment();
465  return 0;
466}
467
468unsigned AttributeSetNode::getStackAlignment() const {
469  for (iterator I = begin(), E = end(); I != E; ++I)
470    if (I->hasAttribute(Attribute::StackAlignment))
471      return I->getStackAlignment();
472  return 0;
473}
474
475std::string AttributeSetNode::getAsString(bool InAttrGrp) const {
476  std::string Str;
477  for (iterator I = begin(), E = end(); I != E; ++I) {
478    if (I != begin())
479      Str += ' ';
480    Str += I->getAsString(InAttrGrp);
481  }
482  return Str;
483}
484
485//===----------------------------------------------------------------------===//
486// AttributeSetImpl Definition
487//===----------------------------------------------------------------------===//
488
489uint64_t AttributeSetImpl::Raw(unsigned Index) const {
490  for (unsigned I = 0, E = getNumAttributes(); I != E; ++I) {
491    if (getSlotIndex(I) != Index) continue;
492    const AttributeSetNode *ASN = getSlotNode(I);
493    uint64_t Mask = 0;
494
495    for (AttributeSetNode::iterator II = ASN->begin(),
496           IE = ASN->end(); II != IE; ++II) {
497      Attribute Attr = *II;
498
499      // This cannot handle string attributes.
500      if (Attr.isStringAttribute()) continue;
501
502      Attribute::AttrKind Kind = Attr.getKindAsEnum();
503
504      if (Kind == Attribute::Alignment)
505        Mask |= (Log2_32(ASN->getAlignment()) + 1) << 16;
506      else if (Kind == Attribute::StackAlignment)
507        Mask |= (Log2_32(ASN->getStackAlignment()) + 1) << 26;
508      else
509        Mask |= AttributeImpl::getAttrMask(Kind);
510    }
511
512    return Mask;
513  }
514
515  return 0;
516}
517
518void AttributeSetImpl::dump() const {
519  AttributeSet(const_cast<AttributeSetImpl *>(this)).dump();
520}
521
522//===----------------------------------------------------------------------===//
523// AttributeSet Construction and Mutation Methods
524//===----------------------------------------------------------------------===//
525
526AttributeSet
527AttributeSet::getImpl(LLVMContext &C,
528                      ArrayRef<std::pair<unsigned, AttributeSetNode*> > Attrs) {
529  LLVMContextImpl *pImpl = C.pImpl;
530  FoldingSetNodeID ID;
531  AttributeSetImpl::Profile(ID, Attrs);
532
533  void *InsertPoint;
534  AttributeSetImpl *PA = pImpl->AttrsLists.FindNodeOrInsertPos(ID, InsertPoint);
535
536  // If we didn't find any existing attributes of the same shape then
537  // create a new one and insert it.
538  if (!PA) {
539    // Coallocate entries after the AttributeSetImpl itself.
540    void *Mem = ::operator new(sizeof(AttributeSetImpl) +
541                               sizeof(std::pair<unsigned, AttributeSetNode *>) *
542                                   Attrs.size());
543    PA = new (Mem) AttributeSetImpl(C, Attrs);
544    pImpl->AttrsLists.InsertNode(PA, InsertPoint);
545  }
546
547  // Return the AttributesList that we found or created.
548  return AttributeSet(PA);
549}
550
551AttributeSet AttributeSet::get(LLVMContext &C,
552                               ArrayRef<std::pair<unsigned, Attribute> > Attrs){
553  // If there are no attributes then return a null AttributesList pointer.
554  if (Attrs.empty())
555    return AttributeSet();
556
557#ifndef NDEBUG
558  for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
559    assert((!i || Attrs[i-1].first <= Attrs[i].first) &&
560           "Misordered Attributes list!");
561    assert(!Attrs[i].second.hasAttribute(Attribute::None) &&
562           "Pointless attribute!");
563  }
564#endif
565
566  // Create a vector if (unsigned, AttributeSetNode*) pairs from the attributes
567  // list.
568  SmallVector<std::pair<unsigned, AttributeSetNode*>, 8> AttrPairVec;
569  for (ArrayRef<std::pair<unsigned, Attribute> >::iterator I = Attrs.begin(),
570         E = Attrs.end(); I != E; ) {
571    unsigned Index = I->first;
572    SmallVector<Attribute, 4> AttrVec;
573    while (I != E && I->first == Index) {
574      AttrVec.push_back(I->second);
575      ++I;
576    }
577
578    AttrPairVec.push_back(std::make_pair(Index,
579                                         AttributeSetNode::get(C, AttrVec)));
580  }
581
582  return getImpl(C, AttrPairVec);
583}
584
585AttributeSet AttributeSet::get(LLVMContext &C,
586                               ArrayRef<std::pair<unsigned,
587                                                  AttributeSetNode*> > Attrs) {
588  // If there are no attributes then return a null AttributesList pointer.
589  if (Attrs.empty())
590    return AttributeSet();
591
592  return getImpl(C, Attrs);
593}
594
595AttributeSet AttributeSet::get(LLVMContext &C, unsigned Index, AttrBuilder &B) {
596  if (!B.hasAttributes())
597    return AttributeSet();
598
599  // Add target-independent attributes.
600  SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
601  for (Attribute::AttrKind Kind = Attribute::None;
602       Kind != Attribute::EndAttrKinds; Kind = Attribute::AttrKind(Kind + 1)) {
603    if (!B.contains(Kind))
604      continue;
605
606    if (Kind == Attribute::Alignment)
607      Attrs.push_back(std::make_pair(Index, Attribute::
608                                     getWithAlignment(C, B.getAlignment())));
609    else if (Kind == Attribute::StackAlignment)
610      Attrs.push_back(std::make_pair(Index, Attribute::
611                              getWithStackAlignment(C, B.getStackAlignment())));
612    else
613      Attrs.push_back(std::make_pair(Index, Attribute::get(C, Kind)));
614  }
615
616  // Add target-dependent (string) attributes.
617  for (AttrBuilder::td_iterator I = B.td_begin(), E = B.td_end();
618       I != E; ++I)
619    Attrs.push_back(std::make_pair(Index, Attribute::get(C, I->first,I->second)));
620
621  return get(C, Attrs);
622}
623
624AttributeSet AttributeSet::get(LLVMContext &C, unsigned Index,
625                               ArrayRef<Attribute::AttrKind> Kind) {
626  SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
627  for (ArrayRef<Attribute::AttrKind>::iterator I = Kind.begin(),
628         E = Kind.end(); I != E; ++I)
629    Attrs.push_back(std::make_pair(Index, Attribute::get(C, *I)));
630  return get(C, Attrs);
631}
632
633AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef<AttributeSet> Attrs) {
634  if (Attrs.empty()) return AttributeSet();
635  if (Attrs.size() == 1) return Attrs[0];
636
637  SmallVector<std::pair<unsigned, AttributeSetNode*>, 8> AttrNodeVec;
638  AttributeSetImpl *A0 = Attrs[0].pImpl;
639  if (A0)
640    AttrNodeVec.append(A0->getNode(0), A0->getNode(A0->getNumAttributes()));
641  // Copy all attributes from Attrs into AttrNodeVec while keeping AttrNodeVec
642  // ordered by index.  Because we know that each list in Attrs is ordered by
643  // index we only need to merge each successive list in rather than doing a
644  // full sort.
645  for (unsigned I = 1, E = Attrs.size(); I != E; ++I) {
646    AttributeSetImpl *AS = Attrs[I].pImpl;
647    if (!AS) continue;
648    SmallVector<std::pair<unsigned, AttributeSetNode *>, 8>::iterator
649      ANVI = AttrNodeVec.begin(), ANVE;
650    for (const AttributeSetImpl::IndexAttrPair
651             *AI = AS->getNode(0),
652             *AE = AS->getNode(AS->getNumAttributes());
653         AI != AE; ++AI) {
654      ANVE = AttrNodeVec.end();
655      while (ANVI != ANVE && ANVI->first <= AI->first)
656        ++ANVI;
657      ANVI = AttrNodeVec.insert(ANVI, *AI) + 1;
658    }
659  }
660
661  return getImpl(C, AttrNodeVec);
662}
663
664AttributeSet AttributeSet::addAttribute(LLVMContext &C, unsigned Index,
665                                        Attribute::AttrKind Attr) const {
666  if (hasAttribute(Index, Attr)) return *this;
667  return addAttributes(C, Index, AttributeSet::get(C, Index, Attr));
668}
669
670AttributeSet AttributeSet::addAttribute(LLVMContext &C, unsigned Index,
671                                        StringRef Kind) const {
672  llvm::AttrBuilder B;
673  B.addAttribute(Kind);
674  return addAttributes(C, Index, AttributeSet::get(C, Index, B));
675}
676
677AttributeSet AttributeSet::addAttribute(LLVMContext &C, unsigned Index,
678                                        StringRef Kind, StringRef Value) const {
679  llvm::AttrBuilder B;
680  B.addAttribute(Kind, Value);
681  return addAttributes(C, Index, AttributeSet::get(C, Index, B));
682}
683
684AttributeSet AttributeSet::addAttributes(LLVMContext &C, unsigned Index,
685                                         AttributeSet Attrs) const {
686  if (!pImpl) return Attrs;
687  if (!Attrs.pImpl) return *this;
688
689#ifndef NDEBUG
690  // FIXME it is not obvious how this should work for alignment. For now, say
691  // we can't change a known alignment.
692  unsigned OldAlign = getParamAlignment(Index);
693  unsigned NewAlign = Attrs.getParamAlignment(Index);
694  assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
695         "Attempt to change alignment!");
696#endif
697
698  // Add the attribute slots before the one we're trying to add.
699  SmallVector<AttributeSet, 4> AttrSet;
700  uint64_t NumAttrs = pImpl->getNumAttributes();
701  AttributeSet AS;
702  uint64_t LastIndex = 0;
703  for (unsigned I = 0, E = NumAttrs; I != E; ++I) {
704    if (getSlotIndex(I) >= Index) {
705      if (getSlotIndex(I) == Index) AS = getSlotAttributes(LastIndex++);
706      break;
707    }
708    LastIndex = I + 1;
709    AttrSet.push_back(getSlotAttributes(I));
710  }
711
712  // Now add the attribute into the correct slot. There may already be an
713  // AttributeSet there.
714  AttrBuilder B(AS, Index);
715
716  for (unsigned I = 0, E = Attrs.pImpl->getNumAttributes(); I != E; ++I)
717    if (Attrs.getSlotIndex(I) == Index) {
718      for (AttributeSetImpl::iterator II = Attrs.pImpl->begin(I),
719             IE = Attrs.pImpl->end(I); II != IE; ++II)
720        B.addAttribute(*II);
721      break;
722    }
723
724  AttrSet.push_back(AttributeSet::get(C, Index, B));
725
726  // Add the remaining attribute slots.
727  for (unsigned I = LastIndex, E = NumAttrs; I < E; ++I)
728    AttrSet.push_back(getSlotAttributes(I));
729
730  return get(C, AttrSet);
731}
732
733AttributeSet AttributeSet::removeAttribute(LLVMContext &C, unsigned Index,
734                                           Attribute::AttrKind Attr) const {
735  if (!hasAttribute(Index, Attr)) return *this;
736  return removeAttributes(C, Index, AttributeSet::get(C, Index, Attr));
737}
738
739AttributeSet AttributeSet::removeAttributes(LLVMContext &C, unsigned Index,
740                                            AttributeSet Attrs) const {
741  if (!pImpl) return AttributeSet();
742  if (!Attrs.pImpl) return *this;
743
744#ifndef NDEBUG
745  // FIXME it is not obvious how this should work for alignment.
746  // For now, say we can't pass in alignment, which no current use does.
747  assert(!Attrs.hasAttribute(Index, Attribute::Alignment) &&
748         "Attempt to change alignment!");
749#endif
750
751  // Add the attribute slots before the one we're trying to add.
752  SmallVector<AttributeSet, 4> AttrSet;
753  uint64_t NumAttrs = pImpl->getNumAttributes();
754  AttributeSet AS;
755  uint64_t LastIndex = 0;
756  for (unsigned I = 0, E = NumAttrs; I != E; ++I) {
757    if (getSlotIndex(I) >= Index) {
758      if (getSlotIndex(I) == Index) AS = getSlotAttributes(LastIndex++);
759      break;
760    }
761    LastIndex = I + 1;
762    AttrSet.push_back(getSlotAttributes(I));
763  }
764
765  // Now remove the attribute from the correct slot. There may already be an
766  // AttributeSet there.
767  AttrBuilder B(AS, Index);
768
769  for (unsigned I = 0, E = Attrs.pImpl->getNumAttributes(); I != E; ++I)
770    if (Attrs.getSlotIndex(I) == Index) {
771      B.removeAttributes(Attrs.pImpl->getSlotAttributes(I), Index);
772      break;
773    }
774
775  AttrSet.push_back(AttributeSet::get(C, Index, B));
776
777  // Add the remaining attribute slots.
778  for (unsigned I = LastIndex, E = NumAttrs; I < E; ++I)
779    AttrSet.push_back(getSlotAttributes(I));
780
781  return get(C, AttrSet);
782}
783
784//===----------------------------------------------------------------------===//
785// AttributeSet Accessor Methods
786//===----------------------------------------------------------------------===//
787
788LLVMContext &AttributeSet::getContext() const {
789  return pImpl->getContext();
790}
791
792AttributeSet AttributeSet::getParamAttributes(unsigned Index) const {
793  return pImpl && hasAttributes(Index) ?
794    AttributeSet::get(pImpl->getContext(),
795                      ArrayRef<std::pair<unsigned, AttributeSetNode*> >(
796                        std::make_pair(Index, getAttributes(Index)))) :
797    AttributeSet();
798}
799
800AttributeSet AttributeSet::getRetAttributes() const {
801  return pImpl && hasAttributes(ReturnIndex) ?
802    AttributeSet::get(pImpl->getContext(),
803                      ArrayRef<std::pair<unsigned, AttributeSetNode*> >(
804                        std::make_pair(ReturnIndex,
805                                       getAttributes(ReturnIndex)))) :
806    AttributeSet();
807}
808
809AttributeSet AttributeSet::getFnAttributes() const {
810  return pImpl && hasAttributes(FunctionIndex) ?
811    AttributeSet::get(pImpl->getContext(),
812                      ArrayRef<std::pair<unsigned, AttributeSetNode*> >(
813                        std::make_pair(FunctionIndex,
814                                       getAttributes(FunctionIndex)))) :
815    AttributeSet();
816}
817
818bool AttributeSet::hasAttribute(unsigned Index, Attribute::AttrKind Kind) const{
819  AttributeSetNode *ASN = getAttributes(Index);
820  return ASN ? ASN->hasAttribute(Kind) : false;
821}
822
823bool AttributeSet::hasAttribute(unsigned Index, StringRef Kind) const {
824  AttributeSetNode *ASN = getAttributes(Index);
825  return ASN ? ASN->hasAttribute(Kind) : false;
826}
827
828bool AttributeSet::hasAttributes(unsigned Index) const {
829  AttributeSetNode *ASN = getAttributes(Index);
830  return ASN ? ASN->hasAttributes() : false;
831}
832
833/// \brief Return true if the specified attribute is set for at least one
834/// parameter or for the return value.
835bool AttributeSet::hasAttrSomewhere(Attribute::AttrKind Attr) const {
836  if (pImpl == 0) return false;
837
838  for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I)
839    for (AttributeSetImpl::iterator II = pImpl->begin(I),
840           IE = pImpl->end(I); II != IE; ++II)
841      if (II->hasAttribute(Attr))
842        return true;
843
844  return false;
845}
846
847Attribute AttributeSet::getAttribute(unsigned Index,
848                                     Attribute::AttrKind Kind) const {
849  AttributeSetNode *ASN = getAttributes(Index);
850  return ASN ? ASN->getAttribute(Kind) : Attribute();
851}
852
853Attribute AttributeSet::getAttribute(unsigned Index,
854                                     StringRef Kind) const {
855  AttributeSetNode *ASN = getAttributes(Index);
856  return ASN ? ASN->getAttribute(Kind) : Attribute();
857}
858
859unsigned AttributeSet::getParamAlignment(unsigned Index) const {
860  AttributeSetNode *ASN = getAttributes(Index);
861  return ASN ? ASN->getAlignment() : 0;
862}
863
864unsigned AttributeSet::getStackAlignment(unsigned Index) const {
865  AttributeSetNode *ASN = getAttributes(Index);
866  return ASN ? ASN->getStackAlignment() : 0;
867}
868
869std::string AttributeSet::getAsString(unsigned Index,
870                                      bool InAttrGrp) const {
871  AttributeSetNode *ASN = getAttributes(Index);
872  return ASN ? ASN->getAsString(InAttrGrp) : std::string("");
873}
874
875/// \brief The attributes for the specified index are returned.
876AttributeSetNode *AttributeSet::getAttributes(unsigned Index) const {
877  if (!pImpl) return 0;
878
879  // Loop through to find the attribute node we want.
880  for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I)
881    if (pImpl->getSlotIndex(I) == Index)
882      return pImpl->getSlotNode(I);
883
884  return 0;
885}
886
887AttributeSet::iterator AttributeSet::begin(unsigned Slot) const {
888  if (!pImpl)
889    return ArrayRef<Attribute>().begin();
890  return pImpl->begin(Slot);
891}
892
893AttributeSet::iterator AttributeSet::end(unsigned Slot) const {
894  if (!pImpl)
895    return ArrayRef<Attribute>().end();
896  return pImpl->end(Slot);
897}
898
899//===----------------------------------------------------------------------===//
900// AttributeSet Introspection Methods
901//===----------------------------------------------------------------------===//
902
903/// \brief Return the number of slots used in this attribute list.  This is the
904/// number of arguments that have an attribute set on them (including the
905/// function itself).
906unsigned AttributeSet::getNumSlots() const {
907  return pImpl ? pImpl->getNumAttributes() : 0;
908}
909
910unsigned AttributeSet::getSlotIndex(unsigned Slot) const {
911  assert(pImpl && Slot < pImpl->getNumAttributes() &&
912         "Slot # out of range!");
913  return pImpl->getSlotIndex(Slot);
914}
915
916AttributeSet AttributeSet::getSlotAttributes(unsigned Slot) const {
917  assert(pImpl && Slot < pImpl->getNumAttributes() &&
918         "Slot # out of range!");
919  return pImpl->getSlotAttributes(Slot);
920}
921
922uint64_t AttributeSet::Raw(unsigned Index) const {
923  // FIXME: Remove this.
924  return pImpl ? pImpl->Raw(Index) : 0;
925}
926
927void AttributeSet::dump() const {
928  dbgs() << "PAL[\n";
929
930  for (unsigned i = 0, e = getNumSlots(); i < e; ++i) {
931    uint64_t Index = getSlotIndex(i);
932    dbgs() << "  { ";
933    if (Index == ~0U)
934      dbgs() << "~0U";
935    else
936      dbgs() << Index;
937    dbgs() << " => " << getAsString(Index) << " }\n";
938  }
939
940  dbgs() << "]\n";
941}
942
943//===----------------------------------------------------------------------===//
944// AttrBuilder Method Implementations
945//===----------------------------------------------------------------------===//
946
947AttrBuilder::AttrBuilder(AttributeSet AS, unsigned Index)
948  : Attrs(0), Alignment(0), StackAlignment(0) {
949  AttributeSetImpl *pImpl = AS.pImpl;
950  if (!pImpl) return;
951
952  for (unsigned I = 0, E = pImpl->getNumAttributes(); I != E; ++I) {
953    if (pImpl->getSlotIndex(I) != Index) continue;
954
955    for (AttributeSetImpl::iterator II = pImpl->begin(I),
956           IE = pImpl->end(I); II != IE; ++II)
957      addAttribute(*II);
958
959    break;
960  }
961}
962
963void AttrBuilder::clear() {
964  Attrs.reset();
965  Alignment = StackAlignment = 0;
966}
967
968AttrBuilder &AttrBuilder::addAttribute(Attribute::AttrKind Val) {
969  assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
970  assert(Val != Attribute::Alignment && Val != Attribute::StackAlignment &&
971         "Adding alignment attribute without adding alignment value!");
972  Attrs[Val] = true;
973  return *this;
974}
975
976AttrBuilder &AttrBuilder::addAttribute(Attribute Attr) {
977  if (Attr.isStringAttribute()) {
978    addAttribute(Attr.getKindAsString(), Attr.getValueAsString());
979    return *this;
980  }
981
982  Attribute::AttrKind Kind = Attr.getKindAsEnum();
983  Attrs[Kind] = true;
984
985  if (Kind == Attribute::Alignment)
986    Alignment = Attr.getAlignment();
987  else if (Kind == Attribute::StackAlignment)
988    StackAlignment = Attr.getStackAlignment();
989  return *this;
990}
991
992AttrBuilder &AttrBuilder::addAttribute(StringRef A, StringRef V) {
993  TargetDepAttrs[A] = V;
994  return *this;
995}
996
997AttrBuilder &AttrBuilder::removeAttribute(Attribute::AttrKind Val) {
998  assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
999  Attrs[Val] = false;
1000
1001  if (Val == Attribute::Alignment)
1002    Alignment = 0;
1003  else if (Val == Attribute::StackAlignment)
1004    StackAlignment = 0;
1005
1006  return *this;
1007}
1008
1009AttrBuilder &AttrBuilder::removeAttributes(AttributeSet A, uint64_t Index) {
1010  unsigned Slot = ~0U;
1011  for (unsigned I = 0, E = A.getNumSlots(); I != E; ++I)
1012    if (A.getSlotIndex(I) == Index) {
1013      Slot = I;
1014      break;
1015    }
1016
1017  assert(Slot != ~0U && "Couldn't find index in AttributeSet!");
1018
1019  for (AttributeSet::iterator I = A.begin(Slot), E = A.end(Slot); I != E; ++I) {
1020    Attribute Attr = *I;
1021    if (Attr.isEnumAttribute() || Attr.isAlignAttribute()) {
1022      Attribute::AttrKind Kind = I->getKindAsEnum();
1023      Attrs[Kind] = false;
1024
1025      if (Kind == Attribute::Alignment)
1026        Alignment = 0;
1027      else if (Kind == Attribute::StackAlignment)
1028        StackAlignment = 0;
1029    } else {
1030      assert(Attr.isStringAttribute() && "Invalid attribute type!");
1031      std::map<std::string, std::string>::iterator
1032        Iter = TargetDepAttrs.find(Attr.getKindAsString());
1033      if (Iter != TargetDepAttrs.end())
1034        TargetDepAttrs.erase(Iter);
1035    }
1036  }
1037
1038  return *this;
1039}
1040
1041AttrBuilder &AttrBuilder::removeAttribute(StringRef A) {
1042  std::map<std::string, std::string>::iterator I = TargetDepAttrs.find(A);
1043  if (I != TargetDepAttrs.end())
1044    TargetDepAttrs.erase(I);
1045  return *this;
1046}
1047
1048AttrBuilder &AttrBuilder::addAlignmentAttr(unsigned Align) {
1049  if (Align == 0) return *this;
1050
1051  assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
1052  assert(Align <= 0x40000000 && "Alignment too large.");
1053
1054  Attrs[Attribute::Alignment] = true;
1055  Alignment = Align;
1056  return *this;
1057}
1058
1059AttrBuilder &AttrBuilder::addStackAlignmentAttr(unsigned Align) {
1060  // Default alignment, allow the target to define how to align it.
1061  if (Align == 0) return *this;
1062
1063  assert(isPowerOf2_32(Align) && "Alignment must be a power of two.");
1064  assert(Align <= 0x100 && "Alignment too large.");
1065
1066  Attrs[Attribute::StackAlignment] = true;
1067  StackAlignment = Align;
1068  return *this;
1069}
1070
1071AttrBuilder &AttrBuilder::merge(const AttrBuilder &B) {
1072  // FIXME: What if both have alignments, but they don't match?!
1073  if (!Alignment)
1074    Alignment = B.Alignment;
1075
1076  if (!StackAlignment)
1077    StackAlignment = B.StackAlignment;
1078
1079  Attrs |= B.Attrs;
1080
1081  for (td_const_iterator I = B.TargetDepAttrs.begin(),
1082         E = B.TargetDepAttrs.end(); I != E; ++I)
1083    TargetDepAttrs[I->first] = I->second;
1084
1085  return *this;
1086}
1087
1088bool AttrBuilder::contains(StringRef A) const {
1089  return TargetDepAttrs.find(A) != TargetDepAttrs.end();
1090}
1091
1092bool AttrBuilder::hasAttributes() const {
1093  return !Attrs.none() || !TargetDepAttrs.empty();
1094}
1095
1096bool AttrBuilder::hasAttributes(AttributeSet A, uint64_t Index) const {
1097  unsigned Slot = ~0U;
1098  for (unsigned I = 0, E = A.getNumSlots(); I != E; ++I)
1099    if (A.getSlotIndex(I) == Index) {
1100      Slot = I;
1101      break;
1102    }
1103
1104  assert(Slot != ~0U && "Couldn't find the index!");
1105
1106  for (AttributeSet::iterator I = A.begin(Slot), E = A.end(Slot);
1107       I != E; ++I) {
1108    Attribute Attr = *I;
1109    if (Attr.isEnumAttribute() || Attr.isAlignAttribute()) {
1110      if (Attrs[I->getKindAsEnum()])
1111        return true;
1112    } else {
1113      assert(Attr.isStringAttribute() && "Invalid attribute kind!");
1114      return TargetDepAttrs.find(Attr.getKindAsString())!=TargetDepAttrs.end();
1115    }
1116  }
1117
1118  return false;
1119}
1120
1121bool AttrBuilder::hasAlignmentAttr() const {
1122  return Alignment != 0;
1123}
1124
1125bool AttrBuilder::operator==(const AttrBuilder &B) {
1126  if (Attrs != B.Attrs)
1127    return false;
1128
1129  for (td_const_iterator I = TargetDepAttrs.begin(),
1130         E = TargetDepAttrs.end(); I != E; ++I)
1131    if (B.TargetDepAttrs.find(I->first) == B.TargetDepAttrs.end())
1132      return false;
1133
1134  return Alignment == B.Alignment && StackAlignment == B.StackAlignment;
1135}
1136
1137AttrBuilder &AttrBuilder::addRawValue(uint64_t Val) {
1138  // FIXME: Remove this in 4.0.
1139  if (!Val) return *this;
1140
1141  for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
1142       I = Attribute::AttrKind(I + 1)) {
1143    if (uint64_t A = (Val & AttributeImpl::getAttrMask(I))) {
1144      Attrs[I] = true;
1145
1146      if (I == Attribute::Alignment)
1147        Alignment = 1ULL << ((A >> 16) - 1);
1148      else if (I == Attribute::StackAlignment)
1149        StackAlignment = 1ULL << ((A >> 26)-1);
1150    }
1151  }
1152
1153  return *this;
1154}
1155
1156//===----------------------------------------------------------------------===//
1157// AttributeFuncs Function Defintions
1158//===----------------------------------------------------------------------===//
1159
1160/// \brief Which attributes cannot be applied to a type.
1161AttributeSet AttributeFuncs::typeIncompatible(Type *Ty, uint64_t Index) {
1162  AttrBuilder Incompatible;
1163
1164  if (!Ty->isIntegerTy())
1165    // Attribute that only apply to integers.
1166    Incompatible.addAttribute(Attribute::SExt)
1167      .addAttribute(Attribute::ZExt);
1168
1169  if (!Ty->isPointerTy())
1170    // Attribute that only apply to pointers.
1171    Incompatible.addAttribute(Attribute::ByVal)
1172      .addAttribute(Attribute::Nest)
1173      .addAttribute(Attribute::NoAlias)
1174      .addAttribute(Attribute::NoCapture)
1175      .addAttribute(Attribute::ReadNone)
1176      .addAttribute(Attribute::ReadOnly)
1177      .addAttribute(Attribute::StructRet);
1178
1179  return AttributeSet::get(Ty->getContext(), Index, Incompatible);
1180}
1181