1fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner//===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===// 2fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// 3fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// The LLVM Compiler Infrastructure 4fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// 8fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner//===----------------------------------------------------------------------===// 9fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// 10fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// This file implements the ValueEnumerator class. 11fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner// 12fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner//===----------------------------------------------------------------------===// 13fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 14fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner#include "ValueEnumerator.h" 15f5a90561b033428bd2c5b365ca09ed9e688dce6eRafael Espindola#include "llvm/ADT/STLExtras.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/ValueSymbolTable.h" 224e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier#include "llvm/Support/Debug.h" 234e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier#include "llvm/Support/raw_ostream.h" 2412f535b937cb35a5cc2b3cc67995f09b9e8e1326Chris Lattner#include <algorithm> 25fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattnerusing namespace llvm; 26fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 272333e29be441d9d55920651e0b2add23ab0c1613Duncan Sandsstatic bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { 282333e29be441d9d55920651e0b2add23ab0c1613Duncan Sands return V.first->getType()->isIntOrIntVectorTy(); 296da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner} 306da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner 31fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner/// ValueEnumerator - Enumerate module-level information. 32fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris LattnerValueEnumerator::ValueEnumerator(const Module *M) { 33fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Enumerate the global variables. 34fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner for (Module::const_global_iterator I = M->global_begin(), 35fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner E = M->global_end(); I != E; ++I) 36fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateValue(I); 37fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 38fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Enumerate the functions. 39dc024674ff96820d6020757b48d47f46d4c07db2Duncan Sands for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { 40fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateValue(I); 410598866c052147c31b808391f58434ce3dbfb838Devang Patel EnumerateAttributes(cast<Function>(I)->getAttributes()); 42dc024674ff96820d6020757b48d47f46d4c07db2Duncan Sands } 43fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 4407d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner // Enumerate the aliases. 4507d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 4607d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner I != E; ++I) 4707d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner EnumerateValue(I); 48a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 496da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner // Remember what is the cutoff between globalvalue's and other constants. 506da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner unsigned FirstConstant = Values.size(); 51a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 52fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Enumerate the global variable initializers. 53fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner for (Module::const_global_iterator I = M->global_begin(), 54fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner E = M->global_end(); I != E; ++I) 55fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner if (I->hasInitializer()) 56fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateValue(I->getInitializer()); 57fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 5807d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner // Enumerate the aliasees. 5907d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 6007d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner I != E; ++I) 6107d98b4afbdcbb4eed048400d9116de1ec83e866Chris Lattner EnumerateValue(I->getAliasee()); 62a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 631e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne // Enumerate the prefix data constants. 641e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) 651e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne if (I->hasPrefixData()) 661e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne EnumerateValue(I->getPrefixData()); 671e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne 68ef7964c1b78f57e277e74bda4f38e1143d1363feJoe Abbey // Insert constants and metadata that are named at module level into the slot 690386f01e061513094504bc11f8352a40173cada7Devang Patel // pool so that the module symbol table can refer to them... 70fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateValueSymbolTable(M->getValueSymbolTable()); 7117aa92c92a925b4a674440c7ef088c223990e854Dan Gohman EnumerateNamedMetadata(M); 72a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 73cc7b011728b9e8c3574247b81f79689840b3d33aChris Lattner SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; 74cc7b011728b9e8c3574247b81f79689840b3d33aChris Lattner 758d35c79f273b74df1e95b4472620e31e81342037Chris Lattner // Enumerate types used by function bodies and argument lists. 76cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (const Function &F : *M) { 77cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (const Argument &A : F.args()) 78cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EnumerateType(A.getType()); 79cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 80cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (const BasicBlock &BB : F) 81cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (const Instruction &I : BB) { 82cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (const Use &Op : I.operands()) { 83cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (MDNode *MD = dyn_cast<MDNode>(&Op)) 842b3365ca1dd53b078714ec99b5b2ea6b67b23c9cVictor Hernandez if (MD->isFunctionLocal() && MD->getFunction()) 85d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez // These will get enumerated during function-incorporation. 86d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez continue; 87cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EnumerateOperandType(Op); 88d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez } 89cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EnumerateType(I.getType()); 90cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (const CallInst *CI = dyn_cast<CallInst>(&I)) 910598866c052147c31b808391f58434ce3dbfb838Devang Patel EnumerateAttributes(CI->getAttributes()); 92cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) 930598866c052147c31b808391f58434ce3dbfb838Devang Patel EnumerateAttributes(II->getAttributes()); 94e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel 95a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar // Enumerate metadata attached with this instruction. 96f61b2371c8ec6e0ff2da8f2bd2a606ba755bb2feDevang Patel MDs.clear(); 97cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines I.getAllMetadataOtherThanDebugLoc(MDs); 983990b121cf4a0b280ed3e54cf13870cbf4259e78Chris Lattner for (unsigned i = 0, e = MDs.size(); i != e; ++i) 99d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez EnumerateMetadata(MDs[i].second); 100170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 101cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!I.getDebugLoc().isUnknown()) { 102a6245247e9d0c718fb14230ba6610ee939b030faChris Lattner MDNode *Scope, *IA; 103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines I.getDebugLoc().getScopeAndInlinedAt(Scope, IA, I.getContext()); 104a6245247e9d0c718fb14230ba6610ee939b030faChris Lattner if (Scope) EnumerateMetadata(Scope); 105a6245247e9d0c718fb14230ba6610ee939b030faChris Lattner if (IA) EnumerateMetadata(IA); 106a6245247e9d0c718fb14230ba6610ee939b030faChris Lattner } 107fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner } 108fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner } 109a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 1106da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner // Optimize constant ordering. 1116da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner OptimizeConstants(FirstConstant, Values.size()); 112f5a90561b033428bd2c5b365ca09ed9e688dce6eRafael Espindola} 113f5a90561b033428bd2c5b365ca09ed9e688dce6eRafael Espindola 114e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patelunsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { 115e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel InstructionMapType::const_iterator I = InstructionMap.find(Inst); 1161afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner assert(I != InstructionMap.end() && "Instruction is not mapped!"); 1175c18fa2736a603e0144c90b02a9581220c42b52dDan Gohman return I->second; 118a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar} 119e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel 120cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesunsigned ValueEnumerator::getComdatID(const Comdat *C) const { 121cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned ComdatID = Comdats.idFor(C); 122cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(ComdatID && "Comdat not found!"); 123cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ComdatID; 124cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 125cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 126e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patelvoid ValueEnumerator::setInstructionID(const Instruction *I) { 127e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel InstructionMap[I] = InstructionCount++; 128e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel} 129e8e0213cc3daa2d0457c22e4c12e6973f21fc942Devang Patel 130d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patelunsigned ValueEnumerator::getValueID(const Value *V) const { 131bc5201f8371f9041e79efcca3b158335da5c2604Devang Patel if (isa<MDNode>(V) || isa<MDString>(V)) { 132d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel ValueMapType::const_iterator I = MDValueMap.find(V); 133d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel assert(I != MDValueMap.end() && "Value not in slotcalculator!"); 134d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel return I->second-1; 135d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel } 136a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 137d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel ValueMapType::const_iterator I = ValueMap.find(V); 138d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel assert(I != ValueMap.end() && "Value not in slotcalculator!"); 139d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel return I->second-1; 140d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel} 141a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 1424e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosiervoid ValueEnumerator::dump() const { 1434e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier print(dbgs(), ValueMap, "Default"); 1444e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier dbgs() << '\n'; 1454e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier print(dbgs(), MDValueMap, "MetaData"); 1464e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier dbgs() << '\n'; 1474e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier} 1484e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1494e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosiervoid ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, 1504e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier const char *Name) const { 1514e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1524e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << "Map Name: " << Name << "\n"; 1534e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << "Size: " << Map.size() << "\n"; 1544e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier for (ValueMapType::const_iterator I = Map.begin(), 1554e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier E = Map.end(); I != E; ++I) { 1564e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1574e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier const Value *V = I->first; 1584e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier if (V->hasName()) 1594e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << "Value: " << V->getName(); 1604e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier else 1614e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << "Value: [null]\n"; 1624e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier V->dump(); 1634e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1644e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):"; 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const Use &U : V->uses()) { 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (&U != &*V->use_begin()) 1674e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << ","; 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if(U->hasName()) 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << " " << U->getName(); 1704e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier else 1714e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << " [null]"; 1724e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1734e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier } 1744e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier OS << "\n\n"; 1754e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier } 1764e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier} 1774e6c03fc3de8885b9a0a0b8069123b86d4834f08Chad Rosier 1786da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner/// OptimizeConstants - Reorder constant pool for denser encoding. 1796da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattnervoid ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 1806da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 181a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd, 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines [this](const std::pair<const Value *, unsigned> &LHS, 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const std::pair<const Value *, unsigned> &RHS) { 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Sort by plane. 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (LHS.first->getType() != RHS.first->getType()) 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType()); 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Then by frequency. 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return LHS.second > RHS.second; 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 191a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 1922333e29be441d9d55920651e0b2add23ab0c1613Duncan Sands // Ensure that integer and vector of integer constants are at the start of the 1932333e29be441d9d55920651e0b2add23ab0c1613Duncan Sands // constant pool. This is important so that GEP structure indices come before 1942333e29be441d9d55920651e0b2add23ab0c1613Duncan Sands // gep constant exprs. 1956da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, 1962333e29be441d9d55920651e0b2add23ab0c1613Duncan Sands isIntOrIntVectorValue); 197a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 1986da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner // Rebuild the modified portion of ValueMap. 1996da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner for (; CstStart != CstEnd; ++CstStart) 2006da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner ValueMap[Values[CstStart].first] = CstStart+1; 2016da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner} 2026da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner 2036da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner 204fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 205fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner/// table into the values table. 206fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattnervoid ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 207a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 208fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner VI != VE; ++VI) 209fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateValue(VI->getValue()); 210fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner} 211fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 21217aa92c92a925b4a674440c7ef088c223990e854Dan Gohman/// EnumerateNamedMetadata - Insert all of the values referenced by 21317aa92c92a925b4a674440c7ef088c223990e854Dan Gohman/// named metadata in the specified module. 21417aa92c92a925b4a674440c7ef088c223990e854Dan Gohmanvoid ValueEnumerator::EnumerateNamedMetadata(const Module *M) { 21517aa92c92a925b4a674440c7ef088c223990e854Dan Gohman for (Module::const_named_metadata_iterator I = M->named_metadata_begin(), 21617aa92c92a925b4a674440c7ef088c223990e854Dan Gohman E = M->named_metadata_end(); I != E; ++I) 21717aa92c92a925b4a674440c7ef088c223990e854Dan Gohman EnumerateNamedMDNode(I); 2180386f01e061513094504bc11f8352a40173cada7Devang Patel} 2190386f01e061513094504bc11f8352a40173cada7Devang Patel 2208fba578be72dc98497508dec053e966858571f6aDevang Patelvoid ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { 2218fba578be72dc98497508dec053e966858571f6aDevang Patel for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) 222078b05320a0bad930332a2071832c2bb725ce4a5Dan Gohman EnumerateMetadata(MD->getOperand(i)); 2238fba578be72dc98497508dec053e966858571f6aDevang Patel} 2248fba578be72dc98497508dec053e966858571f6aDevang Patel 225309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman/// EnumerateMDNodeOperands - Enumerate all non-function-local values 226309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman/// and types referenced by the given MDNode. 227309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohmanvoid ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { 228309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 229309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (Value *V = N->getOperand(i)) { 230309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (isa<MDNode>(V) || isa<MDString>(V)) 231309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateMetadata(V); 232309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman else if (!isa<Instruction>(V) && !isa<Argument>(V)) 233309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateValue(V); 234309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman } else 235309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateType(Type::getVoidTy(N->getContext())); 236309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman } 237309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman} 238309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 239bc5201f8371f9041e79efcca3b158335da5c2604Devang Patelvoid ValueEnumerator::EnumerateMetadata(const Value *MD) { 240e88a8e6fbf4ea8163eebdbc2f72fa08d72a02532Benjamin Kramer assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind"); 241309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 242309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // Enumerate the type of this value. 243309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateType(MD->getType()); 244309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 245309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman const MDNode *N = dyn_cast<MDNode>(MD); 246309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 247309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // In the module-level pass, skip function-local nodes themselves, but 248309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // do walk their operands. 249309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (N && N->isFunctionLocal() && N->getFunction()) { 250309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateMDNodeOperands(N); 251309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman return; 252309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman } 253309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 254d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel // Check to see if it's already in! 255d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel unsigned &MDValueID = MDValueMap[MD]; 256d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel if (MDValueID) { 257d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel // Increment use count. 258d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel MDValues[MDValueID-1].second++; 259d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel return; 260d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel } 261309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValues.push_back(std::make_pair(MD, 1U)); 262309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValueID = MDValues.size(); 263309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 264309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // Enumerate all non-function-local operands. 265309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (N) 266309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateMDNodeOperands(N); 267309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman} 268309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 269309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman/// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata 270309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman/// information reachable from the given MDNode. 271309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohmanvoid ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) { 272309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman assert(N->isFunctionLocal() && N->getFunction() && 273309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman "EnumerateFunctionLocalMetadata called on non-function-local mdnode!"); 274d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel 275d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel // Enumerate the type of this value. 276309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateType(N->getType()); 277d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel 278309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // Check to see if it's already in! 279309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman unsigned &MDValueID = MDValueMap[N]; 280309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (MDValueID) { 281309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // Increment use count. 282309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValues[MDValueID-1].second++; 283d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel return; 284837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner } 285309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValues.push_back(std::make_pair(N, 1U)); 286d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel MDValueID = MDValues.size(); 287309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 288309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // To incoroporate function-local information visit all function-local 289309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // MDNodes and all function-local values they reference. 290309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 291309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (Value *V = N->getOperand(i)) { 292d01347e0808f1d06b92d04bd9c0798df0d024879Dan Gohman if (MDNode *O = dyn_cast<MDNode>(V)) { 293309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (O->isFunctionLocal() && O->getFunction()) 294309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateFunctionLocalMetadata(O); 295d01347e0808f1d06b92d04bd9c0798df0d024879Dan Gohman } else if (isa<Instruction>(V) || isa<Argument>(V)) 296309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateValue(V); 297309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman } 298309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 299309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman // Also, collect all function-local MDNodes for easy access. 300309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman FunctionLocalMDs.push_back(N); 301d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel} 302d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel 303d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandezvoid ValueEnumerator::EnumerateValue(const Value *V) { 304cc7b011728b9e8c3574247b81f79689840b3d33aChris Lattner assert(!V->getType()->isVoidTy() && "Can't insert void values!"); 305309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman assert(!isa<MDNode>(V) && !isa<MDString>(V) && 306309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman "EnumerateValue doesn't handle Metadata!"); 307d5ac40457b62f37f0abfb1d61064f7c7300e91eeDevang Patel 308fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Check to see if it's already in! 309fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner unsigned &ValueID = ValueMap[V]; 310fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner if (ValueID) { 311fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Increment use count. 312fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner Values[ValueID-1].second++; 313fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner return; 314fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner } 315fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 316cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (auto *GO = dyn_cast<GlobalObject>(V)) 317cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (const Comdat *C = GO->getComdat()) 318cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Comdats.insert(C); 319cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 3207a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // Enumerate the type of this value. 3217a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner EnumerateType(V->getType()); 322a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 323fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner if (const Constant *C = dyn_cast<Constant>(V)) { 324fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner if (isa<GlobalValue>(C)) { 325fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner // Initializers for globals are handled explicitly elsewhere. 3267a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner } else if (C->getNumOperands()) { 3277a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // If a constant has operands, enumerate them. This makes sure that if a 3287a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // constant has uses (for example an array of const ints), that they are 3297a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // inserted also. 330a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 3317a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // We prefer to enumerate them with values before we enumerate the user 3327a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // itself. This makes it more likely that we can avoid forward references 3337a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // in the reader. We know that there can be no cycles in the constants 3347a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // graph that don't go through a global variable. 335fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 336fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner I != E; ++I) 337cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. 338d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez EnumerateValue(*I); 339a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 3407a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // Finally, add the value. Doing this could make the ValueID reference be 3417a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // dangling, don't reuse it. 3427a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner Values.push_back(std::make_pair(V, 1U)); 3437a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner ValueMap[V] = Values.size(); 3447a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner return; 345104cf9e02b0ed94d4173869a598af6c6972a8660Devang Patel } 346104cf9e02b0ed94d4173869a598af6c6972a8660Devang Patel } 347cb33799b9f4e152e3460faa83e59b53ff604c87dNick Lewycky 3487a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner // Add the value. 3497a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner Values.push_back(std::make_pair(V, 1U)); 3507a303d1591ef1b2d087dd863f2f058d30fcf7830Chris Lattner ValueID = Values.size(); 351fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner} 352fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 353fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 354db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnervoid ValueEnumerator::EnumerateType(Type *Ty) { 3551afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner unsigned *TypeID = &TypeMap[Ty]; 356a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 357f5a90561b033428bd2c5b365ca09ed9e688dce6eRafael Espindola // We've already seen this type. 3581afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (*TypeID) 359fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner return; 360a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 3611afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If it is a non-anonymous struct, mark the type as being visited so that we 3621afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // don't recursively visit it. This is safe because we allow forward 3631afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // references of these in the bitcode reader. 364db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(Ty)) 3653ebb64946bc8e7c8feba1b2044e7a47f80b3a83fChris Lattner if (!STy->isLiteral()) 3661afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner *TypeID = ~0U; 367170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 3681afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Enumerate all of the subtypes before we enumerate this type. This ensures 3691afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // that the type will be enumerated in an order that can be directly built. 370fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 371fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner I != E; ++I) 372fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner EnumerateType(*I); 373170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 3741afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Refresh the TypeID pointer in case the table rehashed. 3751afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner TypeID = &TypeMap[Ty]; 376170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 3771afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Check to see if we got the pointer another way. This can happen when 3781afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // enumerating recursive types that hit the base case deeper than they start. 3791afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // 3801afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // If this is actually a struct that we are treating as forward ref'able, 3811afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // then emit the definition now that all of its contents are available. 3821afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner if (*TypeID && *TypeID != ~0U) 3831afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner return; 384170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 3851afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // Add this type now that its contents are all happily enumerated. 3861afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner Types.push_back(Ty); 387170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 3881afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner *TypeID = Types.size(); 389fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner} 390fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 39133f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner// Enumerate the types for the specified value. If the value is a constant, 39233f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner// walk through it, enumerating the types of the constant. 393d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandezvoid ValueEnumerator::EnumerateOperandType(const Value *V) { 39433f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner EnumerateType(V->getType()); 395170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 39633f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner if (const Constant *C = dyn_cast<Constant>(V)) { 39733f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner // If this constant is already enumerated, ignore it, we know its type must 39833f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner // be enumerated. 39933f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner if (ValueMap.count(V)) return; 40033f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner 40133f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner // This constant may have operands, make sure to enumerate the types in 40233f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner // them. 403837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 4048340d0b6595567375e80466fdcd277d5e190ed98Jay Foad const Value *Op = C->getOperand(i); 405170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 406837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner // Don't enumerate basic blocks here, this happens as operands to 407837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner // blockaddress. 408837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner if (isa<BasicBlock>(Op)) continue; 409170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 410879d811563565c17a4cad63643128afbc95694ddDan Gohman EnumerateOperandType(Op); 411837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner } 412cb33799b9f4e152e3460faa83e59b53ff604c87dNick Lewycky 413cb33799b9f4e152e3460faa83e59b53ff604c87dNick Lewycky if (const MDNode *N = dyn_cast<MDNode>(V)) { 4145d0cacdbb6577f2449986f345858db17dc1bcf59Chris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 4155d0cacdbb6577f2449986f345858db17dc1bcf59Chris Lattner if (Value *Elem = N->getOperand(i)) 416d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez EnumerateOperandType(Elem); 417cb33799b9f4e152e3460faa83e59b53ff604c87dNick Lewycky } 418104cf9e02b0ed94d4173869a598af6c6972a8660Devang Patel } else if (isa<MDString>(V) || isa<MDNode>(V)) 41978aeae2d7b771e33c5ff5218802cd2e9dab13df0Dan Gohman EnumerateMetadata(V); 42033f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner} 42133f1d5b328813c986b8d083006a024e1a0c7d982Chris Lattner 422105ea3d49d4a458af8779ae7f144f00d19c4168fBill Wendlingvoid ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { 42358d74910c6b82e622ecbb57d6644d48fec5a5c0fChris Lattner if (PAL.isEmpty()) return; // null is always 0. 424105ea3d49d4a458af8779ae7f144f00d19c4168fBill Wendling 42550954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner // Do a lookup. 426105ea3d49d4a458af8779ae7f144f00d19c4168fBill Wendling unsigned &Entry = AttributeMap[PAL]; 42750954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner if (Entry == 0) { 42850954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner // Never saw this before, add it. 429034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling Attribute.push_back(PAL); 430034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling Entry = Attribute.size(); 43150954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner } 4328c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling 4338c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling // Do lookups for all attribute groups. 4348c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) { 4358c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling AttributeSet AS = PAL.getSlotAttributes(i); 436e9229a6a9614cbde1bff2bd6ffae3b7336db5702Bill Wendling unsigned &Entry = AttributeGroupMap[AS]; 4378c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling if (Entry == 0) { 438e9229a6a9614cbde1bff2bd6ffae3b7336db5702Bill Wendling AttributeGroups.push_back(AS); 439e9229a6a9614cbde1bff2bd6ffae3b7336db5702Bill Wendling Entry = AttributeGroups.size(); 4408c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling } 4418c2e77f895301967bf37d04e905fb1f069ec91b2Bill Wendling } 44250954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner} 44350954f5cba406a88011cc8ade3ceb4235830f907Chris Lattner 4446a0c04dff288b7eaa0459cc7419159765bb5a0b9Chad Rosiervoid ValueEnumerator::incorporateFunction(const Function &F) { 4459a49f1552db7e2ce24a03ec068b17db8a238856dNick Lewycky InstructionCount = 0; 446b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5Chris Lattner NumModuleValues = Values.size(); 447309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman NumModuleMDValues = MDValues.size(); 448a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 4498d35c79f273b74df1e95b4472620e31e81342037Chris Lattner // Adding function arguments to the value table. 4506dd26ba4bab4e3ebb1545e7e2211297f66e61e0bDan Gohman for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 4516dd26ba4bab4e3ebb1545e7e2211297f66e61e0bDan Gohman I != E; ++I) 4528d35c79f273b74df1e95b4472620e31e81342037Chris Lattner EnumerateValue(I); 4538d35c79f273b74df1e95b4472620e31e81342037Chris Lattner 454b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5Chris Lattner FirstFuncConstantID = Values.size(); 455a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 4568d35c79f273b74df1e95b4472620e31e81342037Chris Lattner // Add all function-level constants to the value table. 4578d35c79f273b74df1e95b4472620e31e81342037Chris Lattner for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 4588d35c79f273b74df1e95b4472620e31e81342037Chris Lattner for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 459a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 4608d35c79f273b74df1e95b4472620e31e81342037Chris Lattner OI != E; ++OI) { 4618d35c79f273b74df1e95b4472620e31e81342037Chris Lattner if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 4628d35c79f273b74df1e95b4472620e31e81342037Chris Lattner isa<InlineAsm>(*OI)) 4638d35c79f273b74df1e95b4472620e31e81342037Chris Lattner EnumerateValue(*OI); 4648d35c79f273b74df1e95b4472620e31e81342037Chris Lattner } 465c59c0afd7d24480f5a23d8fd6764ecfd6d4424ccChris Lattner BasicBlocks.push_back(BB); 466e825ed5a031937ad27d83bca12acf5533d7e0faeChris Lattner ValueMap[BB] = BasicBlocks.size(); 4678d35c79f273b74df1e95b4472620e31e81342037Chris Lattner } 468a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 4696da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner // Optimize the constant layout. 4706da91d3c2c138eb1d9739701a1314ba3580df897Chris Lattner OptimizeConstants(FirstFuncConstantID, Values.size()); 471a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 472dc024674ff96820d6020757b48d47f46d4c07db2Duncan Sands // Add the function's parameter attributes so they are available for use in 473dc024674ff96820d6020757b48d47f46d4c07db2Duncan Sands // the function's instruction. 4740598866c052147c31b808391f58434ce3dbfb838Devang Patel EnumerateAttributes(F.getAttributes()); 475dc024674ff96820d6020757b48d47f46d4c07db2Duncan Sands 476b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5Chris Lattner FirstInstID = Values.size(); 477a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 4786209869f83979319e2e5791382f09b83e54191e0Devang Patel SmallVector<MDNode *, 8> FnLocalMDVector; 4798d35c79f273b74df1e95b4472620e31e81342037Chris Lattner // Add all of the instructions. 4808d35c79f273b74df1e95b4472620e31e81342037Chris Lattner for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 481fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 482ab9cd107211604988c19d2d49eb4bfcd05df7995Victor Hernandez for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 483ab9cd107211604988c19d2d49eb4bfcd05df7995Victor Hernandez OI != E; ++OI) { 484d7e6457c3faf6c5530a4c8224e2dfcf91b57093bVictor Hernandez if (MDNode *MD = dyn_cast<MDNode>(*OI)) 4852b3365ca1dd53b078714ec99b5b2ea6b67b23c9cVictor Hernandez if (MD->isFunctionLocal() && MD->getFunction()) 486af6ce14d679e2a87d2de6a3e26ce6a1f34d1f879Victor Hernandez // Enumerate metadata after the instructions they might refer to. 4876209869f83979319e2e5791382f09b83e54191e0Devang Patel FnLocalMDVector.push_back(MD); 488ab9cd107211604988c19d2d49eb4bfcd05df7995Victor Hernandez } 489309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman 490309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; 491309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman I->getAllMetadataOtherThanDebugLoc(MDs); 492309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman for (unsigned i = 0, e = MDs.size(); i != e; ++i) { 493309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDNode *N = MDs[i].second; 494309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman if (N->isFunctionLocal() && N->getFunction()) 495309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman FnLocalMDVector.push_back(N); 496309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman } 497170a15e98dc6900df1ae40d03c5f0622d792fb45Joe Abbey 498f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (!I->getType()->isVoidTy()) 4998d35c79f273b74df1e95b4472620e31e81342037Chris Lattner EnumerateValue(I); 500fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner } 501fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner } 502af6ce14d679e2a87d2de6a3e26ce6a1f34d1f879Victor Hernandez 503af6ce14d679e2a87d2de6a3e26ce6a1f34d1f879Victor Hernandez // Add all of the function-local metadata. 5046209869f83979319e2e5791382f09b83e54191e0Devang Patel for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) 505309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman EnumerateFunctionLocalMetadata(FnLocalMDVector[i]); 506fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner} 507fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner 5086a0c04dff288b7eaa0459cc7419159765bb5a0b9Chad Rosiervoid ValueEnumerator::purgeFunction() { 5098d35c79f273b74df1e95b4472620e31e81342037Chris Lattner /// Remove purged values from the ValueMap. 510b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5Chris Lattner for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 5118d35c79f273b74df1e95b4472620e31e81342037Chris Lattner ValueMap.erase(Values[i].first); 512309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i) 513309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValueMap.erase(MDValues[i].first); 514c59c0afd7d24480f5a23d8fd6764ecfd6d4424ccChris Lattner for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 515c59c0afd7d24480f5a23d8fd6764ecfd6d4424ccChris Lattner ValueMap.erase(BasicBlocks[i]); 516a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 517b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5Chris Lattner Values.resize(NumModuleValues); 518309b3af547a60bedd74daa2a94ebd3d3ed5f06e9Dan Gohman MDValues.resize(NumModuleMDValues); 519c59c0afd7d24480f5a23d8fd6764ecfd6d4424ccChris Lattner BasicBlocks.clear(); 520848c9aedd7e6a957604cea2150dab66ee2c5a24fDan Gohman FunctionLocalMDs.clear(); 521fd57cecd2cb3ac726942e0101de6a82dc5a958a6Chris Lattner} 522837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner 523837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattnerstatic void IncorporateFunctionInfoGlobalBBIDs(const Function *F, 524837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner DenseMap<const BasicBlock*, unsigned> &IDMap) { 525837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner unsigned Counter = 0; 526837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 527837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner IDMap[BB] = ++Counter; 528837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner} 529837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner 530837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner/// getGlobalBasicBlockID - This returns the function-specific ID for the 531837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner/// specified basic block. This is relatively expensive information, so it 532837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner/// should only be used by rare constructs such as address-of-label. 533837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattnerunsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { 534837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner unsigned &Idx = GlobalBasicBlockIDs[BB]; 535837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner if (Idx != 0) 536cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner return Idx-1; 537837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner 538837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); 539837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner return getGlobalBasicBlockID(BB); 540837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner} 541837e04a8bf13712a4a8ae279daab65a048b21f7dChris Lattner 542