1//===- ValueList.cpp - Internal BitcodeReader implementation --------------===//
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 "ValueList.h"
10#include "llvm/ADT/SmallVector.h"
11#include "llvm/IR/Argument.h"
12#include "llvm/IR/Constant.h"
13#include "llvm/IR/Constants.h"
14#include "llvm/IR/GlobalValue.h"
15#include "llvm/IR/Instruction.h"
16#include "llvm/IR/Type.h"
17#include "llvm/IR/User.h"
18#include "llvm/IR/Value.h"
19#include "llvm/IR/ValueHandle.h"
20#include "llvm/Support/Casting.h"
21#include "llvm/Support/ErrorHandling.h"
22#include <algorithm>
23#include <cassert>
24#include <cstddef>
25#include <limits>
26#include <utility>
27
28using namespace llvm;
29
30namespace llvm {
31
32namespace {
33
34/// A class for maintaining the slot number definition
35/// as a placeholder for the actual definition for forward constants defs.
36class ConstantPlaceHolder : public ConstantExpr {
37public:
38  explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
39      : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
40    Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
41  }
42
43  ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete;
44
45  // allocate space for exactly one operand
46  void *operator new(size_t s) { return User::operator new(s, 1); }
47
48  /// Methods to support type inquiry through isa, cast, and dyn_cast.
49  static bool classof(const Value *V) {
50    return isa<ConstantExpr>(V) &&
51           cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
52  }
53
54  /// Provide fast operand accessors
55  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
56};
57
58} // end anonymous namespace
59
60// FIXME: can we inherit this from ConstantExpr?
61template <>
62struct OperandTraits<ConstantPlaceHolder>
63    : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
64DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
65
66} // end namespace llvm
67
68void BitcodeReaderValueList::assignValue(Value *V, unsigned Idx, Type *FullTy) {
69  if (Idx == size()) {
70    push_back(V, FullTy);
71    return;
72  }
73
74  if (Idx >= size())
75    resize(Idx + 1);
76
77  assert(FullTypes[Idx] == nullptr || FullTypes[Idx] == FullTy);
78  FullTypes[Idx] = FullTy;
79
80  WeakTrackingVH &OldV = ValuePtrs[Idx];
81  if (!OldV) {
82    OldV = V;
83    return;
84  }
85
86  // Handle constants and non-constants (e.g. instrs) differently for
87  // efficiency.
88  if (Constant *PHC = dyn_cast<Constant>(&*OldV)) {
89    ResolveConstants.push_back(std::make_pair(PHC, Idx));
90    OldV = V;
91  } else {
92    // If there was a forward reference to this value, replace it.
93    Value *PrevVal = OldV;
94    OldV->replaceAllUsesWith(V);
95    PrevVal->deleteValue();
96  }
97}
98
99Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty) {
100  // Bail out for a clearly invalid value.
101  if (Idx >= RefsUpperBound)
102    return nullptr;
103
104  if (Idx >= size())
105    resize(Idx + 1);
106
107  if (Value *V = ValuePtrs[Idx]) {
108    if (Ty != V->getType())
109      report_fatal_error("Type mismatch in constant table!");
110    return cast<Constant>(V);
111  }
112
113  // Create and return a placeholder, which will later be RAUW'd.
114  Constant *C = new ConstantPlaceHolder(Ty, Context);
115  ValuePtrs[Idx] = C;
116  return C;
117}
118
119Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
120                                              Type **FullTy) {
121  // Bail out for a clearly invalid value.
122  if (Idx >= RefsUpperBound)
123    return nullptr;
124
125  if (Idx >= size())
126    resize(Idx + 1);
127
128  if (Value *V = ValuePtrs[Idx]) {
129    // If the types don't match, it's invalid.
130    if (Ty && Ty != V->getType())
131      return nullptr;
132    if (FullTy)
133      *FullTy = FullTypes[Idx];
134    return V;
135  }
136
137  // No type specified, must be invalid reference.
138  if (!Ty)
139    return nullptr;
140
141  // Create and return a placeholder, which will later be RAUW'd.
142  Value *V = new Argument(Ty);
143  ValuePtrs[Idx] = V;
144  return V;
145}
146
147/// Once all constants are read, this method bulk resolves any forward
148/// references.  The idea behind this is that we sometimes get constants (such
149/// as large arrays) which reference *many* forward ref constants.  Replacing
150/// each of these causes a lot of thrashing when building/reuniquing the
151/// constant.  Instead of doing this, we look at all the uses and rewrite all
152/// the place holders at once for any constant that uses a placeholder.
153void BitcodeReaderValueList::resolveConstantForwardRefs() {
154  // Sort the values by-pointer so that they are efficient to look up with a
155  // binary search.
156  llvm::sort(ResolveConstants);
157
158  SmallVector<Constant *, 64> NewOps;
159
160  while (!ResolveConstants.empty()) {
161    Value *RealVal = operator[](ResolveConstants.back().second);
162    Constant *Placeholder = ResolveConstants.back().first;
163    ResolveConstants.pop_back();
164
165    // Loop over all users of the placeholder, updating them to reference the
166    // new value.  If they reference more than one placeholder, update them all
167    // at once.
168    while (!Placeholder->use_empty()) {
169      auto UI = Placeholder->user_begin();
170      User *U = *UI;
171
172      // If the using object isn't uniqued, just update the operands.  This
173      // handles instructions and initializers for global variables.
174      if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
175        UI.getUse().set(RealVal);
176        continue;
177      }
178
179      // Otherwise, we have a constant that uses the placeholder.  Replace that
180      // constant with a new constant that has *all* placeholder uses updated.
181      Constant *UserC = cast<Constant>(U);
182      for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
183           ++I) {
184        Value *NewOp;
185        if (!isa<ConstantPlaceHolder>(*I)) {
186          // Not a placeholder reference.
187          NewOp = *I;
188        } else if (*I == Placeholder) {
189          // Common case is that it just references this one placeholder.
190          NewOp = RealVal;
191        } else {
192          // Otherwise, look up the placeholder in ResolveConstants.
193          ResolveConstantsTy::iterator It = llvm::lower_bound(
194              ResolveConstants,
195              std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
196          assert(It != ResolveConstants.end() && It->first == *I);
197          NewOp = operator[](It->second);
198        }
199
200        NewOps.push_back(cast<Constant>(NewOp));
201      }
202
203      // Make the new constant.
204      Constant *NewC;
205      if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
206        NewC = ConstantArray::get(UserCA->getType(), NewOps);
207      } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
208        NewC = ConstantStruct::get(UserCS->getType(), NewOps);
209      } else if (isa<ConstantVector>(UserC)) {
210        NewC = ConstantVector::get(NewOps);
211      } else {
212        assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
213        NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
214      }
215
216      UserC->replaceAllUsesWith(NewC);
217      UserC->destroyConstant();
218      NewOps.clear();
219    }
220
221    // Update all ValueHandles, they should be the only users at this point.
222    Placeholder->replaceAllUsesWith(RealVal);
223    Placeholder->deleteValue();
224  }
225}
226