lib/VMCore/Use.cpp

   1 //===-- Use.cpp - Implement the Use class ---------------------------------===//
   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 implements the algorithm for finding the User of a Use.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/User.h"
  15
  16 namespace llvm {
  17
  18 //===----------------------------------------------------------------------===//
  19 //                         Use swap Implementation
  20 //===----------------------------------------------------------------------===//
  21
  22 void Use::swap(Use &RHS) {
  23   Value *V1(Val);
  24   Value *V2(RHS.Val);
  25   if (V1 != V2) {
  26     if (V1) {
  27       removeFromList();
  28     }
  29
  30     if (V2) {
  31       RHS.removeFromList();
  32       Val = V2;
  33       V2->addUse(*this);
  34     } else {
  35       Val = 0;
  36     }
  37
  38     if (V1) {
  39       RHS.Val = V1;
  40       V1->addUse(RHS);
  41     } else {
  42       RHS.Val = 0;
  43     }
  44   }
  45 }
  46
  47 //===----------------------------------------------------------------------===//
  48 //                         Use getImpliedUser Implementation
  49 //===----------------------------------------------------------------------===//
  50
  51 const Use *Use::getImpliedUser() const {
  52   const Use *Current = this;
  53
  54   while (true) {
  55     unsigned Tag = (Current++)->Prev.getInt();
  56     switch (Tag) {
  57       case zeroDigitTag:
  58       case oneDigitTag:
  59         continue;
  60
  61       case stopTag: {
  62         ++Current;
  63         ptrdiff_t Offset = 1;
  64         while (true) {
  65           unsigned Tag = Current->Prev.getInt();
  66           switch (Tag) {
  67             case zeroDigitTag:
  68             case oneDigitTag:
  69               ++Current;
  70               Offset = (Offset << 1) + Tag;
  71               continue;
  72             default:
  73               return Current + Offset;
  74           }
  75         }
  76       }
  77
  78       case fullStopTag:
  79         return Current;
  80     }
  81   }
  82 }
  83
  84 //===----------------------------------------------------------------------===//
  85 //                         Use initTags Implementation
  86 //===----------------------------------------------------------------------===//
  87
  88 Use *Use::initTags(Use * const Start, Use *Stop, ptrdiff_t Done) {
  89   while (Done < 20) {
  90     if (Start == Stop--)
  91       return Start;
  92     static const PrevPtrTag tags[20] = { fullStopTag, oneDigitTag, stopTag,
  93                                          oneDigitTag, oneDigitTag, stopTag,
  94                                          zeroDigitTag, oneDigitTag, oneDigitTag,
  95                                          stopTag, zeroDigitTag, oneDigitTag,
  96                                          zeroDigitTag, oneDigitTag, stopTag,
  97                                          oneDigitTag, oneDigitTag, oneDigitTag,
  98                                          oneDigitTag, stopTag
  99                                        };
 100     Stop->Prev.setFromOpaqueValue(reinterpret_cast<Use**>(tags[Done++]));
 101     Stop->Val = 0;
 102   }
 103
 104   ptrdiff_t Count = Done;
 105   while (Start != Stop) {
 106     --Stop;
 107     Stop->Val = 0;
 108     if (!Count) {
 109       Stop->Prev.setFromOpaqueValue(reinterpret_cast<Use**>(stopTag));
 110       ++Done;
 111       Count = Done;
 112     } else {
 113       Stop->Prev.setFromOpaqueValue(reinterpret_cast<Use**>(Count & 1));
 114       Count >>= 1;
 115       ++Done;
 116     }
 117   }
 118
 119   return Start;
 120 }
 121
 122 //===----------------------------------------------------------------------===//
 123 //                         Use zap Implementation
 124 //===----------------------------------------------------------------------===//
 125
 126 void Use::zap(Use *Start, const Use *Stop, bool del) {
 127   if (del) {
 128     while (Start != Stop) {
 129       (--Stop)->~Use();
 130     }
 131     ::operator delete(Start);
 132     return;
 133   }
 134
 135   while (Start != Stop) {
 136     (Start++)->set(0);
 137   }
 138 }
 139
 140 //===----------------------------------------------------------------------===//
 141 //                         AugmentedUse layout struct
 142 //===----------------------------------------------------------------------===//
 143
 144 struct AugmentedUse : public Use {
 145   PointerIntPair<User*, 1, Tag> ref;
 146   AugmentedUse(); // not implemented
 147 };
 148
 149
 150 //===----------------------------------------------------------------------===//
 151 //                         Use getUser Implementation
 152 //===----------------------------------------------------------------------===//
 153
 154 User *Use::getUser() const {
 155   const Use *End = getImpliedUser();
 156   const PointerIntPair<User*, 1, Tag>& ref(
 157                                 static_cast<const AugmentedUse*>(End - 1)->ref);
 158   User *She = ref.getPointer();
 159   return ref.getInt()
 160     ? She
 161     : (User*)End;
 162 }
 163
 164 //===----------------------------------------------------------------------===//
 165 //                         User allocHungoffUses Implementation
 166 //===----------------------------------------------------------------------===//
 167
 168 Use *User::allocHungoffUses(unsigned N) const {
 169   Use *Begin = static_cast<Use*>(::operator new(sizeof(Use) * N
 170                                                 + sizeof(AugmentedUse)
 171                                                 - sizeof(Use)));
 172   Use *End = Begin + N;
 173   PointerIntPair<User*, 1, Tag>& ref(static_cast<AugmentedUse&>(End[-1]).ref);
 174   ref.setPointer(const_cast<User*>(this));
 175   ref.setInt(tagOne);
 176   return Use::initTags(Begin, End);
 177 }
 178
 179 //===----------------------------------------------------------------------===//
 180 //                         User operator new Implementations
 181 //===----------------------------------------------------------------------===//
 182
 183 void *User::operator new(size_t s, unsigned Us) {
 184   void *Storage = ::operator new(s + sizeof(Use) * Us);
 185   Use *Start = static_cast<Use*>(Storage);
 186   Use *End = Start + Us;
 187   User *Obj = reinterpret_cast<User*>(End);
 188   Obj->OperandList = Start;
 189   Obj->NumOperands = Us;
 190   Use::initTags(Start, End);
 191   return Obj;
 192 }
 193
 194 /// Prefixed allocation - just before the first Use, allocate a NULL pointer.
 195 /// The destructor can detect its presence and readjust the OperandList
 196 /// for deletition.
 197 ///
 198 void *User::operator new(size_t s, unsigned Us, bool Prefix) {
 199   // currently prefixed allocation only admissible for
 200   // unconditional branch instructions
 201   if (!Prefix)
 202     return operator new(s, Us);
 203
 204   assert(Us == 1 && "Other than one Use allocated?");
 205   typedef PointerIntPair<void*, 2, Use::PrevPtrTag> TaggedPrefix;
 206   void *Raw = ::operator new(s + sizeof(TaggedPrefix) + sizeof(Use) * Us);
 207   TaggedPrefix *Pre = static_cast<TaggedPrefix*>(Raw);
 208   Pre->setFromOpaqueValue(0);
 209   void *Storage = Pre + 1; // skip over prefix
 210   Use *Start = static_cast<Use*>(Storage);
 211   Use *End = Start + Us;
 212   User *Obj = reinterpret_cast<User*>(End);
 213   Obj->OperandList = Start;
 214   Obj->NumOperands = Us;
 215   Use::initTags(Start, End);
 216   return Obj;
 217 }
 218
 219 //===----------------------------------------------------------------------===//
 220 //                         User operator delete Implementation
 221 //===----------------------------------------------------------------------===//
 222
 223 void User::operator delete(void *Usr) {
 224   User *Start = static_cast<User*>(Usr);
 225   Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
 226   //
 227   // look for a variadic User
 228   if (Storage == Start->OperandList) {
 229     ::operator delete(Storage);
 230     return;
 231   }
 232   //
 233   // check for the flag whether the destructor has detected a prefixed
 234   // allocation, in which case we remove the flag and delete starting
 235   // at OperandList
 236   if (reinterpret_cast<intptr_t>(Start->OperandList) & 1) {
 237     ::operator delete(reinterpret_cast<char*>(Start->OperandList) - 1);
 238     return;
 239   }
 240   //
 241   // in all other cases just delete the nullary User (covers hung-off
 242   // uses also
 243   ::operator delete(Usr);
 244 }
 245
 246 } // End llvm namespace