Use.cpp revision efe65369a74871c3140a540a6c95ce5d1f080954 
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
16namespace llvm {
17
18//===----------------------------------------------------------------------===//
19//                         Use getImpliedUser Implementation
20//===----------------------------------------------------------------------===//
21
22const 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
59Use *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
82void 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
100struct AugmentedUse : Use {
101  User *ref;
102  AugmentedUse(); // not implemented
103};
104
105
106//===----------------------------------------------------------------------===//
107//                         Use getUser Implementation
108//===----------------------------------------------------------------------===//
109
110User *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
124Use *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
132