ValueEnumerator.cpp revision 198892
1254885Sdumbbell//===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===// 2254885Sdumbbell// 3254885Sdumbbell// The LLVM Compiler Infrastructure 4254885Sdumbbell// 5254885Sdumbbell// This file is distributed under the University of Illinois Open Source 6254885Sdumbbell// License. See LICENSE.TXT for details. 7254885Sdumbbell// 8254885Sdumbbell//===----------------------------------------------------------------------===// 9254885Sdumbbell// 10254885Sdumbbell// This file implements the ValueEnumerator class. 11254885Sdumbbell// 12254885Sdumbbell//===----------------------------------------------------------------------===// 13254885Sdumbbell 14254885Sdumbbell#include "ValueEnumerator.h" 15254885Sdumbbell#include "llvm/Constants.h" 16254885Sdumbbell#include "llvm/DerivedTypes.h" 17254885Sdumbbell#include "llvm/LLVMContext.h" 18254885Sdumbbell#include "llvm/Metadata.h" 19254885Sdumbbell#include "llvm/Module.h" 20254885Sdumbbell#include "llvm/TypeSymbolTable.h" 21254885Sdumbbell#include "llvm/ValueSymbolTable.h" 22254885Sdumbbell#include "llvm/Instructions.h" 23254885Sdumbbell#include <algorithm> 24254885Sdumbbellusing namespace llvm; 25254885Sdumbbell 26254885Sdumbbellstatic bool isSingleValueType(const std::pair<const llvm::Type*, 27254885Sdumbbell unsigned int> &P) { 28254885Sdumbbell return P.first->isSingleValueType(); 29254885Sdumbbell} 30254885Sdumbbell 31254885Sdumbbellstatic bool isIntegerValue(const std::pair<const Value*, unsigned> &V) { 32254885Sdumbbell return isa<IntegerType>(V.first->getType()); 33254885Sdumbbell} 34254885Sdumbbell 35254885Sdumbbellstatic bool CompareByFrequency(const std::pair<const llvm::Type*, 36254885Sdumbbell unsigned int> &P1, 37254885Sdumbbell const std::pair<const llvm::Type*, 38254885Sdumbbell unsigned int> &P2) { 39254885Sdumbbell return P1.second > P2.second; 40254885Sdumbbell} 41254885Sdumbbell 42254885Sdumbbell/// ValueEnumerator - Enumerate module-level information. 43254885SdumbbellValueEnumerator::ValueEnumerator(const Module *M) { 44254885Sdumbbell InstructionCount = 0; 45254885Sdumbbell 46254885Sdumbbell // Enumerate the global variables. 47254885Sdumbbell for (Module::const_global_iterator I = M->global_begin(), 48254885Sdumbbell E = M->global_end(); I != E; ++I) 49254885Sdumbbell EnumerateValue(I); 50254885Sdumbbell 51254885Sdumbbell // Enumerate the functions. 52254885Sdumbbell for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { 53254885Sdumbbell EnumerateValue(I); 54254885Sdumbbell EnumerateAttributes(cast<Function>(I)->getAttributes()); 55254885Sdumbbell } 56254885Sdumbbell 57254885Sdumbbell // Enumerate the aliases. 58254885Sdumbbell for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 59254885Sdumbbell I != E; ++I) 60254885Sdumbbell EnumerateValue(I); 61254885Sdumbbell 62254885Sdumbbell // Remember what is the cutoff between globalvalue's and other constants. 63254885Sdumbbell unsigned FirstConstant = Values.size(); 64254885Sdumbbell 65254885Sdumbbell // Enumerate the global variable initializers. 66254885Sdumbbell for (Module::const_global_iterator I = M->global_begin(), 67254885Sdumbbell E = M->global_end(); I != E; ++I) 68254885Sdumbbell if (I->hasInitializer()) 69254885Sdumbbell EnumerateValue(I->getInitializer()); 70254885Sdumbbell 71254885Sdumbbell // Enumerate the aliasees. 72254885Sdumbbell for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 73254885Sdumbbell I != E; ++I) 74254885Sdumbbell EnumerateValue(I->getAliasee()); 75254885Sdumbbell 76254885Sdumbbell // Enumerate types used by the type symbol table. 77254885Sdumbbell EnumerateTypeSymbolTable(M->getTypeSymbolTable()); 78254885Sdumbbell 79254885Sdumbbell // Insert constants that are named at module level into the slot pool so that 80254885Sdumbbell // the module symbol table can refer to them... 81254885Sdumbbell EnumerateValueSymbolTable(M->getValueSymbolTable()); 82254885Sdumbbell 83254885Sdumbbell // Enumerate types used by function bodies and argument lists. 84254885Sdumbbell for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) { 85254885Sdumbbell 86254885Sdumbbell for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 87254885Sdumbbell I != E; ++I) 88254885Sdumbbell EnumerateType(I->getType()); 89254885Sdumbbell 90254885Sdumbbell MetadataContext &TheMetadata = F->getContext().getMetadata(); 91254885Sdumbbell typedef SmallVector<std::pair<unsigned, TrackingVH<MDNode> >, 2> MDMapTy; 92254885Sdumbbell MDMapTy MDs; 93254885Sdumbbell for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 94254885Sdumbbell for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){ 95254885Sdumbbell for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 96254885Sdumbbell OI != E; ++OI) 97254885Sdumbbell EnumerateOperandType(*OI); 98254885Sdumbbell EnumerateType(I->getType()); 99254885Sdumbbell if (const CallInst *CI = dyn_cast<CallInst>(I)) 100254885Sdumbbell EnumerateAttributes(CI->getAttributes()); 101254885Sdumbbell else if (const InvokeInst *II = dyn_cast<InvokeInst>(I)) 102254885Sdumbbell EnumerateAttributes(II->getAttributes()); 103254885Sdumbbell 104254885Sdumbbell // Enumerate metadata attached with this instruction. 105254885Sdumbbell MDs.clear(); 106254885Sdumbbell TheMetadata.getMDs(I, MDs); 107254885Sdumbbell for (MDMapTy::const_iterator MI = MDs.begin(), ME = MDs.end(); MI != ME; 108254885Sdumbbell ++MI) 109254885Sdumbbell EnumerateMetadata(MI->second); 110254885Sdumbbell } 111254885Sdumbbell } 112254885Sdumbbell 113254885Sdumbbell // Optimize constant ordering. 114254885Sdumbbell OptimizeConstants(FirstConstant, Values.size()); 115254885Sdumbbell 116254885Sdumbbell // Sort the type table by frequency so that most commonly used types are early 117254885Sdumbbell // in the table (have low bit-width). 118254885Sdumbbell std::stable_sort(Types.begin(), Types.end(), CompareByFrequency); 119254885Sdumbbell 120254885Sdumbbell // Partition the Type ID's so that the single-value types occur before the 121254885Sdumbbell // aggregate types. This allows the aggregate types to be dropped from the 122254885Sdumbbell // type table after parsing the global variable initializers. 123254885Sdumbbell std::partition(Types.begin(), Types.end(), isSingleValueType); 124254885Sdumbbell 125254885Sdumbbell // Now that we rearranged the type table, rebuild TypeMap. 126254885Sdumbbell for (unsigned i = 0, e = Types.size(); i != e; ++i) 127254885Sdumbbell TypeMap[Types[i].first] = i+1; 128254885Sdumbbell} 129254885Sdumbbell 130254885Sdumbbellunsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { 131254885Sdumbbell InstructionMapType::const_iterator I = InstructionMap.find(Inst); 132254885Sdumbbell assert (I != InstructionMap.end() && "Instruction is not mapped!"); 133254885Sdumbbell return I->second; 134254885Sdumbbell} 135254885Sdumbbell 136254885Sdumbbellvoid ValueEnumerator::setInstructionID(const Instruction *I) { 137254885Sdumbbell InstructionMap[I] = InstructionCount++; 138254885Sdumbbell} 139254885Sdumbbell 140254885Sdumbbellunsigned ValueEnumerator::getValueID(const Value *V) const { 141254885Sdumbbell if (isa<MetadataBase>(V)) { 142254885Sdumbbell ValueMapType::const_iterator I = MDValueMap.find(V); 143254885Sdumbbell assert(I != MDValueMap.end() && "Value not in slotcalculator!"); 144254885Sdumbbell return I->second-1; 145254885Sdumbbell } 146254885Sdumbbell 147254885Sdumbbell ValueMapType::const_iterator I = ValueMap.find(V); 148254885Sdumbbell assert(I != ValueMap.end() && "Value not in slotcalculator!"); 149254885Sdumbbell return I->second-1; 150254885Sdumbbell} 151254885Sdumbbell 152254885Sdumbbell// Optimize constant ordering. 153254885Sdumbbellnamespace { 154254885Sdumbbell struct CstSortPredicate { 155254885Sdumbbell ValueEnumerator &VE; 156254885Sdumbbell explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} 157254885Sdumbbell bool operator()(const std::pair<const Value*, unsigned> &LHS, 158254885Sdumbbell const std::pair<const Value*, unsigned> &RHS) { 159254885Sdumbbell // Sort by plane. 160254885Sdumbbell if (LHS.first->getType() != RHS.first->getType()) 161254885Sdumbbell return VE.getTypeID(LHS.first->getType()) < 162254885Sdumbbell VE.getTypeID(RHS.first->getType()); 163254885Sdumbbell // Then by frequency. 164254885Sdumbbell return LHS.second > RHS.second; 165254885Sdumbbell } 166254885Sdumbbell }; 167254885Sdumbbell} 168254885Sdumbbell 169254885Sdumbbell/// OptimizeConstants - Reorder constant pool for denser encoding. 170254885Sdumbbellvoid ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 171254885Sdumbbell if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 172254885Sdumbbell 173254885Sdumbbell CstSortPredicate P(*this); 174254885Sdumbbell std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); 175254885Sdumbbell 176254885Sdumbbell // Ensure that integer constants are at the start of the constant pool. This 177254885Sdumbbell // is important so that GEP structure indices come before gep constant exprs. 178254885Sdumbbell std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, 179254885Sdumbbell isIntegerValue); 180254885Sdumbbell 181254885Sdumbbell // Rebuild the modified portion of ValueMap. 182254885Sdumbbell for (; CstStart != CstEnd; ++CstStart) 183254885Sdumbbell ValueMap[Values[CstStart].first] = CstStart+1; 184254885Sdumbbell} 185254885Sdumbbell 186254885Sdumbbell 187254885Sdumbbell/// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol 188254885Sdumbbell/// table. 189254885Sdumbbellvoid ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) { 190254885Sdumbbell for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end(); 191254885Sdumbbell TI != TE; ++TI) 192254885Sdumbbell EnumerateType(TI->second); 193254885Sdumbbell} 194254885Sdumbbell 195254885Sdumbbell/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 196254885Sdumbbell/// table into the values table. 197254885Sdumbbellvoid ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 198254885Sdumbbell for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 199254885Sdumbbell VI != VE; ++VI) 200254885Sdumbbell EnumerateValue(VI->getValue()); 201254885Sdumbbell} 202254885Sdumbbell 203254885Sdumbbellvoid ValueEnumerator::EnumerateMetadata(const MetadataBase *MD) { 204254885Sdumbbell // Check to see if it's already in! 205254885Sdumbbell unsigned &MDValueID = MDValueMap[MD]; 206254885Sdumbbell if (MDValueID) { 207254885Sdumbbell // Increment use count. 208254885Sdumbbell MDValues[MDValueID-1].second++; 209254885Sdumbbell return; 210254885Sdumbbell } 211254885Sdumbbell 212254885Sdumbbell // Enumerate the type of this value. 213254885Sdumbbell EnumerateType(MD->getType()); 214254885Sdumbbell 215254885Sdumbbell if (const MDNode *N = dyn_cast<MDNode>(MD)) { 216254885Sdumbbell MDValues.push_back(std::make_pair(MD, 1U)); 217254885Sdumbbell MDValueMap[MD] = MDValues.size(); 218254885Sdumbbell MDValueID = MDValues.size(); 219254885Sdumbbell for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) { 220254885Sdumbbell if (Value *V = N->getElement(i)) 221254885Sdumbbell EnumerateValue(V); 222254885Sdumbbell else 223254885Sdumbbell EnumerateType(Type::getVoidTy(MD->getContext())); 224254885Sdumbbell } 225254885Sdumbbell return; 226254885Sdumbbell } 227254885Sdumbbell 228254885Sdumbbell if (const NamedMDNode *N = dyn_cast<NamedMDNode>(MD)) { 229254885Sdumbbell for(NamedMDNode::const_elem_iterator I = N->elem_begin(), 230254885Sdumbbell E = N->elem_end(); I != E; ++I) { 231254885Sdumbbell MetadataBase *M = *I; 232254885Sdumbbell EnumerateValue(M); 233254885Sdumbbell } 234254885Sdumbbell MDValues.push_back(std::make_pair(MD, 1U)); 235254885Sdumbbell MDValueMap[MD] = Values.size(); 236254885Sdumbbell return; 237254885Sdumbbell } 238254885Sdumbbell 239254885Sdumbbell // Add the value. 240254885Sdumbbell MDValues.push_back(std::make_pair(MD, 1U)); 241254885Sdumbbell MDValueID = MDValues.size(); 242254885Sdumbbell} 243254885Sdumbbell 244254885Sdumbbellvoid ValueEnumerator::EnumerateValue(const Value *V) { 245254885Sdumbbell assert(V->getType() != Type::getVoidTy(V->getContext()) && 246254885Sdumbbell "Can't insert void values!"); 247254885Sdumbbell if (const MetadataBase *MB = dyn_cast<MetadataBase>(V)) 248254885Sdumbbell return EnumerateMetadata(MB); 249254885Sdumbbell 250254885Sdumbbell // Check to see if it's already in! 251254885Sdumbbell unsigned &ValueID = ValueMap[V]; 252254885Sdumbbell if (ValueID) { 253 // Increment use count. 254 Values[ValueID-1].second++; 255 return; 256 } 257 258 // Enumerate the type of this value. 259 EnumerateType(V->getType()); 260 261 if (const Constant *C = dyn_cast<Constant>(V)) { 262 if (isa<GlobalValue>(C)) { 263 // Initializers for globals are handled explicitly elsewhere. 264 } else if (isa<ConstantArray>(C) && cast<ConstantArray>(C)->isString()) { 265 // Do not enumerate the initializers for an array of simple characters. 266 // The initializers just polute the value table, and we emit the strings 267 // specially. 268 } else if (C->getNumOperands()) { 269 // If a constant has operands, enumerate them. This makes sure that if a 270 // constant has uses (for example an array of const ints), that they are 271 // inserted also. 272 273 // We prefer to enumerate them with values before we enumerate the user 274 // itself. This makes it more likely that we can avoid forward references 275 // in the reader. We know that there can be no cycles in the constants 276 // graph that don't go through a global variable. 277 for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 278 I != E; ++I) 279 if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. 280 EnumerateValue(*I); 281 282 // Finally, add the value. Doing this could make the ValueID reference be 283 // dangling, don't reuse it. 284 Values.push_back(std::make_pair(V, 1U)); 285 ValueMap[V] = Values.size(); 286 return; 287 } 288 } 289 290 // Add the value. 291 Values.push_back(std::make_pair(V, 1U)); 292 ValueID = Values.size(); 293} 294 295 296void ValueEnumerator::EnumerateType(const Type *Ty) { 297 unsigned &TypeID = TypeMap[Ty]; 298 299 if (TypeID) { 300 // If we've already seen this type, just increase its occurrence count. 301 Types[TypeID-1].second++; 302 return; 303 } 304 305 // First time we saw this type, add it. 306 Types.push_back(std::make_pair(Ty, 1U)); 307 TypeID = Types.size(); 308 309 // Enumerate subtypes. 310 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 311 I != E; ++I) 312 EnumerateType(*I); 313} 314 315// Enumerate the types for the specified value. If the value is a constant, 316// walk through it, enumerating the types of the constant. 317void ValueEnumerator::EnumerateOperandType(const Value *V) { 318 EnumerateType(V->getType()); 319 if (const Constant *C = dyn_cast<Constant>(V)) { 320 // If this constant is already enumerated, ignore it, we know its type must 321 // be enumerated. 322 if (ValueMap.count(V)) return; 323 324 // This constant may have operands, make sure to enumerate the types in 325 // them. 326 for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 327 const User *Op = C->getOperand(i); 328 329 // Don't enumerate basic blocks here, this happens as operands to 330 // blockaddress. 331 if (isa<BasicBlock>(Op)) continue; 332 333 EnumerateOperandType(cast<Constant>(Op)); 334 } 335 336 if (const MDNode *N = dyn_cast<MDNode>(V)) { 337 for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) 338 if (Value *Elem = N->getElement(i)) 339 EnumerateOperandType(Elem); 340 } 341 } else if (isa<MDString>(V) || isa<MDNode>(V)) 342 EnumerateValue(V); 343} 344 345void ValueEnumerator::EnumerateAttributes(const AttrListPtr &PAL) { 346 if (PAL.isEmpty()) return; // null is always 0. 347 // Do a lookup. 348 unsigned &Entry = AttributeMap[PAL.getRawPointer()]; 349 if (Entry == 0) { 350 // Never saw this before, add it. 351 Attributes.push_back(PAL); 352 Entry = Attributes.size(); 353 } 354} 355 356 357void ValueEnumerator::incorporateFunction(const Function &F) { 358 NumModuleValues = Values.size(); 359 360 // Adding function arguments to the value table. 361 for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 362 I != E; ++I) 363 EnumerateValue(I); 364 365 FirstFuncConstantID = Values.size(); 366 367 // Add all function-level constants to the value table. 368 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 369 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 370 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 371 OI != E; ++OI) { 372 if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 373 isa<InlineAsm>(*OI)) 374 EnumerateValue(*OI); 375 } 376 BasicBlocks.push_back(BB); 377 ValueMap[BB] = BasicBlocks.size(); 378 } 379 380 // Optimize the constant layout. 381 OptimizeConstants(FirstFuncConstantID, Values.size()); 382 383 // Add the function's parameter attributes so they are available for use in 384 // the function's instruction. 385 EnumerateAttributes(F.getAttributes()); 386 387 FirstInstID = Values.size(); 388 389 // Add all of the instructions. 390 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 391 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 392 if (I->getType() != Type::getVoidTy(F.getContext())) 393 EnumerateValue(I); 394 } 395 } 396} 397 398void ValueEnumerator::purgeFunction() { 399 /// Remove purged values from the ValueMap. 400 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 401 ValueMap.erase(Values[i].first); 402 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 403 ValueMap.erase(BasicBlocks[i]); 404 405 Values.resize(NumModuleValues); 406 BasicBlocks.clear(); 407} 408 409static void IncorporateFunctionInfoGlobalBBIDs(const Function *F, 410 DenseMap<const BasicBlock*, unsigned> &IDMap) { 411 unsigned Counter = 0; 412 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 413 IDMap[BB] = ++Counter; 414} 415 416/// getGlobalBasicBlockID - This returns the function-specific ID for the 417/// specified basic block. This is relatively expensive information, so it 418/// should only be used by rare constructs such as address-of-label. 419unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { 420 unsigned &Idx = GlobalBasicBlockIDs[BB]; 421 if (Idx != 0) 422 return Idx-1; 423 424 IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); 425 return getGlobalBasicBlockID(BB); 426} 427 428