1//===-- Use.cpp - Implement the Use class ---------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/IR/Use.h"
10#include "llvm/IR/User.h"
11#include "llvm/IR/Value.h"
12#include <new>
13
14namespace llvm {
15
16void Use::swap(Use &RHS) {
17  if (Val == RHS.Val)
18    return;
19
20  if (Val)
21    removeFromList();
22
23  Value *OldVal = Val;
24  if (RHS.Val) {
25    RHS.removeFromList();
26    Val = RHS.Val;
27    Val->addUse(*this);
28  } else {
29    Val = nullptr;
30  }
31
32  if (OldVal) {
33    RHS.Val = OldVal;
34    RHS.Val->addUse(RHS);
35  } else {
36    RHS.Val = nullptr;
37  }
38}
39
40User *Use::getUser() const {
41  const Use *End = getImpliedUser();
42  const UserRef *ref = reinterpret_cast<const UserRef *>(End);
43  return ref->getInt() ? ref->getPointer()
44                       : reinterpret_cast<User *>(const_cast<Use *>(End));
45}
46
47unsigned Use::getOperandNo() const {
48  return this - getUser()->op_begin();
49}
50
51// Sets up the waymarking algorithm's tags for a series of Uses. See the
52// algorithm details here:
53//
54//   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
55//
56Use *Use::initTags(Use *const Start, Use *Stop) {
57  ptrdiff_t Done = 0;
58  while (Done < 20) {
59    if (Start == Stop--)
60      return Start;
61    static const PrevPtrTag tags[20] = {
62        fullStopTag,  oneDigitTag,  stopTag,      oneDigitTag, oneDigitTag,
63        stopTag,      zeroDigitTag, oneDigitTag,  oneDigitTag, stopTag,
64        zeroDigitTag, oneDigitTag,  zeroDigitTag, oneDigitTag, stopTag,
65        oneDigitTag,  oneDigitTag,  oneDigitTag,  oneDigitTag, stopTag};
66    new (Stop) Use(tags[Done++]);
67  }
68
69  ptrdiff_t Count = Done;
70  while (Start != Stop) {
71    --Stop;
72    if (!Count) {
73      new (Stop) Use(stopTag);
74      ++Done;
75      Count = Done;
76    } else {
77      new (Stop) Use(PrevPtrTag(Count & 1));
78      Count >>= 1;
79      ++Done;
80    }
81  }
82
83  return Start;
84}
85
86void Use::zap(Use *Start, const Use *Stop, bool del) {
87  while (Start != Stop)
88    (--Stop)->~Use();
89  if (del)
90    ::operator delete(Start);
91}
92
93const Use *Use::getImpliedUser() const {
94  const Use *Current = this;
95
96  while (true) {
97    unsigned Tag = (Current++)->Prev.getInt();
98    switch (Tag) {
99    case zeroDigitTag:
100    case oneDigitTag:
101      continue;
102
103    case stopTag: {
104      ++Current;
105      ptrdiff_t Offset = 1;
106      while (true) {
107        unsigned Tag = Current->Prev.getInt();
108        switch (Tag) {
109        case zeroDigitTag:
110        case oneDigitTag:
111          ++Current;
112          Offset = (Offset << 1) + Tag;
113          continue;
114        default:
115          return Current + Offset;
116        }
117      }
118    }
119
120    case fullStopTag:
121      return Current;
122    }
123  }
124}
125
126} // End llvm namespace
127