LLVM  6.0.0svn
ValueList.cpp
Go to the documentation of this file.
1 //===- ValueList.cpp - Internal BitcodeReader implementation --------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "ValueList.h"
11 #include "llvm/ADT/SmallVector.h"
12 #include "llvm/IR/Argument.h"
13 #include "llvm/IR/Constant.h"
14 #include "llvm/IR/Constants.h"
15 #include "llvm/IR/GlobalValue.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/IR/Type.h"
18 #include "llvm/IR/User.h"
19 #include "llvm/IR/Value.h"
20 #include "llvm/IR/ValueHandle.h"
21 #include "llvm/Support/Casting.h"
23 #include <algorithm>
24 #include <cassert>
25 #include <cstddef>
26 #include <limits>
27 #include <utility>
28 
29 using namespace llvm;
30 
31 namespace llvm {
32 
33 namespace {
34 
35 /// \brief A class for maintaining the slot number definition
36 /// as a placeholder for the actual definition for forward constants defs.
37 class ConstantPlaceHolder : public ConstantExpr {
38 public:
39  explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
40  : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
41  Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
42  }
43 
44  ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete;
45 
46  // allocate space for exactly one operand
47  void *operator new(size_t s) { return User::operator new(s, 1); }
48 
49  /// \brief Methods to support type inquiry through isa, cast, and dyn_cast.
50  static bool classof(const Value *V) {
51  return isa<ConstantExpr>(V) &&
52  cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
53  }
54 
55  /// Provide fast operand accessors
57 };
58 
59 } // end anonymous namespace
60 
61 // FIXME: can we inherit this from ConstantExpr?
62 template <>
63 struct OperandTraits<ConstantPlaceHolder>
64  : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
65 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
66 
67 } // end namespace llvm
68 
70  if (Idx == size()) {
71  push_back(V);
72  return;
73  }
74 
75  if (Idx >= size())
76  resize(Idx + 1);
77 
78  WeakTrackingVH &OldV = ValuePtrs[Idx];
79  if (!OldV) {
80  OldV = V;
81  return;
82  }
83 
84  // Handle constants and non-constants (e.g. instrs) differently for
85  // efficiency.
86  if (Constant *PHC = dyn_cast<Constant>(&*OldV)) {
87  ResolveConstants.push_back(std::make_pair(PHC, Idx));
88  OldV = V;
89  } else {
90  // If there was a forward reference to this value, replace it.
91  Value *PrevVal = OldV;
92  OldV->replaceAllUsesWith(V);
93  PrevVal->deleteValue();
94  }
95 }
96 
98  if (Idx >= size())
99  resize(Idx + 1);
100 
101  if (Value *V = ValuePtrs[Idx]) {
102  if (Ty != V->getType())
103  report_fatal_error("Type mismatch in constant table!");
104  return cast<Constant>(V);
105  }
106 
107  // Create and return a placeholder, which will later be RAUW'd.
108  Constant *C = new ConstantPlaceHolder(Ty, Context);
109  ValuePtrs[Idx] = C;
110  return C;
111 }
112 
114  // Bail out for a clearly invalid value. This would make us call resize(0)
116  return nullptr;
117 
118  if (Idx >= size())
119  resize(Idx + 1);
120 
121  if (Value *V = ValuePtrs[Idx]) {
122  // If the types don't match, it's invalid.
123  if (Ty && Ty != V->getType())
124  return nullptr;
125  return V;
126  }
127 
128  // No type specified, must be invalid reference.
129  if (!Ty)
130  return nullptr;
131 
132  // Create and return a placeholder, which will later be RAUW'd.
133  Value *V = new Argument(Ty);
134  ValuePtrs[Idx] = V;
135  return V;
136 }
137 
138 /// Once all constants are read, this method bulk resolves any forward
139 /// references. The idea behind this is that we sometimes get constants (such
140 /// as large arrays) which reference *many* forward ref constants. Replacing
141 /// each of these causes a lot of thrashing when building/reuniquing the
142 /// constant. Instead of doing this, we look at all the uses and rewrite all
143 /// the place holders at once for any constant that uses a placeholder.
145  // Sort the values by-pointer so that they are efficient to look up with a
146  // binary search.
147  std::sort(ResolveConstants.begin(), ResolveConstants.end());
148 
150 
151  while (!ResolveConstants.empty()) {
152  Value *RealVal = operator[](ResolveConstants.back().second);
153  Constant *Placeholder = ResolveConstants.back().first;
154  ResolveConstants.pop_back();
155 
156  // Loop over all users of the placeholder, updating them to reference the
157  // new value. If they reference more than one placeholder, update them all
158  // at once.
159  while (!Placeholder->use_empty()) {
160  auto UI = Placeholder->user_begin();
161  User *U = *UI;
162 
163  // If the using object isn't uniqued, just update the operands. This
164  // handles instructions and initializers for global variables.
165  if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
166  UI.getUse().set(RealVal);
167  continue;
168  }
169 
170  // Otherwise, we have a constant that uses the placeholder. Replace that
171  // constant with a new constant that has *all* placeholder uses updated.
172  Constant *UserC = cast<Constant>(U);
173  for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
174  ++I) {
175  Value *NewOp;
176  if (!isa<ConstantPlaceHolder>(*I)) {
177  // Not a placeholder reference.
178  NewOp = *I;
179  } else if (*I == Placeholder) {
180  // Common case is that it just references this one placeholder.
181  NewOp = RealVal;
182  } else {
183  // Otherwise, look up the placeholder in ResolveConstants.
184  ResolveConstantsTy::iterator It = std::lower_bound(
185  ResolveConstants.begin(), ResolveConstants.end(),
186  std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
187  assert(It != ResolveConstants.end() && It->first == *I);
188  NewOp = operator[](It->second);
189  }
190 
191  NewOps.push_back(cast<Constant>(NewOp));
192  }
193 
194  // Make the new constant.
195  Constant *NewC;
196  if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
197  NewC = ConstantArray::get(UserCA->getType(), NewOps);
198  } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
199  NewC = ConstantStruct::get(UserCS->getType(), NewOps);
200  } else if (isa<ConstantVector>(UserC)) {
201  NewC = ConstantVector::get(NewOps);
202  } else {
203  assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
204  NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
205  }
206 
207  UserC->replaceAllUsesWith(NewC);
208  UserC->destroyConstant();
209  NewOps.clear();
210  }
211 
212  // Update all ValueHandles, they should be the only users at this point.
213  Placeholder->replaceAllUsesWith(RealVal);
214  Placeholder->deleteValue();
215  }
216 }
uint64_t CallInst * C
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
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:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:95
op_iterator op_begin()
Definition: User.h:214
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:888
Value * getValueFwdRef(unsigned Idx, Type *Ty)
Definition: ValueList.cpp:113
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
#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:862
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:182
void assignValue(Value *V, unsigned Idx)
Definition: ValueList.cpp:69
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
op_iterator op_end()
Definition: User.h:216
void resolveConstantForwardRefs()
Once all constants are read, this method bulk resolves any forward references.
Definition: ValueList.cpp:144
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:949
#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:1320
Constant * getConstantFwdRef(unsigned Idx, Type *Ty)
Definition: ValueList.cpp:97
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
ConstantArray - Constant Array Declarations.
Definition: Constants.h:405
auto lower_bound(R &&Range, ForwardIt I) -> decltype(std::begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:859
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
#define I(x, y, z)
Definition: MD5.cpp:58
Compile-time customization of User operands.
Definition: User.h:43
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:300
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:377
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:31
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:984