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" 22 #include "llvm/Support/ErrorHandling.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 /// 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 /// 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 56 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); 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 69 void BitcodeReaderValueList::assignValue(Value *V, unsigned Idx) { 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 97 Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty) { 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 113 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty) { 114 // Bail out for a clearly invalid value. This would make us call resize(0) 115 if (Idx == std::numeric_limits<unsigned>::max()) 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. 144 void BitcodeReaderValueList::resolveConstantForwardRefs() { 145 // Sort the values by-pointer so that they are efficient to look up with a 146 // binary search. 147 llvm::sort(ResolveConstants.begin(), ResolveConstants.end()); 148 149 SmallVector<Constant *, 64> NewOps; 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 } 217