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   ptrdiff_t dist((char*)&RHS - (char*)this);
  24
  25   if (dist) {
  26     Use *valid1(stripTag<tagMaskN>(Next));
  27     Use *valid2(stripTag<tagMaskN>(RHS.Next));
  28     if (valid1 && valid2) {
  29       bool real1(fullStopTagN != extractTag<NextPtrTag, tagMaskN>(Next));
  30       bool real2(fullStopTagN != extractTag<NextPtrTag, tagMaskN>(RHS.Next));
  31       (char*&)*stripTag<tagMask>(Prev) += dist;
  32       (char*&)*stripTag<tagMask>(RHS.Prev) -= dist;
  33       if (real1)
  34         (char*&)valid1->Next += dist;
  35       if (real2)
  36         (char*&)valid2->Next -= dist;
  37
  38     }
  39
  40     // swap the members
  41     std::swap(Next, RHS.Next);
  42     Use** Prev1 = transferTag<tagMask>(Prev, stripTag<tagMask>(RHS.Prev));
  43     RHS.Prev = transferTag<tagMask>(RHS.Prev, stripTag<tagMask>(Prev));
  44     Prev = Prev1;
  45   }
  46   /*  Value *V1(Val1);
  47   Value *V2(RHS.Val1);
  48   if (V1 != V2) {
  49     if (V1) {
  50       removeFromList();
  51     }
  52
  53     if (V2) {
  54       RHS.removeFromList();
  55       Val1 = V2;
  56       V2->addUse(*this);
  57     } else {
  58       Val1 = 0;
  59     }
  60
  61     if (V1) {
  62       RHS.Val1 = V1;
  63       V1->addUse(RHS);
  64     } else {
  65       RHS.Val1 = 0;
  66     }
  67   }
  68   */
  69 }
  70
  71 //===----------------------------------------------------------------------===//
  72 //                         Use getImpliedUser Implementation
  73 //===----------------------------------------------------------------------===//
  74
  75 const Use *Use::getImpliedUser() const {
  76   const Use *Current = this;
  77
  78   while (true) {
  79     unsigned Tag = extractTag<PrevPtrTag, tagMask>((Current++)->Prev);
  80     switch (Tag) {
  81       case zeroDigitTag:
  82       case oneDigitTag:
  83         continue;
  84
  85       case stopTag: {
  86         ++Current;
  87         ptrdiff_t Offset = 1;
  88         while (true) {
  89           unsigned Tag = extractTag<PrevPtrTag, tagMask>(Current->Prev);
  90           switch (Tag) {
  91             case zeroDigitTag:
  92             case oneDigitTag:
  93               ++Current;
  94               Offset = (Offset << 1) + Tag;
  95               continue;
  96             default:
  97               return Current + Offset;
  98           }
  99         }
 100       }
 101
 102       case fullStopTag:
 103         return Current;
 104     }
 105   }
 106 }
 107
 108 //===----------------------------------------------------------------------===//
 109 //                         Use initTags Implementation
 110 //===----------------------------------------------------------------------===//
 111
 112 Use *Use::initTags(Use * const Start, Use *Stop, ptrdiff_t Done) {
 113   ptrdiff_t Count = Done;
 114   while (Start != Stop) {
 115     --Stop;
 116     Stop->Val1 = 0;
 117     Stop->Next = nilUse(0);
 118     if (!Count) {
 119       Stop->Prev = reinterpret_cast<Use**>(Done == 0 ? fullStopTag : stopTag);
 120       ++Done;
 121       Count = Done;
 122     } else {
 123       Stop->Prev = reinterpret_cast<Use**>(Count & 1);
 124       Count >>= 1;
 125       ++Done;
 126     }
 127   }
 128
 129   return Start;
 130 }
 131
 132 //===----------------------------------------------------------------------===//
 133 //                         Use zap Implementation
 134 //===----------------------------------------------------------------------===//
 135
 136 void Use::zap(Use *Start, const Use *Stop, bool del) {
 137   if (del) {
 138     while (Start != Stop) {
 139       (--Stop)->~Use();
 140     }
 141     ::operator delete(Start);
 142     return;
 143   }
 144
 145   while (Start != Stop) {
 146     (Start++)->set(0);
 147   }
 148 }
 149
 150 //===----------------------------------------------------------------------===//
 151 //                         AugmentedUse layout struct
 152 //===----------------------------------------------------------------------===//
 153
 154 struct AugmentedUse : Use {
 155   User *ref;
 156   AugmentedUse(); // not implemented
 157 };
 158
 159
 160 //===----------------------------------------------------------------------===//
 161 //                         Use getUser Implementation
 162 //===----------------------------------------------------------------------===//
 163
 164 User *Use::getUser() const {
 165   const Use *End = getImpliedUser();
 166   User *She = static_cast<const AugmentedUse*>(End - 1)->ref;
 167   She = extractTag<Tag, tagOne>(She)
 168       ? llvm::stripTag<tagOne>(She)
 169       : reinterpret_cast<User*>(const_cast<Use*>(End));
 170
 171   return She;
 172 }
 173
 174 //===----------------------------------------------------------------------===//
 175 //                         User allocHungoffUses Implementation
 176 //===----------------------------------------------------------------------===//
 177
 178 Use *User::allocHungoffUses(unsigned N) const {
 179   Use *Begin = static_cast<Use*>(::operator new(sizeof(Use) * N
 180                                                 + sizeof(AugmentedUse)
 181                                                 - sizeof(Use)));
 182   Use *End = Begin + N;
 183   static_cast<AugmentedUse&>(End[-1]).ref = addTag(this, tagOne);
 184   return Use::initTags(Begin, End);
 185 }
 186
 187 } // End llvm namespace