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