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