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