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 getImpliedUser Implementation
  20 //===----------------------------------------------------------------------===//
  21
  22 const Use *Use::getImpliedUser() const {
  23   const Use *Current = this;
  24
  25   while (true) {
  26     unsigned Tag = extractTag<PrevPtrTag, fullStopTag>((Current++)->Prev);
  27     switch (Tag) {
  28       case zeroDigitTag:
  29       case oneDigitTag:
  30         continue;
  31
  32       case stopTag: {
  33         ++Current;
  34         ptrdiff_t Offset = 1;
  35         while (true) {
  36           unsigned Tag = extractTag<PrevPtrTag, fullStopTag>(Current->Prev);
  37           switch (Tag) {
  38             case zeroDigitTag:
  39             case oneDigitTag:
  40               ++Current;
  41               Offset = (Offset << 1) + Tag;
  42               continue;
  43             default:
  44               return Current + Offset;
  45           }
  46         }
  47       }
  48
  49       case fullStopTag:
  50         return Current;
  51     }
  52   }
  53 }
  54
  55 //===----------------------------------------------------------------------===//
  56 //                         Use initTags Implementation
  57 //===----------------------------------------------------------------------===//
  58
  59 Use *Use::initTags(Use * const Start, Use *Stop, ptrdiff_t Done) {
  60   ptrdiff_t Count = Done;
  61   while (Start != Stop) {
  62     --Stop;
  63     Stop->Val = 0;
  64     if (!Count) {
  65       Stop->Prev = reinterpret_cast<Use**>(Done == 0 ? fullStopTag : stopTag);
  66       ++Done;
  67       Count = Done;
  68     } else {
  69       Stop->Prev = reinterpret_cast<Use**>(Count & 1);
  70       Count >>= 1;
  71       ++Done;
  72     }
  73   }
  74
  75   return Start;
  76 }
  77
  78 //===----------------------------------------------------------------------===//
  79 //                         Use zap Implementation
  80 //===----------------------------------------------------------------------===//
  81
  82 void Use::zap(Use *Start, const Use *Stop, bool del) {
  83   if (del) {
  84     while (Start != Stop) {
  85       (--Stop)->~Use();
  86     }
  87     ::operator delete(Start);
  88     return;
  89   }
  90
  91   while (Start != Stop) {
  92     (Start++)->set(0);
  93   }
  94 }
  95
  96 //===----------------------------------------------------------------------===//
  97 //                         AugmentedUse layout struct
  98 //===----------------------------------------------------------------------===//
  99
 100 struct AugmentedUse : Use {
 101   User *ref;
 102   AugmentedUse(); // not implemented
 103 };
 104
 105
 106 //===----------------------------------------------------------------------===//
 107 //                         Use getUser Implementation
 108 //===----------------------------------------------------------------------===//
 109
 110 User *Use::getUser() const {
 111   const Use *End = getImpliedUser();
 112   User *She = static_cast<const AugmentedUse*>(End - 1)->ref;
 113   She = extractTag<Tag, tagOne>(She)
 114       ? llvm::stripTag<tagOne>(She)
 115       : reinterpret_cast<User*>(const_cast<Use*>(End));
 116
 117   return She;
 118 }
 119
 120 //===----------------------------------------------------------------------===//
 121 //                         User allocHungoffUses Implementation
 122 //===----------------------------------------------------------------------===//
 123
 124 Use *User::allocHungoffUses(unsigned N) const {
 125   Use *Begin = static_cast<Use*>(::operator new(sizeof(Use) * N + sizeof(AugmentedUse) - sizeof(Use)));
 126   Use *End = Begin + N;
 127   static_cast<AugmentedUse&>(End[-1]).ref = addTag(this, tagOne);
 128   return Use::initTags(Begin, End);
 129 }
 130
 131 } // End llvm namespace