151cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner//===- ValueMapper.cpp - Interface shared by lib/Transforms/Utils ---------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 951cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner// 1051cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner// This file defines the MapValue function, which is shared by various parts of 1151cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner// the lib/Transforms/Utils library. 1251cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner// 1351cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner//===----------------------------------------------------------------------===// 1451cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner 1505ea54e8869a81b8dd846397175f218f97968907Dan Gohman#include "llvm/Transforms/Utils/ValueMapper.h" 1651cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner#include "llvm/Constants.h" 171bb95911de8d0821aff16bf0cb1e1dfe43856bf1Chris Lattner#include "llvm/Function.h" 187305c55a806e550020c0fd78239b587da222f600Chris Lattner#include "llvm/InlineAsm.h" 1995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad#include "llvm/Instructions.h" 200a9f7b9c3ebe7d0ec033462e1a7c9101279956f9Devang Patel#include "llvm/Metadata.h" 21f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 2251cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner 231afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner// Out of line method to get vtable etc for class. 241afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattnervoid ValueMapTypeRemapper::Anchor() {} 251afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 261afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris LattnerValue *llvm::MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags, 271afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner ValueMapTypeRemapper *TypeMapper) { 28b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner ValueToValueMapTy::iterator I = VM.find(V); 29b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner 30b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // If the value already exists in the map, use it. 31b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner if (I != VM.end() && I->second) return I->second; 325e665f559419c7f58a4fd9360cd488f065505c44Chris Lattner 336cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman // Global values do not need to be seeded into the VM if they 346cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman // are using the identity mapping. 357305c55a806e550020c0fd78239b587da222f600Chris Lattner if (isa<GlobalValue>(V) || isa<MDString>(V)) 36b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner return VM[V] = const_cast<Value*>(V); 377305c55a806e550020c0fd78239b587da222f600Chris Lattner 387305c55a806e550020c0fd78239b587da222f600Chris Lattner if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) { 397305c55a806e550020c0fd78239b587da222f600Chris Lattner // Inline asm may need *type* remapping. 407305c55a806e550020c0fd78239b587da222f600Chris Lattner FunctionType *NewTy = IA->getFunctionType(); 417305c55a806e550020c0fd78239b587da222f600Chris Lattner if (TypeMapper) { 427305c55a806e550020c0fd78239b587da222f600Chris Lattner NewTy = cast<FunctionType>(TypeMapper->remapType(NewTy)); 437305c55a806e550020c0fd78239b587da222f600Chris Lattner 447305c55a806e550020c0fd78239b587da222f600Chris Lattner if (NewTy != IA->getFunctionType()) 457305c55a806e550020c0fd78239b587da222f600Chris Lattner V = InlineAsm::get(NewTy, IA->getAsmString(), IA->getConstraintString(), 467305c55a806e550020c0fd78239b587da222f600Chris Lattner IA->hasSideEffects(), IA->isAlignStack()); 477305c55a806e550020c0fd78239b587da222f600Chris Lattner } 487305c55a806e550020c0fd78239b587da222f600Chris Lattner 497305c55a806e550020c0fd78239b587da222f600Chris Lattner return VM[V] = const_cast<Value*>(V); 507305c55a806e550020c0fd78239b587da222f600Chris Lattner } 517305c55a806e550020c0fd78239b587da222f600Chris Lattner 525f92e2b11f68624f9003e710f44e3bc324cbf89aChris Lattner 531b3ef34b759434624bb0c194c2d368ba7617c3a9Chris Lattner if (const MDNode *MD = dyn_cast<MDNode>(V)) { 54b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // If this is a module-level metadata and we know that nothing at the module 55b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // level is changing, then use an identity mapping. 56b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner if (!MD->isFunctionLocal() && (Flags & RF_NoModuleLevelChanges)) 57b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner return VM[V] = const_cast<Value*>(V); 58b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner 5951e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner // Create a dummy node in case we have a metadata cycle. 60ec9186bcf975c9ffa3ec7ca97867f0ec6eb55115Jay Foad MDNode *Dummy = MDNode::getTemporary(V->getContext(), ArrayRef<Value*>()); 6151e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner VM[V] = Dummy; 6251e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner 636cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman // Check all operands to see if any need to be remapped. 646cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) { 656cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman Value *OP = MD->getOperand(i); 661afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (OP == 0 || MapValue(OP, VM, Flags, TypeMapper) == OP) continue; 676cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman 6851e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner // Ok, at least one operand needs remapping. 696cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman SmallVector<Value*, 4> Elts; 706cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman Elts.reserve(MD->getNumOperands()); 71b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner for (i = 0; i != e; ++i) { 72b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner Value *Op = MD->getOperand(i); 731afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Elts.push_back(Op ? MapValue(Op, VM, Flags, TypeMapper) : 0); 74b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner } 75ec9186bcf975c9ffa3ec7ca97867f0ec6eb55115Jay Foad MDNode *NewMD = MDNode::get(V->getContext(), Elts); 766cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman Dummy->replaceAllUsesWith(NewMD); 7751e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner VM[V] = NewMD; 786cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman MDNode::deleteTemporary(Dummy); 7951e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner return NewMD; 806cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman } 816cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman 8251e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner VM[V] = const_cast<Value*>(V); 8351e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner MDNode::deleteTemporary(Dummy); 8451e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner 85b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // No operands needed remapping. Use an identity mapping. 8651e62f0f73b2d2a32c2a5b98402114e4c71dc14fChris Lattner return const_cast<Value*>(V); 87f58c34d5315a35d489c5c203ae45430ccb53f973Victor Hernandez } 88f58c34d5315a35d489c5c203ae45430ccb53f973Victor Hernandez 89b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // Okay, this either must be a constant (which may or may not be mappable) or 90b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // is something that is not in the mapping table. 9177488ccc6305760af485c884872368c7a490ab84Chris Lattner Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V)); 926cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman if (C == 0) 936cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman return 0; 9477488ccc6305760af485c884872368c7a490ab84Chris Lattner 95b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) { 961afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Function *F = 971afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner cast<Function>(MapValue(BA->getFunction(), VM, Flags, TypeMapper)); 98b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(), VM, 991afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Flags, TypeMapper)); 100b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock()); 10177488ccc6305760af485c884872368c7a490ab84Chris Lattner } 10277488ccc6305760af485c884872368c7a490ab84Chris Lattner 1031afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Otherwise, we have some other constant to remap. Start by checking to see 1041afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // if all operands have an identity remapping. 1051afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner unsigned OpNo = 0, NumOperands = C->getNumOperands(); 1061afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Value *Mapped = 0; 1071afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner for (; OpNo != NumOperands; ++OpNo) { 1081afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Value *Op = C->getOperand(OpNo); 1091afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Mapped = MapValue(Op, VM, Flags, TypeMapper); 1101afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (Mapped != C) break; 1111afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner } 1121afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1131afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // See if the type mapper wants to remap the type as well. 1141afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Type *NewTy = C->getType(); 1151afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (TypeMapper) 1161afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner NewTy = TypeMapper->remapType(NewTy); 1171afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1181afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If the result type and all operands match up, then just insert an identity 1191afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // mapping. 1201afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (OpNo == NumOperands && NewTy == C->getType()) 1211afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = C; 1221afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1231afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Okay, we need to create a new constant. We've already processed some or 1241afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // all of the operands, set them all up now. 1251afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner SmallVector<Constant*, 8> Ops; 1261afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Ops.reserve(NumOperands); 1271afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner for (unsigned j = 0; j != OpNo; ++j) 1281afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Ops.push_back(cast<Constant>(C->getOperand(j))); 1291afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1301afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If one of the operands mismatch, push it and the other mapped operands. 1311afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (OpNo != NumOperands) { 132b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner Ops.push_back(cast<Constant>(Mapped)); 1331afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 134b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // Map the rest of the operands that aren't processed yet. 1351afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner for (++OpNo; OpNo != NumOperands; ++OpNo) 1361afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Ops.push_back(MapValue(cast<Constant>(C->getOperand(OpNo)), VM, 1371afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Flags, TypeMapper)); 1381bb95911de8d0821aff16bf0cb1e1dfe43856bf1Chris Lattner } 1391afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1401afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 1411afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = CE->getWithOperands(Ops, NewTy); 1421afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (isa<ConstantArray>(C)) 1431afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = ConstantArray::get(cast<ArrayType>(NewTy), Ops); 1441afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (isa<ConstantStruct>(C)) 1451afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = ConstantStruct::get(cast<StructType>(NewTy), Ops); 1461afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (isa<ConstantVector>(C)) 1471afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = ConstantVector::get(Ops); 1481afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If this is a no-operand constant, it must be because the type was remapped. 1491afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (isa<UndefValue>(C)) 1501afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = UndefValue::get(NewTy); 1511afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (isa<ConstantAggregateZero>(C)) 1521afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = ConstantAggregateZero::get(NewTy); 1531afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner assert(isa<ConstantPointerNull>(C)); 1541afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return VM[V] = ConstantPointerNull::get(cast<PointerType>(NewTy)); 15551cbcbf435d1aaa1a5269d62b5d0b31b57316b4aChris Lattner} 1566129af3fb14d1050f9fb4800c787e6f930b910d1Brian Gaeke 1576129af3fb14d1050f9fb4800c787e6f930b910d1Brian Gaeke/// RemapInstruction - Convert the instruction operands from referencing the 15829d3dd8a64791031eea00ffbae51843dc9982df9Devang Patel/// current values into those specified by VMap. 1596129af3fb14d1050f9fb4800c787e6f930b910d1Brian Gaeke/// 1606cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohmanvoid llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, 1611afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner RemapFlags Flags, ValueMapTypeRemapper *TypeMapper){ 1626cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman // Remap operands. 163ba2c4874244f449ce04a72b542144d5c3f7ff50dGabor Greif for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) { 1641afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Value *V = MapValue(*op, VMap, Flags, TypeMapper); 165b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner // If we aren't ignoring missing entries, assert that something happened. 166b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner if (V != 0) 167b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner *op = V; 168b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner else 169b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner assert((Flags & RF_IgnoreMissingEntries) && 170b5fa5fcecc97168a72c9533c84cf297c018b957cChris Lattner "Referenced value not in value map!"); 1716129af3fb14d1050f9fb4800c787e6f930b910d1Brian Gaeke } 172fd406f1ee2d94bafcb4943e4b21c2f4ea4bd8f3aDaniel Dunbar 17395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Remap phi nodes' incoming blocks. 17495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (PHINode *PN = dyn_cast<PHINode>(I)) { 17595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 17695c3e48f9557adb6064d580684bb14cacec2f826Jay Foad Value *V = MapValue(PN->getIncomingBlock(i), VMap, Flags); 17795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // If we aren't ignoring missing entries, assert that something happened. 17895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (V != 0) 17995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PN->setIncomingBlock(i, cast<BasicBlock>(V)); 18095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad else 18195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad assert((Flags & RF_IgnoreMissingEntries) && 18295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad "Referenced block not in value map!"); 18395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad } 18495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad } 18595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 1861f35b178858c693261b08ab41022f92e250e08b4Devang Patel // Remap attached metadata. 1876cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; 1881f35b178858c693261b08ab41022f92e250e08b4Devang Patel I->getAllMetadata(MDs); 1896cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator 1906cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) { 1911afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner MDNode *Old = MI->second; 1921afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner MDNode *New = MapValue(Old, VMap, Flags, TypeMapper); 1936cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman if (New != Old) 1941afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner I->setMetadata(MI->first, New); 1956cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman } 1961afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner 1971afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If the instruction's type is being remapped, do so now. 1981afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (TypeMapper) 1991afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner I->mutateType(TypeMapper->remapType(I->getType())); 2006cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman} 201