/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Bitcode/Reader/ValueList.cpp
Line | Count | Source (jump to first uncovered line) |
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: |
38 | | explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context) |
39 | 2.90k | : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) { |
40 | 2.90k | Op<0>() = UndefValue::get(Type::getInt32Ty(Context)); |
41 | 2.90k | } |
42 | | |
43 | | ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete; |
44 | | |
45 | | // allocate space for exactly one operand |
46 | 2.90k | 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 | 2.90k | static bool classof(const Value *V) { |
50 | 2.90k | return isa<ConstantExpr>(V) && |
51 | 2.90k | cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp12.90k ; |
52 | 2.90k | } |
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 | | |
68 | 8.59M | void BitcodeReaderValueList::assignValue(Value *V, unsigned Idx, Type *FullTy) { |
69 | 8.59M | if (Idx == size()) { |
70 | 4.61M | push_back(V, FullTy); |
71 | 4.61M | return; |
72 | 4.61M | } |
73 | 3.98M | |
74 | 3.98M | if (Idx >= size()) |
75 | 0 | resize(Idx + 1); |
76 | 3.98M | |
77 | 3.98M | assert(FullTypes[Idx] == nullptr || FullTypes[Idx] == FullTy); |
78 | 3.98M | FullTypes[Idx] = FullTy; |
79 | 3.98M | |
80 | 3.98M | WeakTrackingVH &OldV = ValuePtrs[Idx]; |
81 | 3.98M | if (!OldV) { |
82 | 3.72M | OldV = V; |
83 | 3.72M | return; |
84 | 3.72M | } |
85 | 254k | |
86 | 254k | // Handle constants and non-constants (e.g. instrs) differently for |
87 | 254k | // efficiency. |
88 | 254k | if (Constant *PHC = dyn_cast<Constant>(&*OldV)) { |
89 | 2.90k | ResolveConstants.push_back(std::make_pair(PHC, Idx)); |
90 | 2.90k | OldV = V; |
91 | 252k | } else { |
92 | 252k | // If there was a forward reference to this value, replace it. |
93 | 252k | Value *PrevVal = OldV; |
94 | 252k | OldV->replaceAllUsesWith(V); |
95 | 252k | PrevVal->deleteValue(); |
96 | 252k | } |
97 | 254k | } |
98 | | |
99 | 1.46M | Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty) { |
100 | 1.46M | // Bail out for a clearly invalid value. |
101 | 1.46M | if (Idx >= RefsUpperBound) |
102 | 0 | return nullptr; |
103 | 1.46M | |
104 | 1.46M | if (Idx >= size()) |
105 | 2.90k | resize(Idx + 1); |
106 | 1.46M | |
107 | 1.46M | if (Value *V = ValuePtrs[Idx]) { |
108 | 1.45M | if (Ty != V->getType()) |
109 | 0 | report_fatal_error("Type mismatch in constant table!"); |
110 | 1.45M | return cast<Constant>(V); |
111 | 1.45M | } |
112 | 2.90k | |
113 | 2.90k | // Create and return a placeholder, which will later be RAUW'd. |
114 | 2.90k | Constant *C = new ConstantPlaceHolder(Ty, Context); |
115 | 2.90k | ValuePtrs[Idx] = C; |
116 | 2.90k | return C; |
117 | 2.90k | } |
118 | | |
119 | | Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty, |
120 | 19.0M | Type **FullTy) { |
121 | 19.0M | // Bail out for a clearly invalid value. |
122 | 19.0M | if (Idx >= RefsUpperBound) |
123 | 2 | return nullptr; |
124 | 19.0M | |
125 | 19.0M | if (Idx >= size()) |
126 | 185k | resize(Idx + 1); |
127 | 19.0M | |
128 | 19.0M | if (Value *V = ValuePtrs[Idx]) { |
129 | 18.7M | // If the types don't match, it's invalid. |
130 | 18.7M | if (Ty && Ty != V->getType()5.61M ) |
131 | 1 | return nullptr; |
132 | 18.7M | if (FullTy) |
133 | 5.51M | *FullTy = FullTypes[Idx]; |
134 | 18.7M | return V; |
135 | 18.7M | } |
136 | 252k | |
137 | 252k | // No type specified, must be invalid reference. |
138 | 252k | if (!Ty) |
139 | 0 | return nullptr; |
140 | 252k | |
141 | 252k | // Create and return a placeholder, which will later be RAUW'd. |
142 | 252k | Value *V = new Argument(Ty); |
143 | 252k | ValuePtrs[Idx] = V; |
144 | 252k | return V; |
145 | 252k | } |
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. |
153 | 159k | void BitcodeReaderValueList::resolveConstantForwardRefs() { |
154 | 159k | // Sort the values by-pointer so that they are efficient to look up with a |
155 | 159k | // binary search. |
156 | 159k | llvm::sort(ResolveConstants); |
157 | 159k | |
158 | 159k | SmallVector<Constant *, 64> NewOps; |
159 | 159k | |
160 | 162k | while (!ResolveConstants.empty()) { |
161 | 2.90k | Value *RealVal = operator[](ResolveConstants.back().second); |
162 | 2.90k | Constant *Placeholder = ResolveConstants.back().first; |
163 | 2.90k | ResolveConstants.pop_back(); |
164 | 2.90k | |
165 | 2.90k | // Loop over all users of the placeholder, updating them to reference the |
166 | 2.90k | // new value. If they reference more than one placeholder, update them all |
167 | 2.90k | // at once. |
168 | 5.80k | while (!Placeholder->use_empty()) { |
169 | 2.90k | auto UI = Placeholder->user_begin(); |
170 | 2.90k | User *U = *UI; |
171 | 2.90k | |
172 | 2.90k | // If the using object isn't uniqued, just update the operands. This |
173 | 2.90k | // handles instructions and initializers for global variables. |
174 | 2.90k | if (!isa<Constant>(U) || isa<GlobalValue>(U)) { |
175 | 0 | UI.getUse().set(RealVal); |
176 | 0 | continue; |
177 | 0 | } |
178 | 2.90k | |
179 | 2.90k | // Otherwise, we have a constant that uses the placeholder. Replace that |
180 | 2.90k | // constant with a new constant that has *all* placeholder uses updated. |
181 | 2.90k | Constant *UserC = cast<Constant>(U); |
182 | 5.80k | for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E; |
183 | 2.90k | ++I) { |
184 | 2.90k | Value *NewOp; |
185 | 2.90k | if (!isa<ConstantPlaceHolder>(*I)) { |
186 | 3 | // Not a placeholder reference. |
187 | 3 | NewOp = *I; |
188 | 2.90k | } else if (*I == Placeholder) { |
189 | 2.90k | // Common case is that it just references this one placeholder. |
190 | 2.90k | NewOp = RealVal; |
191 | 2.90k | } else { |
192 | 0 | // Otherwise, look up the placeholder in ResolveConstants. |
193 | 0 | ResolveConstantsTy::iterator It = llvm::lower_bound( |
194 | 0 | ResolveConstants, |
195 | 0 | std::pair<Constant *, unsigned>(cast<Constant>(*I), 0)); |
196 | 0 | assert(It != ResolveConstants.end() && It->first == *I); |
197 | 0 | NewOp = operator[](It->second); |
198 | 0 | } |
199 | 2.90k | |
200 | 2.90k | NewOps.push_back(cast<Constant>(NewOp)); |
201 | 2.90k | } |
202 | 2.90k | |
203 | 2.90k | // Make the new constant. |
204 | 2.90k | Constant *NewC; |
205 | 2.90k | if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) { |
206 | 0 | NewC = ConstantArray::get(UserCA->getType(), NewOps); |
207 | 2.90k | } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) { |
208 | 1 | NewC = ConstantStruct::get(UserCS->getType(), NewOps); |
209 | 2.89k | } else if (isa<ConstantVector>(UserC)) { |
210 | 0 | NewC = ConstantVector::get(NewOps); |
211 | 2.89k | } else { |
212 | 2.89k | assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr."); |
213 | 2.89k | NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps); |
214 | 2.89k | } |
215 | 2.90k | |
216 | 2.90k | UserC->replaceAllUsesWith(NewC); |
217 | 2.90k | UserC->destroyConstant(); |
218 | 2.90k | NewOps.clear(); |
219 | 2.90k | } |
220 | 2.90k | |
221 | 2.90k | // Update all ValueHandles, they should be the only users at this point. |
222 | 2.90k | Placeholder->replaceAllUsesWith(RealVal); |
223 | 2.90k | Placeholder->deleteValue(); |
224 | 2.90k | } |
225 | 159k | } |