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" 21 #include "llvm/Support/ErrorHandling.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 55 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 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 99 Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty) { 100 if (Idx >= size()) 101 resize(Idx + 1); 102 103 if (Value *V = ValuePtrs[Idx]) { 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; 112 return C; 113 } 114 115 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty, 116 Type **FullTy) { 117 // Bail out for a clearly invalid value. This would make us call resize(0) 118 if (Idx == std::numeric_limits<unsigned>::max()) 119 return nullptr; 120 121 if (Idx >= size()) 122 resize(Idx + 1); 123 124 if (Value *V = ValuePtrs[Idx]) { 125 // If the types don't match, it's invalid. 126 if (Ty && Ty != V->getType()) 127 return nullptr; 128 if (FullTy) 129 *FullTy = FullTypes[Idx]; 130 return V; 131 } 132 133 // No type specified, must be invalid reference. 134 if (!Ty) 135 return nullptr; 136 137 // Create and return a placeholder, which will later be RAUW'd. 138 Value *V = new Argument(Ty); 139 ValuePtrs[Idx] = V; 140 return V; 141 } 142 143 /// Once all constants are read, this method bulk resolves any forward 144 /// references. The idea behind this is that we sometimes get constants (such 145 /// as large arrays) which reference *many* forward ref constants. Replacing 146 /// each of these causes a lot of thrashing when building/reuniquing the 147 /// constant. Instead of doing this, we look at all the uses and rewrite all 148 /// the place holders at once for any constant that uses a placeholder. 149 void BitcodeReaderValueList::resolveConstantForwardRefs() { 150 // Sort the values by-pointer so that they are efficient to look up with a 151 // binary search. 152 llvm::sort(ResolveConstants); 153 154 SmallVector<Constant *, 64> NewOps; 155 156 while (!ResolveConstants.empty()) { 157 Value *RealVal = operator[](ResolveConstants.back().second); 158 Constant *Placeholder = ResolveConstants.back().first; 159 ResolveConstants.pop_back(); 160 161 // Loop over all users of the placeholder, updating them to reference the 162 // new value. If they reference more than one placeholder, update them all 163 // at once. 164 while (!Placeholder->use_empty()) { 165 auto UI = Placeholder->user_begin(); 166 User *U = *UI; 167 168 // If the using object isn't uniqued, just update the operands. This 169 // handles instructions and initializers for global variables. 170 if (!isa<Constant>(U) || isa<GlobalValue>(U)) { 171 UI.getUse().set(RealVal); 172 continue; 173 } 174 175 // Otherwise, we have a constant that uses the placeholder. Replace that 176 // constant with a new constant that has *all* placeholder uses updated. 177 Constant *UserC = cast<Constant>(U); 178 for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E; 179 ++I) { 180 Value *NewOp; 181 if (!isa<ConstantPlaceHolder>(*I)) { 182 // Not a placeholder reference. 183 NewOp = *I; 184 } else if (*I == Placeholder) { 185 // Common case is that it just references this one placeholder. 186 NewOp = RealVal; 187 } else { 188 // Otherwise, look up the placeholder in ResolveConstants. 189 ResolveConstantsTy::iterator It = llvm::lower_bound( 190 ResolveConstants, 191 std::pair<Constant *, unsigned>(cast<Constant>(*I), 0)); 192 assert(It != ResolveConstants.end() && It->first == *I); 193 NewOp = operator[](It->second); 194 } 195 196 NewOps.push_back(cast<Constant>(NewOp)); 197 } 198 199 // Make the new constant. 200 Constant *NewC; 201 if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) { 202 NewC = ConstantArray::get(UserCA->getType(), NewOps); 203 } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) { 204 NewC = ConstantStruct::get(UserCS->getType(), NewOps); 205 } else if (isa<ConstantVector>(UserC)) { 206 NewC = ConstantVector::get(NewOps); 207 } else { 208 assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr."); 209 NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps); 210 } 211 212 UserC->replaceAllUsesWith(NewC); 213 UserC->destroyConstant(); 214 NewOps.clear(); 215 } 216 217 // Update all ValueHandles, they should be the only users at this point. 218 Placeholder->replaceAllUsesWith(RealVal); 219 Placeholder->deleteValue(); 220 } 221 } 222