1202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner//===-- llvm/Use.h - Definition of the Use class ----------------*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// 10202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// This defines the Use class. The Use class represents the operand of an 11202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// instruction or some other User instance which refers to a Value. The Use 12202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// class keeps the "use list" of the referenced value up to date. 13202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// 14c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// Pointer tagging is used to efficiently find the User corresponding 15c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// to a Use without having to store a User pointer in every Use. A 16c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// User is preceded in memory by all the Uses corresponding to its 17c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// operands, and the low bits of one of the fields (Prev) of the Use 18c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// class are used to encode offsets to be able to find that User given 19c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// a pointer to any Use. For details, see: 20c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// 21c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// http://www.llvm.org/docs/ProgrammersManual.html#UserLayout 22c26672a2d2b4c0a5be329d95870965d883a2ef34Stefanus Du Toit// 23202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner//===----------------------------------------------------------------------===// 24202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 25674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_IR_USE_H 26674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_IR_USE_H 27202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 28fd095b6389ec7c794e094f2a5dc8851bdc108999Gabor Greif#include "llvm/ADT/PointerIntPair.h" 2940be1e85665d10f5444186f0e7106e368dd735b8Filip Pizlo#include "llvm/Support/CBindingWrapping.h" 30daca73f9bec4ce02045aa5a631a60221c33262cfCraig Topper#include "llvm/Support/Compiler.h" 3140be1e85665d10f5444186f0e7106e368dd735b8Filip Pizlo#include "llvm-c/Core.h" 32ae479aa13ed344876680f7d4dc08e3cf4b512da9Nick Lewycky#include <cstddef> 33f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif#include <iterator> 34d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 37202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattnerclass Value; 38202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattnerclass User; 39e30173ac3396510bd0bb26a66fd615ff9083436dChris Lattnerclass Use; 40afde5188f2a97bd776e1349fe78801d67e187136Jay Foadtemplate<typename> 41afde5188f2a97bd776e1349fe78801d67e187136Jay Foadstruct simplify_type; 42202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 43b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner// Use** is only 4-byte aligned. 44b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattnertemplate<> 45b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattnerclass PointerLikeTypeTraits<Use**> { 46b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattnerpublic: 47b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner static inline void *getAsVoidPointer(Use** P) { return P; } 48b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner static inline Use **getFromVoidPointer(void *P) { 49b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner return static_cast<Use**>(P); 50b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner } 51b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner enum { NumLowBitsAvailable = 2 }; 52b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner}; 53b7a00daa1165576dd2bb9d17970c249d536f4a82Chris Lattner 54efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif//===----------------------------------------------------------------------===// 55202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner// Use Class 56202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner//===----------------------------------------------------------------------===// 57202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 58a870039277d26d3d8f3ff774345db90096b544adChris Lattner/// Use is here to make keeping the "use" list of a Value up-to-date really 59a870039277d26d3d8f3ff774345db90096b544adChris Lattner/// easy. 60202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattnerclass Use { 616f4266506bca785828bacda55bd5db9172f990c6Gabor Greifpublic: 6294fb68ba217975d2d99ae86d15993402158ac655Gabor Greif /// swap - provide a fast substitute to std::swap<Use> 6394fb68ba217975d2d99ae86d15993402158ac655Gabor Greif /// that also works with less standard-compliant compilers 6494fb68ba217975d2d99ae86d15993402158ac655Gabor Greif void swap(Use &RHS); 65b8d5b1211f982d65546d855130d99c42780a76a0Chris Lattner 66691c05bb29d3e2ec9c2ed6b1c082ce5d484b75daJay Foad // A type for the word following an array of hung-off Uses in memory, which is 67691c05bb29d3e2ec9c2ed6b1c082ce5d484b75daJay Foad // a pointer back to their User with the bottom bit set. 68691c05bb29d3e2ec9c2ed6b1c082ce5d484b75daJay Foad typedef PointerIntPair<User*, 1, unsigned> UserRef; 69691c05bb29d3e2ec9c2ed6b1c082ce5d484b75daJay Foad 70efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greifprivate: 71f630e49efc7bf3f1716b6daab3c2cc11a908754aCraig Topper Use(const Use &U) LLVM_DELETED_FUNCTION; 72efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 7394fb68ba217975d2d99ae86d15993402158ac655Gabor Greif /// Destructor - Only for zap() 741ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad ~Use() { 756f4266506bca785828bacda55bd5db9172f990c6Gabor Greif if (Val) removeFromList(); 7659dc98de2f79c027eb6860443daee260710b1405Gabor Greif } 77202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 780d1941a46fecefc1bbb83dc358a7092f49eb1890Jay Foad enum PrevPtrTag { zeroDigitTag 790d1941a46fecefc1bbb83dc358a7092f49eb1890Jay Foad , oneDigitTag 800d1941a46fecefc1bbb83dc358a7092f49eb1890Jay Foad , stopTag 810d1941a46fecefc1bbb83dc358a7092f49eb1890Jay Foad , fullStopTag }; 826f4266506bca785828bacda55bd5db9172f990c6Gabor Greif 831ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad /// Constructor 841ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad Use(PrevPtrTag tag) : Val(0) { 851ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad Prev.setInt(tag); 861ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad } 871ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad 88efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greifpublic: 89a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// Normally Use will just implicitly convert to a Value* that it holds. 906f4266506bca785828bacda55bd5db9172f990c6Gabor Greif operator Value*() const { return Val; } 91a870039277d26d3d8f3ff774345db90096b544adChris Lattner 92a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// If implicit conversion to Value* doesn't work, the get() method returns 93a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// the Value*. 946f4266506bca785828bacda55bd5db9172f990c6Gabor Greif Value *get() const { return Val; } 95a870039277d26d3d8f3ff774345db90096b544adChris Lattner 96a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// getUser - This returns the User that contains this Use. For an 97a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// instruction operand, for example, this will return the instruction. 98efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif User *getUser() const; 99202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 100202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner inline void set(Value *Val); 101202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 102202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner Value *operator=(Value *RHS) { 103202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner set(RHS); 104202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner return RHS; 105202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 106202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner const Use &operator=(const Use &RHS) { 1076f4266506bca785828bacda55bd5db9172f990c6Gabor Greif set(RHS.Val); 108202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner return *this; 109202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 110202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 1116f4266506bca785828bacda55bd5db9172f990c6Gabor Greif Value *operator->() { return Val; } 1126f4266506bca785828bacda55bd5db9172f990c6Gabor Greif const Value *operator->() const { return Val; } 11302accaeb172fbe179fe20eafa6172606d0c9eae1Chris Lattner 1146f4266506bca785828bacda55bd5db9172f990c6Gabor Greif Use *getNext() const { return Next; } 115a870039277d26d3d8f3ff774345db90096b544adChris Lattner 116a870039277d26d3d8f3ff774345db90096b544adChris Lattner 11795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad /// initTags - initialize the waymarking tags on an array of Uses, so that 11895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad /// getUser() can find the User from any of those Uses. 11995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad static Use *initTags(Use *Start, Use *Stop); 12095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 121a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// zap - This is used to destroy Use operands when the number of operands of 122a870039277d26d3d8f3ff774345db90096b544adChris Lattner /// a User changes. 123a870039277d26d3d8f3ff774345db90096b544adChris Lattner static void zap(Use *Start, const Use *Stop, bool del = false); 124a870039277d26d3d8f3ff774345db90096b544adChris Lattner 12502accaeb172fbe179fe20eafa6172606d0c9eae1Chris Lattnerprivate: 126a870039277d26d3d8f3ff774345db90096b544adChris Lattner const Use* getImpliedUser() const; 127a870039277d26d3d8f3ff774345db90096b544adChris Lattner 1286f4266506bca785828bacda55bd5db9172f990c6Gabor Greif Value *Val; 129fd095b6389ec7c794e094f2a5dc8851bdc108999Gabor Greif Use *Next; 13084fb959489a07f032208deb8bf32776867aaeab2Gabor Greif PointerIntPair<Use**, 2, PrevPtrTag> Prev; 131202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 132efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif void setPrev(Use **NewPrev) { 133fd095b6389ec7c794e094f2a5dc8851bdc108999Gabor Greif Prev.setPointer(NewPrev); 134efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif } 135a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner void addToList(Use **List) { 136a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner Next = *List; 1376f4266506bca785828bacda55bd5db9172f990c6Gabor Greif if (Next) Next->setPrev(&Next); 138efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif setPrev(List); 139a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner *List = this; 140a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner } 141a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner void removeFromList() { 142fd095b6389ec7c794e094f2a5dc8851bdc108999Gabor Greif Use **StrippedPrev = Prev.getPointer(); 143efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif *StrippedPrev = Next; 1446f4266506bca785828bacda55bd5db9172f990c6Gabor Greif if (Next) Next->setPrev(StrippedPrev); 145a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner } 146202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 147a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner friend class Value; 148a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner}; 149202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 150a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner// simplify_type - Allow clients to treat uses just like values when using 151a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner// casting operators. 15260e9742e8270c44f5fd83dd269633681bee42cb5Chris Lattnertemplate<> struct simplify_type<Use> { 153202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner typedef Value* SimpleType; 1547fe65d691dcce550d53ec9310913aab67ab6d654Rafael Espindola static SimpleType getSimplifiedValue(Use &Val) { 1557fe65d691dcce550d53ec9310913aab67ab6d654Rafael Espindola return Val.get(); 156202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 157202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner}; 15860e9742e8270c44f5fd83dd269633681bee42cb5Chris Lattnertemplate<> struct simplify_type<const Use> { 1597fe65d691dcce550d53ec9310913aab67ab6d654Rafael Espindola typedef /*const*/ Value* SimpleType; 160202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner static SimpleType getSimplifiedValue(const Use &Val) { 1617fe65d691dcce550d53ec9310913aab67ab6d654Rafael Espindola return Val.get(); 162202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 163202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner}; 164202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 165202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 166202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 167a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattnertemplate<typename UserTy> // UserTy == 'User' or 'const User' 1687362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greifclass value_use_iterator : public std::iterator<std::forward_iterator_tag, 1697362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif UserTy*, ptrdiff_t> { 170f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif typedef std::iterator<std::forward_iterator_tag, UserTy*, ptrdiff_t> super; 171a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner typedef value_use_iterator<UserTy> _Self; 172a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner 173a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner Use *U; 1746f4266506bca785828bacda55bd5db9172f990c6Gabor Greif explicit value_use_iterator(Use *u) : U(u) {} 175a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner friend class Value; 176a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattnerpublic: 177a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner typedef typename super::reference reference; 178a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner typedef typename super::pointer pointer; 179202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 180a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner value_use_iterator() {} 181202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 1829769ab22265b313171d201b5928688524a01bd87Misha Brukman bool operator==(const _Self &x) const { 183a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner return U == x.U; 184202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 185a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner bool operator!=(const _Self &x) const { 186a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner return !operator==(x); 187202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 188f4290266e9e1b7b4d7df9eda39e83ab59cbc372bTorok Edwin 1893ef437d137afe7409b93310a2092a2f8a8dbfccaChris Lattner /// atEnd - return true if this iterator is equal to use_end() on the value. 1906f4266506bca785828bacda55bd5db9172f990c6Gabor Greif bool atEnd() const { return U == 0; } 191202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 192a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner // Iterator traversal: forward iteration only 193a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner _Self &operator++() { // Preincrement 1946f4266506bca785828bacda55bd5db9172f990c6Gabor Greif assert(U && "Cannot increment end iterator!"); 195a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner U = U->getNext(); 1969769ab22265b313171d201b5928688524a01bd87Misha Brukman return *this; 197a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner } 198a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner _Self operator++(int) { // Postincrement 1999769ab22265b313171d201b5928688524a01bd87Misha Brukman _Self tmp = *this; ++*this; return tmp; 200202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner } 201202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 2026f4266506bca785828bacda55bd5db9172f990c6Gabor Greif // Retrieve a pointer to the current User. 2035dc8050ca3797d7001d05ade44bae199bbe324cfChris Lattner UserTy *operator*() const { 2046f4266506bca785828bacda55bd5db9172f990c6Gabor Greif assert(U && "Cannot dereference end iterator!"); 205a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner return U->getUser(); 206a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner } 207202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 208a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner UserTy *operator->() const { return operator*(); } 209202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 210a26619748932b146a09773d51465d7b7dcdb7dd2Chris Lattner Use &getUse() const { return *U; } 21171fe0f4a4325d9e8a1e244b0db43b9731defeeddChris Lattner 212023cfb6871c3a302387ea3e228dc000e45639b5bChris Lattner /// getOperandNo - Return the operand # of this use in its User. Defined in 213023cfb6871c3a302387ea3e228dc000e45639b5bChris Lattner /// User.h 21471fe0f4a4325d9e8a1e244b0db43b9731defeeddChris Lattner /// 215023cfb6871c3a302387ea3e228dc000e45639b5bChris Lattner unsigned getOperandNo() const; 216202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner}; 217202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner 21840be1e85665d10f5444186f0e7106e368dd735b8Filip Pizlo// Create wrappers for C Binding types (see CBindingWrapping.h). 21940be1e85665d10f5444186f0e7106e368dd735b8Filip PizloDEFINE_SIMPLE_CONVERSION_FUNCTIONS(Use, LLVMUseRef) 22040be1e85665d10f5444186f0e7106e368dd735b8Filip Pizlo 221d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 222d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 223202884fd9b575396f7ca220755cc4e3dac9b5a97Chris Lattner#endif 224