1b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif//===-- Use.cpp - Implement the Use class ---------------------------------===// 2efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// 3efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// The LLVM Compiler Infrastructure 4efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// 5efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// This file is distributed under the University of Illinois Open Source 6efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// License. See LICENSE.TXT for details. 7efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif// 8efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif//===----------------------------------------------------------------------===// 9efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Use.h" 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/User.h" 120b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Value.h" 135dc805566712d9627068647dba3bcd5980911b6cDouglas Gregor#include <new> 14efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 15efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greifnamespace llvm { 16efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 1794fb68ba217975d2d99ae86d15993402158ac655Gabor Greifvoid Use::swap(Use &RHS) { 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Val == RHS.Val) 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Val) 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines removeFromList(); 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *OldVal = Val; 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RHS.Val) { 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.removeFromList(); 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Val = RHS.Val; 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Val->addUse(*this); 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Val = nullptr; 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 3294fb68ba217975d2d99ae86d15993402158ac655Gabor Greif 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (OldVal) { 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.Val = OldVal; 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RHS.Val->addUse(RHS); 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.Val = nullptr; 3894fb68ba217975d2d99ae86d15993402158ac655Gabor Greif } 3994fb68ba217975d2d99ae86d15993402158ac655Gabor Greif} 4094fb68ba217975d2d99ae86d15993402158ac655Gabor Greif 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesUser *Use::getUser() const { 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Use *End = getImpliedUser(); 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const UserRef *ref = reinterpret_cast<const UserRef *>(End); 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return ref->getInt() ? ref->getPointer() 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : reinterpret_cast<User *>(const_cast<Use *>(End)); 46efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif} 47efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned Use::getOperandNo() const { 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return this - getUser()->op_begin(); 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 51efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// Sets up the waymarking algorithm's tags for a series of Uses. See the 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// algorithm details here: 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesUse *Use::initTags(Use *const Start, Use *Stop) { 581ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad ptrdiff_t Done = 0; 59b68f7aea33fd8510e441a1a9a38f3920a9e5db0cGabor Greif while (Done < 20) { 60345ce549a9f79cb4c8f513564bb710a61cc8483fGabor Greif if (Start == Stop--) 61345ce549a9f79cb4c8f513564bb710a61cc8483fGabor Greif return Start; 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static const PrevPtrTag tags[20] = { 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines fullStopTag, oneDigitTag, stopTag, oneDigitTag, oneDigitTag, 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines stopTag, zeroDigitTag, oneDigitTag, oneDigitTag, stopTag, 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines zeroDigitTag, oneDigitTag, zeroDigitTag, oneDigitTag, stopTag, 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines oneDigitTag, oneDigitTag, oneDigitTag, oneDigitTag, stopTag}; 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines new (Stop) Use(tags[Done++]); 68345ce549a9f79cb4c8f513564bb710a61cc8483fGabor Greif } 69345ce549a9f79cb4c8f513564bb710a61cc8483fGabor Greif 70efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif ptrdiff_t Count = Done; 71efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif while (Start != Stop) { 72efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif --Stop; 73efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif if (!Count) { 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines new (Stop) Use(stopTag); 75efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif ++Done; 76efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif Count = Done; 77efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif } else { 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines new (Stop) Use(PrevPtrTag(Count & 1)); 79efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif Count >>= 1; 80efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif ++Done; 81efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif } 82efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif } 83efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 84efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif return Start; 85efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif} 86efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 87efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greifvoid Use::zap(Use *Start, const Use *Stop, bool del) { 881ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad while (Start != Stop) 891ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad (--Stop)->~Use(); 901ed26acc58a13f125bc9e1d5e5aa22fd479654ffJay Foad if (del) 91efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif ::operator delete(Start); 92efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif} 93efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesconst Use *Use::getImpliedUser() const { 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Use *Current = this; 96efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (true) { 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Tag = (Current++)->Prev.getInt(); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines switch (Tag) { 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case zeroDigitTag: 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case oneDigitTag: 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case stopTag: { 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++Current; 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ptrdiff_t Offset = 1; 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (true) { 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Tag = Current->Prev.getInt(); 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines switch (Tag) { 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case zeroDigitTag: 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case oneDigitTag: 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++Current; 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Offset = (Offset << 1) + Tag; 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines default: 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Current + Offset; 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case fullStopTag: 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Current; 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 125efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif} 126efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif 127efe65369a74871c3140a540a6c95ce5d1f080954Gabor Greif} // End llvm namespace 128