LLVM  10.0.0svn
ValueList.cpp
Go to the documentation of this file.
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"
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  : 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
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.
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
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 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 
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 
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.
154  // Sort the values by-pointer so that they are efficient to look up with a
155  // binary search.
156  llvm::sort(ResolveConstants);
157 
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 }
auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1261
uint64_t CallInst * C
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
LLVMContext & Context
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:98
op_iterator op_begin()
Definition: User.h:229
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1014
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
#define DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CLASS, VALUECLASS)
Macro for generating out-of-class operand accessor definitions.
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:888
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:181
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
op_iterator op_end()
Definition: User.h:231
void resolveConstantForwardRefs()
Once all constants are read, this method bulk resolves any forward references.
Definition: ValueList.cpp:153
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1075
#define DECLARE_TRANSPARENT_OPERAND_ACCESSORS(VALUECLASS)
Macro for generating in-class operand accessor declarations.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
Constant * getConstantFwdRef(unsigned Idx, Type *Ty)
Definition: ValueList.cpp:99
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
void assignValue(Value *V, unsigned Idx, Type *FullTy)
Definition: ValueList.cpp:68
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Value * getValueFwdRef(unsigned Idx, Type *Ty, Type **FullTy=nullptr)
Definition: ValueList.cpp:119
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
#define I(x, y, z)
Definition: MD5.cpp:58
Compile-time customization of User operands.
Definition: User.h:42
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:386
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:395
LLVM Value Representation.
Definition: Value.h:73
FixedNumOperandTraits - determine the allocation regime of the Use array when it is a prefix to the U...
Definition: OperandTraits.h:30
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1110