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