LLVM API Documentation

Use.cpp

Go to the documentation of this file.
00001 //===-- Use.cpp - Implement the Use class ---------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the algorithm for finding the User of a Use.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/User.h"
00015 
00016 namespace llvm {
00017 
00018 //===----------------------------------------------------------------------===//
00019 //                         Use swap Implementation
00020 //===----------------------------------------------------------------------===//
00021 
00022 void Use::swap(Use &RHS) {
00023   Value *V1(Val);
00024   Value *V2(RHS.Val);
00025   if (V1 != V2) {
00026     if (V1) {
00027       removeFromList();
00028     }
00029 
00030     if (V2) {
00031       RHS.removeFromList();
00032       Val = V2;
00033       V2->addUse(*this);
00034     } else {
00035       Val = 0;
00036     }
00037 
00038     if (V1) {
00039       RHS.Val = V1;
00040       V1->addUse(RHS);
00041     } else {
00042       RHS.Val = 0;
00043     }
00044   }
00045 }
00046 
00047 //===----------------------------------------------------------------------===//
00048 //                         Use getImpliedUser Implementation
00049 //===----------------------------------------------------------------------===//
00050 
00051 const Use *Use::getImpliedUser() const {
00052   const Use *Current = this;
00053 
00054   while (true) {
00055     unsigned Tag = (Current++)->Prev.getInt();
00056     switch (Tag) {
00057       case zeroDigitTag:
00058       case oneDigitTag:
00059         continue;
00060 
00061       case stopTag: {
00062         ++Current;
00063         ptrdiff_t Offset = 1;
00064         while (true) {
00065           unsigned Tag = Current->Prev.getInt();
00066           switch (Tag) {
00067             case zeroDigitTag:
00068             case oneDigitTag:
00069               ++Current;
00070               Offset = (Offset << 1) + Tag;
00071               continue;
00072             default:
00073               return Current + Offset;
00074           }
00075         }
00076       }
00077 
00078       case fullStopTag:
00079         return Current;
00080     }
00081   }
00082 }
00083 
00084 //===----------------------------------------------------------------------===//
00085 //                         Use initTags Implementation
00086 //===----------------------------------------------------------------------===//
00087 
00088 Use *Use::initTags(Use * const Start, Use *Stop, ptrdiff_t Done) {
00089   ptrdiff_t Count = Done;
00090   while (Start != Stop) {
00091     --Stop;
00092     Stop->Val = 0;
00093     if (!Count) {
00094       Stop->Prev.setFromOpaqueValue(reinterpret_cast<Use**>(Done == 0
00095                                                             ? fullStopTag
00096                                                             : stopTag));
00097       ++Done;
00098       Count = Done;
00099     } else {
00100       Stop->Prev.setFromOpaqueValue(reinterpret_cast<Use**>(Count & 1));
00101       Count >>= 1;
00102       ++Done;
00103     }
00104   }
00105 
00106   return Start;
00107 }
00108 
00109 //===----------------------------------------------------------------------===//
00110 //                         Use zap Implementation
00111 //===----------------------------------------------------------------------===//
00112 
00113 void Use::zap(Use *Start, const Use *Stop, bool del) {
00114   if (del) {
00115     while (Start != Stop) {
00116       (--Stop)->~Use();
00117     }
00118     ::operator delete(Start);
00119     return;
00120   }
00121 
00122   while (Start != Stop) {
00123     (Start++)->set(0);
00124   }
00125 }
00126 
00127 //===----------------------------------------------------------------------===//
00128 //                         AugmentedUse layout struct
00129 //===----------------------------------------------------------------------===//
00130 
00131 struct AugmentedUse : Use {
00132   PointerIntPair<User*, 1, Tag> ref;
00133   AugmentedUse(); // not implemented
00134 };
00135 
00136 
00137 //===----------------------------------------------------------------------===//
00138 //                         Use getUser Implementation
00139 //===----------------------------------------------------------------------===//
00140 
00141 User *Use::getUser() const {
00142   const Use *End = getImpliedUser();
00143   const PointerIntPair<User*, 1, Tag>& ref(
00144                                 static_cast<const AugmentedUse*>(End - 1)->ref);
00145   User *She = ref.getPointer();
00146   return ref.getInt()
00147     ? She
00148     : (User*)End;
00149 }
00150 
00151 //===----------------------------------------------------------------------===//
00152 //                         User allocHungoffUses Implementation
00153 //===----------------------------------------------------------------------===//
00154 
00155 Use *User::allocHungoffUses(unsigned N) const {
00156   Use *Begin = static_cast<Use*>(::operator new(sizeof(Use) * N
00157                                                 + sizeof(AugmentedUse)
00158                                                 - sizeof(Use)));
00159   Use *End = Begin + N;
00160   PointerIntPair<User*, 1, Tag>& ref(static_cast<AugmentedUse&>(End[-1]).ref);
00161   ref.setPointer(const_cast<User*>(this));
00162   ref.setInt(tagOne);
00163   return Use::initTags(Begin, End);
00164 }
00165 
00166 //===----------------------------------------------------------------------===//
00167 //                         User operator new Implementations
00168 //===----------------------------------------------------------------------===//
00169 
00170 void *User::operator new(size_t s, unsigned Us) {
00171   void *Storage = ::operator new(s + sizeof(Use) * Us);
00172   Use *Start = static_cast<Use*>(Storage);
00173   Use *End = Start + Us;
00174   User *Obj = reinterpret_cast<User*>(End);
00175   Obj->OperandList = Start;
00176   Obj->NumOperands = Us;
00177   Use::initTags(Start, End);
00178   return Obj;
00179 }
00180 
00181 /// Prefixed allocation - just before the first Use, allocate a NULL pointer.
00182 /// The destructor can detect its presence and readjust the OperandList
00183 /// for deletition.
00184 ///
00185 void *User::operator new(size_t s, unsigned Us, bool Prefix) {
00186   // currently prefixed allocation only admissible for
00187   // unconditional branch instructions
00188   if (!Prefix)
00189     return operator new(s, Us);
00190 
00191   assert(Us == 1 && "Other than one Use allocated?");
00192   typedef PointerIntPair<void*, 2, Use::PrevPtrTag> TaggedPrefix;
00193   void *Raw = ::operator new(s + sizeof(TaggedPrefix) + sizeof(Use) * Us);
00194   TaggedPrefix *Pre = static_cast<TaggedPrefix*>(Raw);
00195   Pre->setFromOpaqueValue(0);
00196   void *Storage = Pre + 1; // skip over prefix
00197   Use *Start = static_cast<Use*>(Storage);
00198   Use *End = Start + Us;
00199   User *Obj = reinterpret_cast<User*>(End);
00200   Obj->OperandList = Start;
00201   Obj->NumOperands = Us;
00202   Use::initTags(Start, End);
00203   return Obj;
00204 }
00205 
00206 //===----------------------------------------------------------------------===//
00207 //                         User operator delete Implementation
00208 //===----------------------------------------------------------------------===//
00209 
00210 void User::operator delete(void *Usr) {
00211   User *Start = static_cast<User*>(Usr);
00212   Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
00213   //
00214   // look for a variadic User
00215   if (Storage == Start->OperandList) {
00216     ::operator delete(Storage);
00217     return;
00218   }
00219   //
00220   // check for the flag whether the destructor has detected a prefixed
00221   // allocation, in which case we remove the flag and delete starting
00222   // at OperandList
00223   if (reinterpret_cast<intptr_t>(Start->OperandList) & 1) {
00224     ::operator delete(reinterpret_cast<char*>(Start->OperandList) - 1);
00225     return;
00226   }
00227   //
00228   // in all other cases just delete the nullary User (covers hung-off
00229   // uses also
00230   ::operator delete(Usr);
00231 }
00232 
00233 } // End llvm namespace