blob: d848fe9218684d91a4d54a6c26853356f15e118f [file] [log] [blame]
Andrew Scull5e1ddfa2018-08-14 10:06:54 +01001//===- llvm/Value.h - Definition of the Value class -------------*- C++ -*-===//
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// This file declares the Value class.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_IR_VALUE_H
15#define LLVM_IR_VALUE_H
16
17#include "llvm-c/Types.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/IR/Use.h"
20#include "llvm/Support/CBindingWrapping.h"
21#include "llvm/Support/Casting.h"
22#include <cassert>
23#include <iterator>
24#include <memory>
25
26namespace llvm {
27
28class APInt;
29class Argument;
30class BasicBlock;
31class Constant;
32class ConstantData;
33class ConstantAggregate;
34class DataLayout;
35class Function;
36class GlobalAlias;
37class GlobalIFunc;
38class GlobalIndirectSymbol;
39class GlobalObject;
40class GlobalValue;
41class GlobalVariable;
42class InlineAsm;
43class Instruction;
44class LLVMContext;
45class Module;
46class ModuleSlotTracker;
47class raw_ostream;
48template<typename ValueTy> class StringMapEntry;
49class StringRef;
50class Twine;
51class Type;
52class User;
53
54using ValueName = StringMapEntry<Value *>;
55
56//===----------------------------------------------------------------------===//
57// Value Class
58//===----------------------------------------------------------------------===//
59
60/// \brief LLVM Value Representation
61///
62/// This is a very important LLVM class. It is the base class of all values
63/// computed by a program that may be used as operands to other values. Value is
64/// the super class of other important classes such as Instruction and Function.
65/// All Values have a Type. Type is not a subclass of Value. Some values can
66/// have a name and they belong to some Module. Setting the name on the Value
67/// automatically updates the module's symbol table.
68///
69/// Every value has a "use list" that keeps track of which other Values are
70/// using this Value. A Value can also have an arbitrary number of ValueHandle
71/// objects that watch it and listen to RAUW and Destroy events. See
72/// llvm/IR/ValueHandle.h for details.
73class Value {
74 // The least-significant bit of the first word of Value *must* be zero:
75 // http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
76 Type *VTy;
77 Use *UseList;
78
79 friend class ValueAsMetadata; // Allow access to IsUsedByMD.
80 friend class ValueHandleBase;
81
82 const unsigned char SubclassID; // Subclass identifier (for isa/dyn_cast)
83 unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this?
84
85protected:
86 /// \brief Hold subclass data that can be dropped.
87 ///
88 /// This member is similar to SubclassData, however it is for holding
89 /// information which may be used to aid optimization, but which may be
90 /// cleared to zero without affecting conservative interpretation.
91 unsigned char SubclassOptionalData : 7;
92
93private:
94 /// \brief Hold arbitrary subclass data.
95 ///
96 /// This member is defined by this class, but is not used for anything.
97 /// Subclasses can use it to hold whatever state they find useful. This
98 /// field is initialized to zero by the ctor.
99 unsigned short SubclassData;
100
101protected:
102 /// \brief The number of operands in the subclass.
103 ///
104 /// This member is defined by this class, but not used for anything.
105 /// Subclasses can use it to store their number of operands, if they have
106 /// any.
107 ///
108 /// This is stored here to save space in User on 64-bit hosts. Since most
109 /// instances of Value have operands, 32-bit hosts aren't significantly
110 /// affected.
111 ///
112 /// Note, this should *NOT* be used directly by any class other than User.
113 /// User uses this value to find the Use list.
114 enum : unsigned { NumUserOperandsBits = 28 };
115 unsigned NumUserOperands : NumUserOperandsBits;
116
117 // Use the same type as the bitfield above so that MSVC will pack them.
118 unsigned IsUsedByMD : 1;
119 unsigned HasName : 1;
120 unsigned HasHungOffUses : 1;
121 unsigned HasDescriptor : 1;
122
123private:
124 template <typename UseT> // UseT == 'Use' or 'const Use'
125 class use_iterator_impl
126 : public std::iterator<std::forward_iterator_tag, UseT *> {
127 friend class Value;
128
129 UseT *U;
130
131 explicit use_iterator_impl(UseT *u) : U(u) {}
132
133 public:
134 use_iterator_impl() : U() {}
135
136 bool operator==(const use_iterator_impl &x) const { return U == x.U; }
137 bool operator!=(const use_iterator_impl &x) const { return !operator==(x); }
138
139 use_iterator_impl &operator++() { // Preincrement
140 assert(U && "Cannot increment end iterator!");
141 U = U->getNext();
142 return *this;
143 }
144
145 use_iterator_impl operator++(int) { // Postincrement
146 auto tmp = *this;
147 ++*this;
148 return tmp;
149 }
150
151 UseT &operator*() const {
152 assert(U && "Cannot dereference end iterator!");
153 return *U;
154 }
155
156 UseT *operator->() const { return &operator*(); }
157
158 operator use_iterator_impl<const UseT>() const {
159 return use_iterator_impl<const UseT>(U);
160 }
161 };
162
163 template <typename UserTy> // UserTy == 'User' or 'const User'
164 class user_iterator_impl
165 : public std::iterator<std::forward_iterator_tag, UserTy *> {
166 use_iterator_impl<Use> UI;
167 explicit user_iterator_impl(Use *U) : UI(U) {}
168 friend class Value;
169
170 public:
171 user_iterator_impl() = default;
172
173 bool operator==(const user_iterator_impl &x) const { return UI == x.UI; }
174 bool operator!=(const user_iterator_impl &x) const { return !operator==(x); }
175
176 /// \brief Returns true if this iterator is equal to user_end() on the value.
177 bool atEnd() const { return *this == user_iterator_impl(); }
178
179 user_iterator_impl &operator++() { // Preincrement
180 ++UI;
181 return *this;
182 }
183
184 user_iterator_impl operator++(int) { // Postincrement
185 auto tmp = *this;
186 ++*this;
187 return tmp;
188 }
189
190 // Retrieve a pointer to the current User.
191 UserTy *operator*() const {
192 return UI->getUser();
193 }
194
195 UserTy *operator->() const { return operator*(); }
196
197 operator user_iterator_impl<const UserTy>() const {
198 return user_iterator_impl<const UserTy>(*UI);
199 }
200
201 Use &getUse() const { return *UI; }
202 };
203
204protected:
205 Value(Type *Ty, unsigned scid);
206
207 /// Value's destructor should be virtual by design, but that would require
208 /// that Value and all of its subclasses have a vtable that effectively
209 /// duplicates the information in the value ID. As a size optimization, the
210 /// destructor has been protected, and the caller should manually call
211 /// deleteValue.
212 ~Value(); // Use deleteValue() to delete a generic Value.
213
214public:
215 Value(const Value &) = delete;
216 Value &operator=(const Value &) = delete;
217
218 /// Delete a pointer to a generic Value.
219 void deleteValue();
220
221 /// \brief Support for debugging, callable in GDB: V->dump()
222 void dump() const;
223
224 /// \brief Implement operator<< on Value.
225 /// @{
226 void print(raw_ostream &O, bool IsForDebug = false) const;
227 void print(raw_ostream &O, ModuleSlotTracker &MST,
228 bool IsForDebug = false) const;
229 /// @}
230
231 /// \brief Print the name of this Value out to the specified raw_ostream.
232 ///
233 /// This is useful when you just want to print 'int %reg126', not the
234 /// instruction that generated it. If you specify a Module for context, then
235 /// even constanst get pretty-printed; for example, the type of a null
236 /// pointer is printed symbolically.
237 /// @{
238 void printAsOperand(raw_ostream &O, bool PrintType = true,
239 const Module *M = nullptr) const;
240 void printAsOperand(raw_ostream &O, bool PrintType,
241 ModuleSlotTracker &MST) const;
242 /// @}
243
244 /// \brief All values are typed, get the type of this value.
245 Type *getType() const { return VTy; }
246
247 /// \brief All values hold a context through their type.
248 LLVMContext &getContext() const;
249
250 // \brief All values can potentially be named.
251 bool hasName() const { return HasName; }
252 ValueName *getValueName() const;
253 void setValueName(ValueName *VN);
254
255private:
256 void destroyValueName();
257 void doRAUW(Value *New, bool NoMetadata);
258 void setNameImpl(const Twine &Name);
259
260public:
261 /// \brief Return a constant reference to the value's name.
262 ///
263 /// This guaranteed to return the same reference as long as the value is not
264 /// modified. If the value has a name, this does a hashtable lookup, so it's
265 /// not free.
266 StringRef getName() const;
267
268 /// \brief Change the name of the value.
269 ///
270 /// Choose a new unique name if the provided name is taken.
271 ///
272 /// \param Name The new name; or "" if the value's name should be removed.
273 void setName(const Twine &Name);
274
275 /// \brief Transfer the name from V to this value.
276 ///
277 /// After taking V's name, sets V's name to empty.
278 ///
279 /// \note It is an error to call V->takeName(V).
280 void takeName(Value *V);
281
282 /// \brief Change all uses of this to point to a new Value.
283 ///
284 /// Go through the uses list for this definition and make each use point to
285 /// "V" instead of "this". After this completes, 'this's use list is
286 /// guaranteed to be empty.
287 void replaceAllUsesWith(Value *V);
288
289 /// \brief Change non-metadata uses of this to point to a new Value.
290 ///
291 /// Go through the uses list for this definition and make each use point to
292 /// "V" instead of "this". This function skips metadata entries in the list.
293 void replaceNonMetadataUsesWith(Value *V);
294
295 /// replaceUsesOutsideBlock - Go through the uses list for this definition and
296 /// make each use point to "V" instead of "this" when the use is outside the
297 /// block. 'This's use list is expected to have at least one element.
298 /// Unlike replaceAllUsesWith this function does not support basic block
299 /// values or constant users.
300 void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
301
302 /// replaceUsesExceptBlockAddr - Go through the uses list for this definition
303 /// and make each use point to "V" instead of "this" when the use is outside
304 /// the block. 'This's use list is expected to have at least one element.
305 /// Unlike replaceAllUsesWith this function skips blockaddr uses.
306 void replaceUsesExceptBlockAddr(Value *New);
307
308 //----------------------------------------------------------------------
309 // Methods for handling the chain of uses of this Value.
310 //
311 // Materializing a function can introduce new uses, so these methods come in
312 // two variants:
313 // The methods that start with materialized_ check the uses that are
314 // currently known given which functions are materialized. Be very careful
315 // when using them since you might not get all uses.
316 // The methods that don't start with materialized_ assert that modules is
317 // fully materialized.
318 void assertModuleIsMaterializedImpl() const;
319 // This indirection exists so we can keep assertModuleIsMaterializedImpl()
320 // around in release builds of Value.cpp to be linked with other code built
321 // in debug mode. But this avoids calling it in any of the release built code.
322 void assertModuleIsMaterialized() const {
323#ifndef NDEBUG
324 assertModuleIsMaterializedImpl();
325#endif
326 }
327
328 bool use_empty() const {
329 assertModuleIsMaterialized();
330 return UseList == nullptr;
331 }
332
333 bool materialized_use_empty() const {
334 return UseList == nullptr;
335 }
336
337 using use_iterator = use_iterator_impl<Use>;
338 using const_use_iterator = use_iterator_impl<const Use>;
339
340 use_iterator materialized_use_begin() { return use_iterator(UseList); }
341 const_use_iterator materialized_use_begin() const {
342 return const_use_iterator(UseList);
343 }
344 use_iterator use_begin() {
345 assertModuleIsMaterialized();
346 return materialized_use_begin();
347 }
348 const_use_iterator use_begin() const {
349 assertModuleIsMaterialized();
350 return materialized_use_begin();
351 }
352 use_iterator use_end() { return use_iterator(); }
353 const_use_iterator use_end() const { return const_use_iterator(); }
354 iterator_range<use_iterator> materialized_uses() {
355 return make_range(materialized_use_begin(), use_end());
356 }
357 iterator_range<const_use_iterator> materialized_uses() const {
358 return make_range(materialized_use_begin(), use_end());
359 }
360 iterator_range<use_iterator> uses() {
361 assertModuleIsMaterialized();
362 return materialized_uses();
363 }
364 iterator_range<const_use_iterator> uses() const {
365 assertModuleIsMaterialized();
366 return materialized_uses();
367 }
368
369 bool user_empty() const {
370 assertModuleIsMaterialized();
371 return UseList == nullptr;
372 }
373
374 using user_iterator = user_iterator_impl<User>;
375 using const_user_iterator = user_iterator_impl<const User>;
376
377 user_iterator materialized_user_begin() { return user_iterator(UseList); }
378 const_user_iterator materialized_user_begin() const {
379 return const_user_iterator(UseList);
380 }
381 user_iterator user_begin() {
382 assertModuleIsMaterialized();
383 return materialized_user_begin();
384 }
385 const_user_iterator user_begin() const {
386 assertModuleIsMaterialized();
387 return materialized_user_begin();
388 }
389 user_iterator user_end() { return user_iterator(); }
390 const_user_iterator user_end() const { return const_user_iterator(); }
391 User *user_back() {
392 assertModuleIsMaterialized();
393 return *materialized_user_begin();
394 }
395 const User *user_back() const {
396 assertModuleIsMaterialized();
397 return *materialized_user_begin();
398 }
399 iterator_range<user_iterator> materialized_users() {
400 return make_range(materialized_user_begin(), user_end());
401 }
402 iterator_range<const_user_iterator> materialized_users() const {
403 return make_range(materialized_user_begin(), user_end());
404 }
405 iterator_range<user_iterator> users() {
406 assertModuleIsMaterialized();
407 return materialized_users();
408 }
409 iterator_range<const_user_iterator> users() const {
410 assertModuleIsMaterialized();
411 return materialized_users();
412 }
413
414 /// \brief Return true if there is exactly one user of this value.
415 ///
416 /// This is specialized because it is a common request and does not require
417 /// traversing the whole use list.
418 bool hasOneUse() const {
419 const_use_iterator I = use_begin(), E = use_end();
420 if (I == E) return false;
421 return ++I == E;
422 }
423
424 /// \brief Return true if this Value has exactly N users.
425 bool hasNUses(unsigned N) const;
426
427 /// \brief Return true if this value has N users or more.
428 ///
429 /// This is logically equivalent to getNumUses() >= N.
430 bool hasNUsesOrMore(unsigned N) const;
431
432 /// \brief Check if this value is used in the specified basic block.
433 bool isUsedInBasicBlock(const BasicBlock *BB) const;
434
435 /// \brief This method computes the number of uses of this Value.
436 ///
437 /// This is a linear time operation. Use hasOneUse, hasNUses, or
438 /// hasNUsesOrMore to check for specific values.
439 unsigned getNumUses() const;
440
441 /// \brief This method should only be used by the Use class.
442 void addUse(Use &U) { U.addToList(&UseList); }
443
444 /// \brief Concrete subclass of this.
445 ///
446 /// An enumeration for keeping track of the concrete subclass of Value that
447 /// is actually instantiated. Values of this enumeration are kept in the
448 /// Value classes SubclassID field. They are used for concrete type
449 /// identification.
450 enum ValueTy {
451#define HANDLE_VALUE(Name) Name##Val,
452#include "llvm/IR/Value.def"
453
454 // Markers:
455#define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val,
456#include "llvm/IR/Value.def"
457 };
458
459 /// \brief Return an ID for the concrete type of this object.
460 ///
461 /// This is used to implement the classof checks. This should not be used
462 /// for any other purpose, as the values may change as LLVM evolves. Also,
463 /// note that for instructions, the Instruction's opcode is added to
464 /// InstructionVal. So this means three things:
465 /// # there is no value with code InstructionVal (no opcode==0).
466 /// # there are more possible values for the value type than in ValueTy enum.
467 /// # the InstructionVal enumerator must be the highest valued enumerator in
468 /// the ValueTy enum.
469 unsigned getValueID() const {
470 return SubclassID;
471 }
472
473 /// \brief Return the raw optional flags value contained in this value.
474 ///
475 /// This should only be used when testing two Values for equivalence.
476 unsigned getRawSubclassOptionalData() const {
477 return SubclassOptionalData;
478 }
479
480 /// \brief Clear the optional flags contained in this value.
481 void clearSubclassOptionalData() {
482 SubclassOptionalData = 0;
483 }
484
485 /// \brief Check the optional flags for equality.
486 bool hasSameSubclassOptionalData(const Value *V) const {
487 return SubclassOptionalData == V->SubclassOptionalData;
488 }
489
490 /// \brief Return true if there is a value handle associated with this value.
491 bool hasValueHandle() const { return HasValueHandle; }
492
493 /// \brief Return true if there is metadata referencing this value.
494 bool isUsedByMetadata() const { return IsUsedByMD; }
495
496 /// \brief Return true if this value is a swifterror value.
497 ///
498 /// swifterror values can be either a function argument or an alloca with a
499 /// swifterror attribute.
500 bool isSwiftError() const;
501
502 /// \brief Strip off pointer casts, all-zero GEPs, and aliases.
503 ///
504 /// Returns the original uncasted value. If this is called on a non-pointer
505 /// value, it returns 'this'.
506 const Value *stripPointerCasts() const;
507 Value *stripPointerCasts() {
508 return const_cast<Value *>(
509 static_cast<const Value *>(this)->stripPointerCasts());
510 }
511
512 /// \brief Strip off pointer casts, all-zero GEPs, aliases and barriers.
513 ///
514 /// Returns the original uncasted value. If this is called on a non-pointer
515 /// value, it returns 'this'. This function should be used only in
516 /// Alias analysis.
517 const Value *stripPointerCastsAndBarriers() const;
518 Value *stripPointerCastsAndBarriers() {
519 return const_cast<Value *>(
520 static_cast<const Value *>(this)->stripPointerCastsAndBarriers());
521 }
522
523 /// \brief Strip off pointer casts and all-zero GEPs.
524 ///
525 /// Returns the original uncasted value. If this is called on a non-pointer
526 /// value, it returns 'this'.
527 const Value *stripPointerCastsNoFollowAliases() const;
528 Value *stripPointerCastsNoFollowAliases() {
529 return const_cast<Value *>(
530 static_cast<const Value *>(this)->stripPointerCastsNoFollowAliases());
531 }
532
533 /// \brief Strip off pointer casts and all-constant inbounds GEPs.
534 ///
535 /// Returns the original pointer value. If this is called on a non-pointer
536 /// value, it returns 'this'.
537 const Value *stripInBoundsConstantOffsets() const;
538 Value *stripInBoundsConstantOffsets() {
539 return const_cast<Value *>(
540 static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
541 }
542
543 /// \brief Accumulate offsets from \a stripInBoundsConstantOffsets().
544 ///
545 /// Stores the resulting constant offset stripped into the APInt provided.
546 /// The provided APInt will be extended or truncated as needed to be the
547 /// correct bitwidth for an offset of this pointer type.
548 ///
549 /// If this is called on a non-pointer value, it returns 'this'.
550 const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
551 APInt &Offset) const;
552 Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
553 APInt &Offset) {
554 return const_cast<Value *>(static_cast<const Value *>(this)
555 ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset));
556 }
557
558 /// \brief Strip off pointer casts and inbounds GEPs.
559 ///
560 /// Returns the original pointer value. If this is called on a non-pointer
561 /// value, it returns 'this'.
562 const Value *stripInBoundsOffsets() const;
563 Value *stripInBoundsOffsets() {
564 return const_cast<Value *>(
565 static_cast<const Value *>(this)->stripInBoundsOffsets());
566 }
567
568 /// \brief Returns the number of bytes known to be dereferenceable for the
569 /// pointer value.
570 ///
571 /// If CanBeNull is set by this function the pointer can either be null or be
572 /// dereferenceable up to the returned number of bytes.
573 uint64_t getPointerDereferenceableBytes(const DataLayout &DL,
574 bool &CanBeNull) const;
575
576 /// \brief Returns an alignment of the pointer value.
577 ///
578 /// Returns an alignment which is either specified explicitly, e.g. via
579 /// align attribute of a function argument, or guaranteed by DataLayout.
580 unsigned getPointerAlignment(const DataLayout &DL) const;
581
582 /// \brief Translate PHI node to its predecessor from the given basic block.
583 ///
584 /// If this value is a PHI node with CurBB as its parent, return the value in
585 /// the PHI node corresponding to PredBB. If not, return ourself. This is
586 /// useful if you want to know the value something has in a predecessor
587 /// block.
588 const Value *DoPHITranslation(const BasicBlock *CurBB,
589 const BasicBlock *PredBB) const;
590 Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) {
591 return const_cast<Value *>(
592 static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB));
593 }
594
595 /// \brief The maximum alignment for instructions.
596 ///
597 /// This is the greatest alignment value supported by load, store, and alloca
598 /// instructions, and global values.
599 static const unsigned MaxAlignmentExponent = 29;
600 static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent;
601
602 /// \brief Mutate the type of this Value to be of the specified type.
603 ///
604 /// Note that this is an extremely dangerous operation which can create
605 /// completely invalid IR very easily. It is strongly recommended that you
606 /// recreate IR objects with the right types instead of mutating them in
607 /// place.
608 void mutateType(Type *Ty) {
609 VTy = Ty;
610 }
611
612 /// \brief Sort the use-list.
613 ///
614 /// Sorts the Value's use-list by Cmp using a stable mergesort. Cmp is
615 /// expected to compare two \a Use references.
616 template <class Compare> void sortUseList(Compare Cmp);
617
618 /// \brief Reverse the use-list.
619 void reverseUseList();
620
621private:
622 /// \brief Merge two lists together.
623 ///
624 /// Merges \c L and \c R using \c Cmp. To enable stable sorts, always pushes
625 /// "equal" items from L before items from R.
626 ///
627 /// \return the first element in the list.
628 ///
629 /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update).
630 template <class Compare>
631 static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
632 Use *Merged;
633 Use **Next = &Merged;
634
635 while (true) {
636 if (!L) {
637 *Next = R;
638 break;
639 }
640 if (!R) {
641 *Next = L;
642 break;
643 }
644 if (Cmp(*R, *L)) {
645 *Next = R;
646 Next = &R->Next;
647 R = R->Next;
648 } else {
649 *Next = L;
650 Next = &L->Next;
651 L = L->Next;
652 }
653 }
654
655 return Merged;
656 }
657
658protected:
659 unsigned short getSubclassDataFromValue() const { return SubclassData; }
660 void setValueSubclassData(unsigned short D) { SubclassData = D; }
661};
662
663struct ValueDeleter { void operator()(Value *V) { V->deleteValue(); } };
664
665/// Use this instead of std::unique_ptr<Value> or std::unique_ptr<Instruction>.
666/// Those don't work because Value and Instruction's destructors are protected,
667/// aren't virtual, and won't destroy the complete object.
668using unique_value = std::unique_ptr<Value, ValueDeleter>;
669
670inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
671 V.print(OS);
672 return OS;
673}
674
675void Use::set(Value *V) {
676 if (Val) removeFromList();
677 Val = V;
678 if (V) V->addUse(*this);
679}
680
681Value *Use::operator=(Value *RHS) {
682 set(RHS);
683 return RHS;
684}
685
686const Use &Use::operator=(const Use &RHS) {
687 set(RHS.Val);
688 return *this;
689}
690
691template <class Compare> void Value::sortUseList(Compare Cmp) {
692 if (!UseList || !UseList->Next)
693 // No need to sort 0 or 1 uses.
694 return;
695
696 // Note: this function completely ignores Prev pointers until the end when
697 // they're fixed en masse.
698
699 // Create a binomial vector of sorted lists, visiting uses one at a time and
700 // merging lists as necessary.
701 const unsigned MaxSlots = 32;
702 Use *Slots[MaxSlots];
703
704 // Collect the first use, turning it into a single-item list.
705 Use *Next = UseList->Next;
706 UseList->Next = nullptr;
707 unsigned NumSlots = 1;
708 Slots[0] = UseList;
709
710 // Collect all but the last use.
711 while (Next->Next) {
712 Use *Current = Next;
713 Next = Current->Next;
714
715 // Turn Current into a single-item list.
716 Current->Next = nullptr;
717
718 // Save Current in the first available slot, merging on collisions.
719 unsigned I;
720 for (I = 0; I < NumSlots; ++I) {
721 if (!Slots[I])
722 break;
723
724 // Merge two lists, doubling the size of Current and emptying slot I.
725 //
726 // Since the uses in Slots[I] originally preceded those in Current, send
727 // Slots[I] in as the left parameter to maintain a stable sort.
728 Current = mergeUseLists(Slots[I], Current, Cmp);
729 Slots[I] = nullptr;
730 }
731 // Check if this is a new slot.
732 if (I == NumSlots) {
733 ++NumSlots;
734 assert(NumSlots <= MaxSlots && "Use list bigger than 2^32");
735 }
736
737 // Found an open slot.
738 Slots[I] = Current;
739 }
740
741 // Merge all the lists together.
742 assert(Next && "Expected one more Use");
743 assert(!Next->Next && "Expected only one Use");
744 UseList = Next;
745 for (unsigned I = 0; I < NumSlots; ++I)
746 if (Slots[I])
747 // Since the uses in Slots[I] originally preceded those in UseList, send
748 // Slots[I] in as the left parameter to maintain a stable sort.
749 UseList = mergeUseLists(Slots[I], UseList, Cmp);
750
751 // Fix the Prev pointers.
752 for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) {
753 I->setPrev(Prev);
754 Prev = &I->Next;
755 }
756}
757
758// isa - Provide some specializations of isa so that we don't have to include
759// the subtype header files to test to see if the value is a subclass...
760//
761template <> struct isa_impl<Constant, Value> {
762 static inline bool doit(const Value &Val) {
763 static_assert(Value::ConstantFirstVal == 0, "Val.getValueID() >= Value::ConstantFirstVal");
764 return Val.getValueID() <= Value::ConstantLastVal;
765 }
766};
767
768template <> struct isa_impl<ConstantData, Value> {
769 static inline bool doit(const Value &Val) {
770 return Val.getValueID() >= Value::ConstantDataFirstVal &&
771 Val.getValueID() <= Value::ConstantDataLastVal;
772 }
773};
774
775template <> struct isa_impl<ConstantAggregate, Value> {
776 static inline bool doit(const Value &Val) {
777 return Val.getValueID() >= Value::ConstantAggregateFirstVal &&
778 Val.getValueID() <= Value::ConstantAggregateLastVal;
779 }
780};
781
782template <> struct isa_impl<Argument, Value> {
783 static inline bool doit (const Value &Val) {
784 return Val.getValueID() == Value::ArgumentVal;
785 }
786};
787
788template <> struct isa_impl<InlineAsm, Value> {
789 static inline bool doit(const Value &Val) {
790 return Val.getValueID() == Value::InlineAsmVal;
791 }
792};
793
794template <> struct isa_impl<Instruction, Value> {
795 static inline bool doit(const Value &Val) {
796 return Val.getValueID() >= Value::InstructionVal;
797 }
798};
799
800template <> struct isa_impl<BasicBlock, Value> {
801 static inline bool doit(const Value &Val) {
802 return Val.getValueID() == Value::BasicBlockVal;
803 }
804};
805
806template <> struct isa_impl<Function, Value> {
807 static inline bool doit(const Value &Val) {
808 return Val.getValueID() == Value::FunctionVal;
809 }
810};
811
812template <> struct isa_impl<GlobalVariable, Value> {
813 static inline bool doit(const Value &Val) {
814 return Val.getValueID() == Value::GlobalVariableVal;
815 }
816};
817
818template <> struct isa_impl<GlobalAlias, Value> {
819 static inline bool doit(const Value &Val) {
820 return Val.getValueID() == Value::GlobalAliasVal;
821 }
822};
823
824template <> struct isa_impl<GlobalIFunc, Value> {
825 static inline bool doit(const Value &Val) {
826 return Val.getValueID() == Value::GlobalIFuncVal;
827 }
828};
829
830template <> struct isa_impl<GlobalIndirectSymbol, Value> {
831 static inline bool doit(const Value &Val) {
832 return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val);
833 }
834};
835
836template <> struct isa_impl<GlobalValue, Value> {
837 static inline bool doit(const Value &Val) {
838 return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val);
839 }
840};
841
842template <> struct isa_impl<GlobalObject, Value> {
843 static inline bool doit(const Value &Val) {
844 return isa<GlobalVariable>(Val) || isa<Function>(Val);
845 }
846};
847
848// Create wrappers for C Binding types (see CBindingWrapping.h).
849DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef)
850
851// Specialized opaque value conversions.
852inline Value **unwrap(LLVMValueRef *Vals) {
853 return reinterpret_cast<Value**>(Vals);
854}
855
856template<typename T>
857inline T **unwrap(LLVMValueRef *Vals, unsigned Length) {
858#ifndef NDEBUG
859 for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I)
860 unwrap<T>(*I); // For side effect of calling assert on invalid usage.
861#endif
862 (void)Length;
863 return reinterpret_cast<T**>(Vals);
864}
865
866inline LLVMValueRef *wrap(const Value **Vals) {
867 return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals));
868}
869
870} // end namespace llvm
871
872#endif // LLVM_IR_VALUE_H