1 //===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===// 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 // This file defines the MapValue function, which is shared by various parts of 11 // the lib/Transforms/Utils library. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/ValueMapper.h" 16 #include "llvm/IR/Constants.h" 17 #include "llvm/IR/Function.h" 18 #include "llvm/IR/InlineAsm.h" 19 #include "llvm/IR/Instructions.h" 20 #include "llvm/IR/Metadata.h" 21 using namespace llvm; 22 23 // Out of line method to get vtable etc for class. 24 void ValueMapTypeRemapper::anchor() {} 25 void ValueMaterializer::anchor() {} 26 27 Value *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags, 28 ValueMapTypeRemapper *TypeMapper, 29 ValueMaterializer *Materializer) { 30 ValueToValueMapTy::iterator I = VM.find(V); 31 32 // If the value already exists in the map, use it. 33 if (I != VM.end() && I->second) return I->second; 34 35 // If we have a materializer and it can materialize a value, use that. 36 if (Materializer) { 37 if (Value *NewV = Materializer->materializeValueFor(const_cast<Value*>(V))) 38 return VM[V] = NewV; 39 } 40 41 // Global values do not need to be seeded into the VM if they 42 // are using the identity mapping. 43 if (isa<GlobalValue>(V)) 44 return VM[V] = const_cast<Value*>(V); 45 46 if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) { 47 // Inline asm may need *type* remapping. 48 FunctionType *NewTy = IA->getFunctionType(); 49 if (TypeMapper) { 50 NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy)); 51 52 if (NewTy != IA->getFunctionType()) 53 V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(), 54 IA->hasSideEffects(), IA->isAlignStack()); 55 } 56 57 return VM[V] = const_cast<Value*>(V); 58 } 59 60 if (const auto *MDV = dyn_cast<MetadataAsValue>(V)) { 61 const Metadata *MD = MDV->getMetadata(); 62 // If this is a module-level metadata and we know that nothing at the module 63 // level is changing, then use an identity mapping. 64 if (!isa<LocalAsMetadata>(MD) && (Flags & RF_NoModuleLevelChanges)) 65 return VM[V] = const_cast<Value *>(V); 66 67 auto *MappedMD = MapMetadata(MD, VM, Flags, TypeMapper, Materializer); 68 if (MD == MappedMD || (!MappedMD && (Flags & RF_IgnoreMissingEntries))) 69 return VM[V] = const_cast<Value *>(V); 70 71 // FIXME: This assert crashes during bootstrap, but I think it should be 72 // correct. For now, just match behaviour from before the metadata/value 73 // split. 74 // 75 // assert(MappedMD && "Referenced metadata value not in value map"); 76 return VM[V] = MetadataAsValue::get(V->getContext(), MappedMD); 77 } 78 79 // Okay, this either must be a constant (which may or may not be mappable) or 80 // is something that is not in the mapping table. 81 Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V)); 82 if (!C) 83 return nullptr; 84 85 if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) { 86 Function *F = 87 cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper, Materializer)); 88 BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(), VM, 89 Flags, TypeMapper, Materializer)); 90 return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock()); 91 } 92 93 // Otherwise, we have some other constant to remap. Start by checking to see 94 // if all operands have an identity remapping. 95 unsigned OpNo = 0, NumOperands = C->getNumOperands(); 96 Value *Mapped = nullptr; 97 for (; OpNo != NumOperands; ++OpNo) { 98 Value *Op = C->getOperand(OpNo); 99 Mapped = MapValue(Op, VM, Flags, TypeMapper, Materializer); 100 if (Mapped != C) break; 101 } 102 103 // See if the type mapper wants to remap the type as well. 104 Type *NewTy = C->getType(); 105 if (TypeMapper) 106 NewTy = TypeMapper->remapType(NewTy); 107 108 // If the result type and all operands match up, then just insert an identity 109 // mapping. 110 if (OpNo == NumOperands && NewTy == C->getType()) 111 return VM[V] = C; 112 113 // Okay, we need to create a new constant. We've already processed some or 114 // all of the operands, set them all up now. 115 SmallVector<Constant*, 8> Ops; 116 Ops.reserve(NumOperands); 117 for (unsigned j = 0; j != OpNo; ++j) 118 Ops.push_back(cast<Constant>(C->getOperand(j))); 119 120 // If one of the operands mismatch, push it and the other mapped operands. 121 if (OpNo != NumOperands) { 122 Ops.push_back(cast<Constant>(Mapped)); 123 124 // Map the rest of the operands that aren't processed yet. 125 for (++OpNo; OpNo != NumOperands; ++OpNo) 126 Ops.push_back(MapValue(cast<Constant>(C->getOperand(OpNo)), VM, 127 Flags, TypeMapper, Materializer)); 128 } 129 130 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 131 return VM[V] = CE->getWithOperands(Ops, NewTy); 132 if (isa<ConstantArray>(C)) 133 return VM[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops); 134 if (isa<ConstantStruct>(C)) 135 return VM[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops); 136 if (isa<ConstantVector>(C)) 137 return VM[V] = ConstantVector::get(Ops); 138 // If this is a no-operand constant, it must be because the type was remapped. 139 if (isa<UndefValue>(C)) 140 return VM[V] = UndefValue::get(NewTy); 141 if (isa<ConstantAggregateZero>(C)) 142 return VM[V] = ConstantAggregateZero::get(NewTy); 143 assert(isa<ConstantPointerNull>(C)); 144 return VM[V] = ConstantPointerNull::get(cast<PointerType>(NewTy)); 145 } 146 147 static Metadata *mapToMetadata(ValueToValueMapTy &VM, const Metadata *Key, 148 Metadata *Val) { 149 VM.MD()[Key].reset(Val); 150 return Val; 151 } 152 153 static Metadata *mapToSelf(ValueToValueMapTy &VM, const Metadata *MD) { 154 return mapToMetadata(VM, MD, const_cast<Metadata *>(MD)); 155 } 156 157 static Metadata *MapMetadataImpl(const Metadata *MD, 158 SmallVectorImpl<MDNode *> &Cycles, 159 ValueToValueMapTy &VM, RemapFlags Flags, 160 ValueMapTypeRemapper *TypeMapper, 161 ValueMaterializer *Materializer); 162 163 static Metadata *mapMetadataOp(Metadata *Op, SmallVectorImpl<MDNode *> &Cycles, 164 ValueToValueMapTy &VM, RemapFlags Flags, 165 ValueMapTypeRemapper *TypeMapper, 166 ValueMaterializer *Materializer) { 167 if (!Op) 168 return nullptr; 169 if (Metadata *MappedOp = 170 MapMetadataImpl(Op, Cycles, VM, Flags, TypeMapper, Materializer)) 171 return MappedOp; 172 // Use identity map if MappedOp is null and we can ignore missing entries. 173 if (Flags & RF_IgnoreMissingEntries) 174 return Op; 175 176 // FIXME: This assert crashes during bootstrap, but I think it should be 177 // correct. For now, just match behaviour from before the metadata/value 178 // split. 179 // 180 // llvm_unreachable("Referenced metadata not in value map!"); 181 return nullptr; 182 } 183 184 /// \brief Remap nodes. 185 /// 186 /// Insert \c NewNode in the value map, and then remap \c OldNode's operands. 187 /// Assumes that \c NewNode is already a clone of \c OldNode. 188 /// 189 /// \pre \c NewNode is a clone of \c OldNode. 190 static bool remap(const MDNode *OldNode, MDNode *NewNode, 191 SmallVectorImpl<MDNode *> &Cycles, ValueToValueMapTy &VM, 192 RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, 193 ValueMaterializer *Materializer) { 194 assert(OldNode->getNumOperands() == NewNode->getNumOperands() && 195 "Expected nodes to match"); 196 assert(OldNode->isResolved() && "Expected resolved node"); 197 assert(!NewNode->isUniqued() && "Expected non-uniqued node"); 198 199 // Map the node upfront so it's available for cyclic references. 200 mapToMetadata(VM, OldNode, NewNode); 201 bool AnyChanged = false; 202 for (unsigned I = 0, E = OldNode->getNumOperands(); I != E; ++I) { 203 Metadata *Old = OldNode->getOperand(I); 204 assert(NewNode->getOperand(I) == Old && 205 "Expected old operands to already be in place"); 206 207 Metadata *New = mapMetadataOp(OldNode->getOperand(I), Cycles, VM, Flags, 208 TypeMapper, Materializer); 209 if (Old != New) { 210 AnyChanged = true; 211 NewNode->replaceOperandWith(I, New); 212 } 213 } 214 215 return AnyChanged; 216 } 217 218 /// \brief Map a distinct MDNode. 219 /// 220 /// Distinct nodes are not uniqued, so they must always recreated. 221 static Metadata *mapDistinctNode(const MDNode *Node, 222 SmallVectorImpl<MDNode *> &Cycles, 223 ValueToValueMapTy &VM, RemapFlags Flags, 224 ValueMapTypeRemapper *TypeMapper, 225 ValueMaterializer *Materializer) { 226 assert(Node->isDistinct() && "Expected distinct node"); 227 228 MDNode *NewMD = MDNode::replaceWithDistinct(Node->clone()); 229 remap(Node, NewMD, Cycles, VM, Flags, TypeMapper, Materializer); 230 231 // Track any cycles beneath this node. 232 for (Metadata *Op : NewMD->operands()) 233 if (auto *Node = dyn_cast_or_null<MDNode>(Op)) 234 if (!Node->isResolved()) 235 Cycles.push_back(Node); 236 237 return NewMD; 238 } 239 240 /// \brief Map a uniqued MDNode. 241 /// 242 /// Uniqued nodes may not need to be recreated (they may map to themselves). 243 static Metadata *mapUniquedNode(const MDNode *Node, 244 SmallVectorImpl<MDNode *> &Cycles, 245 ValueToValueMapTy &VM, RemapFlags Flags, 246 ValueMapTypeRemapper *TypeMapper, 247 ValueMaterializer *Materializer) { 248 assert(Node->isUniqued() && "Expected uniqued node"); 249 250 // Create a temporary node upfront in case we have a metadata cycle. 251 auto ClonedMD = Node->clone(); 252 if (!remap(Node, ClonedMD.get(), Cycles, VM, Flags, TypeMapper, Materializer)) 253 // No operands changed, so use the identity mapping. 254 return mapToSelf(VM, Node); 255 256 // At least one operand has changed, so uniquify the cloned node. 257 return mapToMetadata(VM, Node, 258 MDNode::replaceWithUniqued(std::move(ClonedMD))); 259 } 260 261 static Metadata *MapMetadataImpl(const Metadata *MD, 262 SmallVectorImpl<MDNode *> &Cycles, 263 ValueToValueMapTy &VM, RemapFlags Flags, 264 ValueMapTypeRemapper *TypeMapper, 265 ValueMaterializer *Materializer) { 266 // If the value already exists in the map, use it. 267 if (Metadata *NewMD = VM.MD().lookup(MD).get()) 268 return NewMD; 269 270 if (isa<MDString>(MD)) 271 return mapToSelf(VM, MD); 272 273 if (isa<ConstantAsMetadata>(MD)) 274 if ((Flags & RF_NoModuleLevelChanges)) 275 return mapToSelf(VM, MD); 276 277 if (const auto *VMD = dyn_cast<ValueAsMetadata>(MD)) { 278 Value *MappedV = 279 MapValue(VMD->getValue(), VM, Flags, TypeMapper, Materializer); 280 if (VMD->getValue() == MappedV || 281 (!MappedV && (Flags & RF_IgnoreMissingEntries))) 282 return mapToSelf(VM, MD); 283 284 // FIXME: This assert crashes during bootstrap, but I think it should be 285 // correct. For now, just match behaviour from before the metadata/value 286 // split. 287 // 288 // assert(MappedV && "Referenced metadata not in value map!"); 289 if (MappedV) 290 return mapToMetadata(VM, MD, ValueAsMetadata::get(MappedV)); 291 return nullptr; 292 } 293 294 // Note: this cast precedes the Flags check so we always get its associated 295 // assertion. 296 const MDNode *Node = cast<MDNode>(MD); 297 298 // If this is a module-level metadata and we know that nothing at the 299 // module level is changing, then use an identity mapping. 300 if (Flags & RF_NoModuleLevelChanges) 301 return mapToSelf(VM, MD); 302 303 // Require resolved nodes whenever metadata might be remapped. 304 assert(Node->isResolved() && "Unexpected unresolved node"); 305 306 if (Node->isDistinct()) 307 return mapDistinctNode(Node, Cycles, VM, Flags, TypeMapper, Materializer); 308 309 return mapUniquedNode(Node, Cycles, VM, Flags, TypeMapper, Materializer); 310 } 311 312 Metadata *llvm::MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, 313 RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, 314 ValueMaterializer *Materializer) { 315 SmallVector<MDNode *, 8> Cycles; 316 Metadata *NewMD = 317 MapMetadataImpl(MD, Cycles, VM, Flags, TypeMapper, Materializer); 318 319 // Resolve cycles underneath MD. 320 if (NewMD && NewMD != MD) { 321 if (auto *N = dyn_cast<MDNode>(NewMD)) 322 if (!N->isResolved()) 323 N->resolveCycles(); 324 325 for (MDNode *N : Cycles) 326 if (!N->isResolved()) 327 N->resolveCycles(); 328 } else { 329 // Shouldn't get unresolved cycles if nothing was remapped. 330 assert(Cycles.empty() && "Expected no unresolved cycles"); 331 } 332 333 return NewMD; 334 } 335 336 MDNode *llvm::MapMetadata(const MDNode *MD, ValueToValueMapTy &VM, 337 RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, 338 ValueMaterializer *Materializer) { 339 return cast<MDNode>(MapMetadata(static_cast<const Metadata *>(MD), VM, Flags, 340 TypeMapper, Materializer)); 341 } 342 343 /// RemapInstruction - Convert the instruction operands from referencing the 344 /// current values into those specified by VMap. 345 /// 346 void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, 347 RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, 348 ValueMaterializer *Materializer){ 349 // Remap operands. 350 for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) { 351 Value *V = MapValue(*op, VMap, Flags, TypeMapper, Materializer); 352 // If we aren't ignoring missing entries, assert that something happened. 353 if (V) 354 *op = V; 355 else 356 assert((Flags & RF_IgnoreMissingEntries) && 357 "Referenced value not in value map!"); 358 } 359 360 // Remap phi nodes' incoming blocks. 361 if (PHINode *PN = dyn_cast<PHINode>(I)) { 362 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 363 Value *V = MapValue(PN->getIncomingBlock(i), VMap, Flags); 364 // If we aren't ignoring missing entries, assert that something happened. 365 if (V) 366 PN->setIncomingBlock(i, cast<BasicBlock>(V)); 367 else 368 assert((Flags & RF_IgnoreMissingEntries) && 369 "Referenced block not in value map!"); 370 } 371 } 372 373 // Remap attached metadata. 374 SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; 375 I->getAllMetadata(MDs); 376 for (SmallVectorImpl<std::pair<unsigned, MDNode *>>::iterator 377 MI = MDs.begin(), 378 ME = MDs.end(); 379 MI != ME; ++MI) { 380 MDNode *Old = MI->second; 381 MDNode *New = MapMetadata(Old, VMap, Flags, TypeMapper, Materializer); 382 if (New != Old) 383 I->setMetadata(MI->first, New); 384 } 385 386 // If the instruction's type is being remapped, do so now. 387 if (TypeMapper) 388 I->mutateType(TypeMapper->remapType(I->getType())); 389 } 390
