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
28 using namespace llvm;
29
30 namespace llvm {
31
32 namespace {
33
34 /// A class for maintaining the slot number definition
35 /// as a placeholder for the actual definition for forward constants defs.
36 class ConstantPlaceHolder : public ConstantExpr {
37 public:
ConstantPlaceHolder(Type * Ty,LLVMContext & Context)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
operator new(size_t s)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.
classof(const Value * V)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?
61 template <>
62 struct OperandTraits<ConstantPlaceHolder>
63 : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
64 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
65
66 } // end namespace llvm
67
assignValue(Value * V,unsigned Idx,Type * FullTy)68 void 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
getConstantFwdRef(unsigned Idx,Type * Ty)99 Constant *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
getValueFwdRef(unsigned Idx,Type * Ty,Type ** FullTy)119 Value *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.
resolveConstantForwardRefs()153 void 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