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