Line data Source code
1 : //===- 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 :
26 : namespace llvm {
27 :
28 : class APInt;
29 : class Argument;
30 : class BasicBlock;
31 : class Constant;
32 : class ConstantData;
33 : class ConstantAggregate;
34 : class DataLayout;
35 : class Function;
36 : class GlobalAlias;
37 : class GlobalIFunc;
38 : class GlobalIndirectSymbol;
39 : class GlobalObject;
40 : class GlobalValue;
41 : class GlobalVariable;
42 : class InlineAsm;
43 : class Instruction;
44 : class LLVMContext;
45 : class Module;
46 : class ModuleSlotTracker;
47 : class raw_ostream;
48 : template<typename ValueTy> class StringMapEntry;
49 : class StringRef;
50 : class Twine;
51 : class Type;
52 : class User;
53 :
54 : using ValueName = StringMapEntry<Value *>;
55 :
56 : //===----------------------------------------------------------------------===//
57 : // Value Class
58 : //===----------------------------------------------------------------------===//
59 :
60 : /// 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.
73 : class 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 :
85 : protected:
86 : /// 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 :
93 : private:
94 : /// 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 :
101 : protected:
102 : /// 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 :
123 : private:
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 0 : use_iterator_impl() : U() {}
135 :
136 108255158 : bool operator==(const use_iterator_impl &x) const { return U == x.U; }
137 46067 : 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 242700972 : U = U->getNext();
142 : return *this;
143 : }
144 :
145 0 : use_iterator_impl operator++(int) { // Postincrement
146 0 : auto tmp = *this;
147 : ++*this;
148 0 : return tmp;
149 : }
150 :
151 0 : UseT &operator*() const {
152 : assert(U && "Cannot dereference end iterator!");
153 0 : return *U;
154 : }
155 0 :
156 209140 : UseT *operator->() const { return &operator*(); }
157 0 :
158 : operator use_iterator_impl<const UseT>() const {
159 0 : return use_iterator_impl<const UseT>(U);
160 : }
161 0 : };
162 :
163 : template <typename UserTy> // UserTy == 'User' or 'const User'
164 274006 : 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 113014316 : 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 : /// 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 19067215 : return *this;
182 : }
183 :
184 0 : user_iterator_impl operator++(int) { // Postincrement
185 0 : auto tmp = *this;
186 : ++*this;
187 0 : return tmp;
188 : }
189 :
190 : // Retrieve a pointer to the current User.
191 : UserTy *operator*() const {
192 162733740 : return UI->getUser();
193 0 : }
194 :
195 0 : UserTy *operator->() const { return operator*(); }
196 :
197 : operator user_iterator_impl<const UserTy>() const {
198 : return user_iterator_impl<const UserTy>(*UI);
199 : }
200 14547427 :
201 136 : Use &getUse() const { return *UI; }
202 : };
203 :
204 : protected:
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 :
214 : public:
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 : /// Support for debugging, callable in GDB: V->dump()
222 : void dump() const;
223 :
224 : /// 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 : /// 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 : /// All values are typed, get the type of this value.
245 0 : Type *getType() const { return VTy; }
246 :
247 : /// All values hold a context through their type.
248 : LLVMContext &getContext() const;
249 :
250 : // All values can potentially be named.
251 364869391 : bool hasName() const { return HasName; }
252 : ValueName *getValueName() const;
253 0 : void setValueName(ValueName *VN);
254 :
255 : private:
256 : void destroyValueName();
257 : enum class ReplaceMetadataUses { No, Yes };
258 : void doRAUW(Value *New, ReplaceMetadataUses);
259 13452987 : void setNameImpl(const Twine &Name);
260 :
261 : public:
262 : /// Return a constant reference to the value's name.
263 : ///
264 : /// This guaranteed to return the same reference as long as the value is not
265 : /// modified. If the value has a name, this does a hashtable lookup, so it's
266 : /// not free.
267 : StringRef getName() const;
268 :
269 : /// Change the name of the value.
270 : ///
271 : /// Choose a new unique name if the provided name is taken.
272 : ///
273 : /// \param Name The new name; or "" if the value's name should be removed.
274 : void setName(const Twine &Name);
275 :
276 : /// Transfer the name from V to this value.
277 : ///
278 : /// After taking V's name, sets V's name to empty.
279 : ///
280 : /// \note It is an error to call V->takeName(V).
281 : void takeName(Value *V);
282 :
283 : /// Change all uses of this to point to a new Value.
284 : ///
285 : /// Go through the uses list for this definition and make each use point to
286 : /// "V" instead of "this". After this completes, 'this's use list is
287 : /// guaranteed to be empty.
288 : void replaceAllUsesWith(Value *V);
289 :
290 : /// Change non-metadata uses of this to point to a new Value.
291 : ///
292 : /// Go through the uses list for this definition and make each use point to
293 : /// "V" instead of "this". This function skips metadata entries in the list.
294 : void replaceNonMetadataUsesWith(Value *V);
295 :
296 : /// replaceUsesOutsideBlock - Go through the uses list for this definition and
297 : /// make each use point to "V" instead of "this" when the use is outside the
298 : /// block. 'This's use list is expected to have at least one element.
299 : /// Unlike replaceAllUsesWith this function does not support basic block
300 : /// values or constant users.
301 : void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
302 :
303 : //----------------------------------------------------------------------
304 : // Methods for handling the chain of uses of this Value.
305 : //
306 : // Materializing a function can introduce new uses, so these methods come in
307 : // two variants:
308 : // The methods that start with materialized_ check the uses that are
309 : // currently known given which functions are materialized. Be very careful
310 : // when using them since you might not get all uses.
311 : // The methods that don't start with materialized_ assert that modules is
312 : // fully materialized.
313 : void assertModuleIsMaterializedImpl() const;
314 : // This indirection exists so we can keep assertModuleIsMaterializedImpl()
315 : // around in release builds of Value.cpp to be linked with other code built
316 : // in debug mode. But this avoids calling it in any of the release built code.
317 0 : void assertModuleIsMaterialized() const {
318 : #ifndef NDEBUG
319 : assertModuleIsMaterializedImpl();
320 : #endif
321 0 : }
322 :
323 0 : bool use_empty() const {
324 : assertModuleIsMaterialized();
325 578802 : return UseList == nullptr;
326 : }
327 :
328 0 : bool materialized_use_empty() const {
329 0 : return UseList == nullptr;
330 : }
331 0 :
332 : using use_iterator = use_iterator_impl<Use>;
333 0 : using const_use_iterator = use_iterator_impl<const Use>;
334 :
335 0 : use_iterator materialized_use_begin() { return use_iterator(UseList); }
336 0 : const_use_iterator materialized_use_begin() const {
337 0 : return const_use_iterator(UseList);
338 : }
339 : use_iterator use_begin() {
340 : assertModuleIsMaterialized();
341 188739 : return materialized_use_begin();
342 : }
343 0 : const_use_iterator use_begin() const {
344 0 : assertModuleIsMaterialized();
345 110505823 : return materialized_use_begin();
346 : }
347 0 : use_iterator use_end() { return use_iterator(); }
348 0 : const_use_iterator use_end() const { return const_use_iterator(); }
349 610 : iterator_range<use_iterator> materialized_uses() {
350 8150898 : return make_range(materialized_use_begin(), use_end());
351 : }
352 : iterator_range<const_use_iterator> materialized_uses() const {
353 7421855 : return make_range(materialized_use_begin(), use_end());
354 : }
355 0 : iterator_range<use_iterator> uses() {
356 0 : assertModuleIsMaterialized();
357 : return materialized_uses();
358 1874 : }
359 : iterator_range<const_use_iterator> uses() const {
360 : assertModuleIsMaterialized();
361 1755293 : return materialized_uses();
362 : }
363 :
364 0 : bool user_empty() const {
365 : assertModuleIsMaterialized();
366 1 : return UseList == nullptr;
367 : }
368 :
369 : using user_iterator = user_iterator_impl<User>;
370 : using const_user_iterator = user_iterator_impl<const User>;
371 :
372 0 : user_iterator materialized_user_begin() { return user_iterator(UseList); }
373 0 : const_user_iterator materialized_user_begin() const {
374 0 : return const_user_iterator(UseList);
375 : }
376 : user_iterator user_begin() {
377 : assertModuleIsMaterialized();
378 10437427 : return materialized_user_begin();
379 : }
380 0 : const_user_iterator user_begin() const {
381 0 : assertModuleIsMaterialized();
382 31535611 : return materialized_user_begin();
383 : }
384 0 : user_iterator user_end() { return user_iterator(); }
385 0 : const_user_iterator user_end() const { return const_user_iterator(); }
386 6975694 : User *user_back() {
387 : assertModuleIsMaterialized();
388 0 : return *materialized_user_begin();
389 : }
390 174385 : const User *user_back() const {
391 : assertModuleIsMaterialized();
392 0 : return *materialized_user_begin();
393 0 : }
394 : iterator_range<user_iterator> materialized_users() {
395 15988857 : return make_range(materialized_user_begin(), user_end());
396 : }
397 : iterator_range<const_user_iterator> materialized_users() const {
398 40268512 : return make_range(materialized_user_begin(), user_end());
399 : }
400 : iterator_range<user_iterator> users() {
401 : assertModuleIsMaterialized();
402 : return materialized_users();
403 21175 : }
404 : iterator_range<const_user_iterator> users() const {
405 : assertModuleIsMaterialized();
406 2988278 : return materialized_users();
407 : }
408 :
409 : /// Return true if there is exactly one user of this value.
410 : ///
411 : /// This is specialized because it is a common request and does not require
412 : /// traversing the whole use list.
413 : bool hasOneUse() const {
414 : const_use_iterator I = use_begin(), E = use_end();
415 111602592 : if (I == E) return false;
416 : return ++I == E;
417 : }
418 :
419 : /// Return true if this Value has exactly N users.
420 : bool hasNUses(unsigned N) const;
421 :
422 : /// Return true if this value has N users or more.
423 7358144 : ///
424 : /// This is logically equivalent to getNumUses() >= N.
425 : bool hasNUsesOrMore(unsigned N) const;
426 :
427 : /// Check if this value is used in the specified basic block.
428 : bool isUsedInBasicBlock(const BasicBlock *BB) const;
429 :
430 : /// This method computes the number of uses of this Value.
431 : ///
432 : /// This is a linear time operation. Use hasOneUse, hasNUses, or
433 : /// hasNUsesOrMore to check for specific values.
434 : unsigned getNumUses() const;
435 :
436 : /// This method should only be used by the Use class.
437 184567496 : void addUse(Use &U) { U.addToList(&UseList); }
438 :
439 : /// Concrete subclass of this.
440 : ///
441 : /// An enumeration for keeping track of the concrete subclass of Value that
442 : /// is actually instantiated. Values of this enumeration are kept in the
443 : /// Value classes SubclassID field. They are used for concrete type
444 : /// identification.
445 533822 : enum ValueTy {
446 : #define HANDLE_VALUE(Name) Name##Val,
447 : #include "llvm/IR/Value.def"
448 :
449 : // Markers:
450 : #define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val,
451 : #include "llvm/IR/Value.def"
452 : };
453 :
454 : /// Return an ID for the concrete type of this object.
455 : ///
456 : /// This is used to implement the classof checks. This should not be used
457 : /// for any other purpose, as the values may change as LLVM evolves. Also,
458 : /// note that for instructions, the Instruction's opcode is added to
459 : /// InstructionVal. So this means three things:
460 : /// # there is no value with code InstructionVal (no opcode==0).
461 : /// # there are more possible values for the value type than in ValueTy enum.
462 : /// # the InstructionVal enumerator must be the highest valued enumerator in
463 : /// the ValueTy enum.
464 0 : unsigned getValueID() const {
465 1499373315 : return SubclassID;
466 : }
467 :
468 : /// Return the raw optional flags value contained in this value.
469 : ///
470 : /// This should only be used when testing two Values for equivalence.
471 : unsigned getRawSubclassOptionalData() const {
472 30354194 : return SubclassOptionalData;
473 209548144 : }
474 :
475 : /// Clear the optional flags contained in this value.
476 : void clearSubclassOptionalData() {
477 17741 : SubclassOptionalData = 0;
478 : }
479 :
480 : /// Check the optional flags for equality.
481 : bool hasSameSubclassOptionalData(const Value *V) const {
482 : return SubclassOptionalData == V->SubclassOptionalData;
483 : }
484 :
485 : /// Return true if there is a value handle associated with this value.
486 53501 : bool hasValueHandle() const { return HasValueHandle; }
487 :
488 : /// Return true if there is metadata referencing this value.
489 56020526 : bool isUsedByMetadata() const { return IsUsedByMD; }
490 :
491 : /// Return true if this value is a swifterror value.
492 : ///
493 : /// swifterror values can be either a function argument or an alloca with a
494 : /// swifterror attribute.
495 : bool isSwiftError() const;
496 :
497 636 : /// Strip off pointer casts, all-zero GEPs, and aliases.
498 : ///
499 : /// Returns the original uncasted value. If this is called on a non-pointer
500 : /// value, it returns 'this'.
501 : const Value *stripPointerCasts() const;
502 : Value *stripPointerCasts() {
503 : return const_cast<Value *>(
504 46305256 : static_cast<const Value *>(this)->stripPointerCasts());
505 : }
506 :
507 : /// Strip off pointer casts, all-zero GEPs, aliases and invariant group
508 : /// info.
509 : ///
510 : /// Returns the original uncasted value. If this is called on a non-pointer
511 : /// value, it returns 'this'. This function should be used only in
512 24976 : /// Alias analysis.
513 : const Value *stripPointerCastsAndInvariantGroups() const;
514 : Value *stripPointerCastsAndInvariantGroups() {
515 : return const_cast<Value *>(
516 0 : static_cast<const Value *>(this)->stripPointerCastsAndInvariantGroups());
517 : }
518 :
519 : /// Strip off pointer casts and all-zero GEPs.
520 : ///
521 : /// Returns the original uncasted value. If this is called on a non-pointer
522 : /// value, it returns 'this'.
523 : const Value *stripPointerCastsNoFollowAliases() const;
524 : Value *stripPointerCastsNoFollowAliases() {
525 : return const_cast<Value *>(
526 11228 : static_cast<const Value *>(this)->stripPointerCastsNoFollowAliases());
527 : }
528 :
529 : /// Strip off pointer casts and all-constant inbounds GEPs.
530 : ///
531 : /// Returns the original pointer value. If this is called on a non-pointer
532 : /// value, it returns 'this'.
533 : const Value *stripInBoundsConstantOffsets() const;
534 : Value *stripInBoundsConstantOffsets() {
535 : return const_cast<Value *>(
536 105 : static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
537 : }
538 :
539 : /// Accumulate offsets from \a stripInBoundsConstantOffsets().
540 : ///
541 : /// Stores the resulting constant offset stripped into the APInt provided.
542 : /// The provided APInt will be extended or truncated as needed to be the
543 : /// correct bitwidth for an offset of this pointer type.
544 : ///
545 : /// If this is called on a non-pointer value, it returns 'this'.
546 : const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
547 : APInt &Offset) const;
548 : Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
549 : APInt &Offset) {
550 : return const_cast<Value *>(static_cast<const Value *>(this)
551 604900 : ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset));
552 : }
553 :
554 : /// Strip off pointer casts and inbounds GEPs.
555 : ///
556 : /// Returns the original pointer value. If this is called on a non-pointer
557 : /// value, it returns 'this'.
558 : const Value *stripInBoundsOffsets() const;
559 : Value *stripInBoundsOffsets() {
560 : return const_cast<Value *>(
561 96717 : static_cast<const Value *>(this)->stripInBoundsOffsets());
562 : }
563 :
564 : /// Returns the number of bytes known to be dereferenceable for the
565 : /// pointer value.
566 : ///
567 : /// If CanBeNull is set by this function the pointer can either be null or be
568 : /// dereferenceable up to the returned number of bytes.
569 : uint64_t getPointerDereferenceableBytes(const DataLayout &DL,
570 : bool &CanBeNull) const;
571 :
572 : /// Returns an alignment of the pointer value.
573 : ///
574 : /// Returns an alignment which is either specified explicitly, e.g. via
575 : /// align attribute of a function argument, or guaranteed by DataLayout.
576 : unsigned getPointerAlignment(const DataLayout &DL) const;
577 :
578 : /// Translate PHI node to its predecessor from the given basic block.
579 : ///
580 : /// If this value is a PHI node with CurBB as its parent, return the value in
581 : /// the PHI node corresponding to PredBB. If not, return ourself. This is
582 : /// useful if you want to know the value something has in a predecessor
583 : /// block.
584 : const Value *DoPHITranslation(const BasicBlock *CurBB,
585 : const BasicBlock *PredBB) const;
586 : Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) {
587 : return const_cast<Value *>(
588 21127 : static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB));
589 : }
590 :
591 : /// The maximum alignment for instructions.
592 : ///
593 : /// This is the greatest alignment value supported by load, store, and alloca
594 : /// instructions, and global values.
595 : static const unsigned MaxAlignmentExponent = 29;
596 : static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent;
597 :
598 : /// Mutate the type of this Value to be of the specified type.
599 : ///
600 : /// Note that this is an extremely dangerous operation which can create
601 : /// completely invalid IR very easily. It is strongly recommended that you
602 : /// recreate IR objects with the right types instead of mutating them in
603 : /// place.
604 0 : void mutateType(Type *Ty) {
605 5420 : VTy = Ty;
606 0 : }
607 :
608 : /// Sort the use-list.
609 : ///
610 : /// Sorts the Value's use-list by Cmp using a stable mergesort. Cmp is
611 : /// expected to compare two \a Use references.
612 : template <class Compare> void sortUseList(Compare Cmp);
613 :
614 : /// Reverse the use-list.
615 : void reverseUseList();
616 :
617 : private:
618 : /// Merge two lists together.
619 : ///
620 : /// Merges \c L and \c R using \c Cmp. To enable stable sorts, always pushes
621 : /// "equal" items from L before items from R.
622 : ///
623 : /// \return the first element in the list.
624 : ///
625 : /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update).
626 : template <class Compare>
627 10115 : static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
628 : Use *Merged;
629 : Use **Next = &Merged;
630 :
631 : while (true) {
632 49280 : if (!L) {
633 5357 : *Next = R;
634 5357 : break;
635 873 : }
636 43923 : if (!R) {
637 4758 : *Next = L;
638 4758 : break;
639 : }
640 41770 : if (Cmp(*R, *L)) {
641 12098 : *Next = R;
642 12098 : Next = &R->Next;
643 11769 : R = R->Next;
644 2276 : } else {
645 27940 : *Next = L;
646 27940 : Next = &L->Next;
647 27396 : L = L->Next;
648 1732 : }
649 850 : }
650 850 :
651 10965 : return Merged;
652 : }
653 882 :
654 882 : protected:
655 882 : unsigned short getSubclassDataFromValue() const { return SubclassData; }
656 45115123 : void setValueSubclassData(unsigned short D) { SubclassData = D; }
657 : };
658 0 :
659 655996 : struct ValueDeleter { void operator()(Value *V) { V->deleteValue(); } };
660 0 :
661 : /// Use this instead of std::unique_ptr<Value> or std::unique_ptr<Instruction>.
662 0 : /// Those don't work because Value and Instruction's destructors are protected,
663 0 : /// aren't virtual, and won't destroy the complete object.
664 2511253 : using unique_value = std::unique_ptr<Value, ValueDeleter>;
665 :
666 0 : inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
667 34817 : V.print(OS);
668 0 : return OS;
669 0 : }
670 :
671 186678682 : void Use::set(Value *V) {
672 260659788 : if (Val) removeFromList();
673 224467182 : Val = V;
674 186678682 : if (V) V->addUse(*this);
675 186678682 : }
676 :
677 0 : Value *Use::operator=(Value *RHS) {
678 141094112 : set(RHS);
679 550372 : return RHS;
680 770536 : }
681 237193 :
682 550372 : const Use &Use::operator=(const Use &RHS) {
683 23723630 : set(RHS.Val);
684 0 : return *this;
685 0 : }
686 23283 :
687 2096 : template <class Compare> void Value::sortUseList(Compare Cmp) {
688 2096 : if (!UseList || !UseList->Next)
689 0 : // No need to sort 0 or 1 uses.
690 0 : return;
691 :
692 0 : // Note: this function completely ignores Prev pointers until the end when
693 0 : // they're fixed en masse.
694 0 :
695 376 : // Create a binomial vector of sorted lists, visiting uses one at a time and
696 376 : // merging lists as necessary.
697 0 : const unsigned MaxSlots = 32;
698 0 : Use *Slots[MaxSlots];
699 0 :
700 : // Collect the first use, turning it into a single-item list.
701 : Use *Next = UseList->Next;
702 2096 : UseList->Next = nullptr;
703 0 : unsigned NumSlots = 1;
704 2096 : Slots[0] = UseList;
705 0 :
706 : // Collect all but the last use.
707 10115 : while (Next->Next) {
708 : Use *Current = Next;
709 : Next = Current->Next;
710 376 :
711 0 : // Turn Current into a single-item list.
712 8395 : Current->Next = nullptr;
713 :
714 0 : // Save Current in the first available slot, merging on collisions.
715 873 : unsigned I;
716 15375 : for (I = 0; I < NumSlots; ++I) {
717 13726 : if (!Slots[I])
718 0 : break;
719 0 :
720 497 : // Merge two lists, doubling the size of Current and emptying slot I.
721 0 : //
722 : // Since the uses in Slots[I] originally preceded those in Current, send
723 0 : // Slots[I] in as the left parameter to maintain a stable sort.
724 8262 : Current = mergeUseLists(Slots[I], Current, Cmp);
725 8054 : Slots[I] = nullptr;
726 : }
727 : // Check if this is a new slot.
728 8019 : if (I == NumSlots) {
729 1649 : ++NumSlots;
730 : assert(NumSlots <= MaxSlots && "Use list bigger than 2^32");
731 : }
732 409 :
733 409 : // Found an open slot.
734 8019 : Slots[I] = Current;
735 : }
736 497 :
737 208 : // Merge all the lists together.
738 : assert(Next && "Expected one more Use");
739 : assert(!Next->Next && "Expected only one Use");
740 2096 : UseList = Next;
741 5841 : for (unsigned I = 0; I < NumSlots; ++I)
742 4242 : if (Slots[I])
743 : // Since the uses in Slots[I] originally preceded those in UseList, send
744 : // Slots[I] in as the left parameter to maintain a stable sort.
745 2759 : UseList = mergeUseLists(Slots[I], UseList, Cmp);
746 :
747 : // Fix the Prev pointers.
748 14683 : for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) {
749 960 : I->setPrev(Prev);
750 12795 : Prev = &I->Next;
751 : }
752 : }
753 464 :
754 : // isa - Provide some specializations of isa so that we don't have to include
755 : // the subtype header files to test to see if the value is a subclass...
756 1625 : //
757 : template <> struct isa_impl<Constant, Value> {
758 1249 : static inline bool doit(const Value &Val) {
759 : static_assert(Value::ConstantFirstVal == 0, "Val.getValueID() >= Value::ConstantFirstVal");
760 154398524 : return Val.getValueID() <= Value::ConstantLastVal;
761 : }
762 : };
763 :
764 : template <> struct isa_impl<ConstantData, Value> {
765 0 : static inline bool doit(const Value &Val) {
766 96 : return Val.getValueID() >= Value::ConstantDataFirstVal &&
767 : Val.getValueID() <= Value::ConstantDataLastVal;
768 18933184 : }
769 : };
770 :
771 : template <> struct isa_impl<ConstantAggregate, Value> {
772 : static inline bool doit(const Value &Val) {
773 0 : return Val.getValueID() >= Value::ConstantAggregateFirstVal &&
774 : Val.getValueID() <= Value::ConstantAggregateLastVal;
775 : }
776 : };
777 :
778 : template <> struct isa_impl<Argument, Value> {
779 : static inline bool doit (const Value &Val) {
780 68463364 : return Val.getValueID() == Value::ArgumentVal;
781 : }
782 0 : };
783 :
784 : template <> struct isa_impl<InlineAsm, Value> {
785 0 : static inline bool doit(const Value &Val) {
786 10377409 : return Val.getValueID() == Value::InlineAsmVal;
787 : }
788 306425 : };
789 :
790 0 : template <> struct isa_impl<Instruction, Value> {
791 : static inline bool doit(const Value &Val) {
792 1748146182 : return Val.getValueID() >= Value::InstructionVal;
793 : }
794 0 : };
795 0 :
796 : template <> struct isa_impl<BasicBlock, Value> {
797 : static inline bool doit(const Value &Val) {
798 15604249 : return Val.getValueID() == Value::BasicBlockVal;
799 : }
800 520528677 : };
801 :
802 0 : template <> struct isa_impl<Function, Value> {
803 0 : static inline bool doit(const Value &Val) {
804 560238427 : return Val.getValueID() == Value::FunctionVal;
805 : }
806 1379 : };
807 0 :
808 : template <> struct isa_impl<GlobalVariable, Value> {
809 : static inline bool doit(const Value &Val) {
810 131630216 : return Val.getValueID() == Value::GlobalVariableVal;
811 : }
812 15870263 : };
813 :
814 : template <> struct isa_impl<GlobalAlias, Value> {
815 : static inline bool doit(const Value &Val) {
816 3718 : return Val.getValueID() == Value::GlobalAliasVal;
817 : }
818 1786582 : };
819 0 :
820 0 : template <> struct isa_impl<GlobalIFunc, Value> {
821 : static inline bool doit(const Value &Val) {
822 0 : return Val.getValueID() == Value::GlobalIFuncVal;
823 0 : }
824 0 : };
825 :
826 0 : template <> struct isa_impl<GlobalIndirectSymbol, Value> {
827 : static inline bool doit(const Value &Val) {
828 115103598 : return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val);
829 : }
830 0 : };
831 :
832 : template <> struct isa_impl<GlobalValue, Value> {
833 : static inline bool doit(const Value &Val) {
834 : return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val);
835 : }
836 4381389 : };
837 :
838 : template <> struct isa_impl<GlobalObject, Value> {
839 : static inline bool doit(const Value &Val) {
840 242819868 : return isa<GlobalVariable>(Val) || isa<Function>(Val);
841 : }
842 : };
843 :
844 : // Create wrappers for C Binding types (see CBindingWrapping.h).
845 : DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef)
846 :
847 : // Specialized opaque value conversions.
848 5295497 : inline Value **unwrap(LLVMValueRef *Vals) {
849 : return reinterpret_cast<Value**>(Vals);
850 : }
851 :
852 : template<typename T>
853 0 : inline T **unwrap(LLVMValueRef *Vals, unsigned Length) {
854 : #ifndef NDEBUG
855 : for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I)
856 : unwrap<T>(*I); // For side effect of calling assert on invalid usage.
857 : #endif
858 : (void)Length;
859 0 : return reinterpret_cast<T**>(Vals);
860 : }
861 :
862 : inline LLVMValueRef *wrap(const Value **Vals) {
863 : return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals));
864 : }
865 :
866 : } // end namespace llvm
867 :
868 : #endif // LLVM_IR_VALUE_H
|
