LLVM  13.0.0git
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/Support/Casting.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) {
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
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 
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 
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.
151  // Sort the values by-pointer so that they are efficient to look up with a
152  // binary search.
153  llvm::sort(ResolveConstants);
154 
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 }
llvm::BitcodeReaderValueList::push_back
void push_back(Value *V, Type *Ty)
Definition: ValueList.h:69
llvm::BitcodeReaderValueList::operator[]
Value * operator[](unsigned i) const
Definition: ValueList.h:80
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm
Definition: AllocatorList.h:23
llvm::WeakTrackingVH
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:204
ValueList.h
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1592
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1325
llvm::BitcodeReaderValueList::assignValue
void assignValue(Value *V, unsigned Idx, Type *FullTy)
Definition: ValueList.cpp:65
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
ErrorHandling.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DEFINE_TRANSPARENT_OPERAND_ACCESSORS
#define DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CLASS, VALUECLASS)
Macro for generating out-of-class operand accessor definitions.
Definition: OperandTraits.h:125
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:197
llvm::BitcodeReaderValueList::getConstantFwdRef
Constant * getConstantFwdRef(unsigned Idx, Type *Ty)
Definition: ValueList.cpp:96
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
Instruction.h
GlobalValue.h
llvm::OperandTraits
Compile-time customization of User operands.
Definition: User.h:42
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:407
llvm::Instruction
Definition: Instruction.h:45
llvm::report_fatal_error
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:140
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1783
Type.h
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::BitcodeReaderValueList::getValueFwdRef
Value * getValueFwdRef(unsigned Idx, Type *Ty, Type **FullTy=nullptr)
Definition: ValueList.cpp:116
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::BitcodeReaderValueList::resize
void resize(unsigned N)
Definition: ValueList.h:65
llvm::BitcodeReaderValueList::resolveConstantForwardRefs
void resolveConstantForwardRefs()
Once all constants are read, this method bulk resolves any forward references.
Definition: ValueList.cpp:150
llvm::BitcodeReaderValueList::size
unsigned size() const
Definition: ValueList.h:64
llvm::ConstantStruct
Definition: Constants.h:439
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:517
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1367
Argument.h
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:931
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
Casting.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
llvm::ConstantArray::get
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1261
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:584
DECLARE_TRANSPARENT_OPERAND_ACCESSORS
#define DECLARE_TRANSPARENT_OPERAND_ACCESSORS(VALUECLASS)
Macro for generating in-class operand accessor declarations.
Definition: OperandTraits.h:110
SmallVector.h
User.h
llvm::User::op_begin
op_iterator op_begin()
Definition: User.h:234
llvm::Value::deleteValue
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:107
llvm::FixedNumOperandTraits
FixedNumOperandTraits - determine the allocation regime of the Use array when it is a prefix to the U...
Definition: OperandTraits.h:30
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Constant::destroyConstant
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:459
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::User::op_end
op_iterator op_end()
Definition: User.h:236