1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- Use.cpp - Implement the Use class ---------------------------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the algorithm for finding the User of a Use. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Value.h" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Use swap Implementation 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Use::swap(Use &RHS) { 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V1(Val); 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V2(RHS.Val); 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1 != V2) { 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1) { 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman removeFromList(); 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V2) { 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS.removeFromList(); 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Val = V2; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V2->addUse(*this); 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Val = 0; 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1) { 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS.Val = V1; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V1->addUse(RHS); 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RHS.Val = 0; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Use getImpliedUser Implementation 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanconst Use *Use::getImpliedUser() const { 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Use *Current = this; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (true) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Tag = (Current++)->Prev.getInt(); 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Tag) { 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case zeroDigitTag: 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case oneDigitTag: 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case stopTag: { 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Current; 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ptrdiff_t Offset = 1; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (true) { 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Tag = Current->Prev.getInt(); 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Tag) { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case zeroDigitTag: 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case oneDigitTag: 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Current; 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Offset = (Offset << 1) + Tag; 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Current + Offset; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case fullStopTag: 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Current; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Use initTags Implementation 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanUse *Use::initTags(Use * const Start, Use *Stop) { 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ptrdiff_t Done = 0; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Done < 20) { 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Start == Stop--) 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Start; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static const PrevPtrTag tags[20] = { fullStopTag, oneDigitTag, stopTag, 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman oneDigitTag, oneDigitTag, stopTag, 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman zeroDigitTag, oneDigitTag, oneDigitTag, 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman stopTag, zeroDigitTag, oneDigitTag, 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman zeroDigitTag, oneDigitTag, stopTag, 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman oneDigitTag, oneDigitTag, oneDigitTag, 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman oneDigitTag, stopTag 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(Stop) Use(tags[Done++]); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ptrdiff_t Count = Done; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Start != Stop) { 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --Stop; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Count) { 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(Stop) Use(stopTag); 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Done; 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Count = Done; 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(Stop) Use(PrevPtrTag(Count & 1)); 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Count >>= 1; 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Done; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Start; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Use zap Implementation 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid Use::zap(Use *Start, const Use *Stop, bool del) { 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (Start != Stop) 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (--Stop)->~Use(); 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (del) 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ::operator delete(Start); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Use getUser Implementation 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanUser *Use::getUser() const { 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Use *End = getImpliedUser(); 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const UserRef *ref = reinterpret_cast<const UserRef*>(End); 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ref->getInt() 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ? ref->getPointer() 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : (User*)End; 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End llvm namespace 145