ValueEnumerator.cpp revision b9d0c2a6a0ef5e19b2d30180ce7d6a10ffa1f5c5
1//===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the ValueEnumerator class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "ValueEnumerator.h" 15#include "llvm/Module.h" 16#include "llvm/TypeSymbolTable.h" 17#include "llvm/ValueSymbolTable.h" 18using namespace llvm; 19 20/// ValueEnumerator - Enumerate module-level information. 21ValueEnumerator::ValueEnumerator(const Module *M) { 22 // Enumerate the global variables. 23 for (Module::const_global_iterator I = M->global_begin(), 24 E = M->global_end(); I != E; ++I) 25 EnumerateValue(I); 26 27 // Enumerate the functions. 28 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) 29 EnumerateValue(I); 30 31 // Enumerate the aliases. 32 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 33 I != E; ++I) 34 EnumerateValue(I); 35 36 // Enumerate the global variable initializers. 37 for (Module::const_global_iterator I = M->global_begin(), 38 E = M->global_end(); I != E; ++I) 39 if (I->hasInitializer()) 40 EnumerateValue(I->getInitializer()); 41 42 // Enumerate the aliasees. 43 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 44 I != E; ++I) 45 EnumerateValue(I->getAliasee()); 46 47 // FIXME: Implement the 'string constant' optimization. 48 49 // Enumerate types used by the type symbol table. 50 EnumerateTypeSymbolTable(M->getTypeSymbolTable()); 51 52 // Insert constants that are named at module level into the slot pool so that 53 // the module symbol table can refer to them... 54 EnumerateValueSymbolTable(M->getValueSymbolTable()); 55 56 // Enumerate types used by function bodies and argument lists. 57 for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) { 58 59 for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 60 I != E; ++I) 61 EnumerateType(I->getType()); 62 63 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 64 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){ 65 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 66 OI != E; ++OI) 67 EnumerateType((*OI)->getType()); 68 EnumerateType(I->getType()); 69 } 70 } 71 72 73 // FIXME: std::partition the type and value tables so that first-class types 74 // come earlier than aggregates. FIXME: Emit a marker into the module 75 // indicating which aggregates types AND values can be dropped form the table. 76 77 // FIXME: Sort type/value tables by frequency. 78 79 // FIXME: Sort constants by type to reduce size. 80} 81 82/// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol 83/// table. 84void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) { 85 for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end(); 86 TI != TE; ++TI) 87 EnumerateType(TI->second); 88} 89 90/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 91/// table into the values table. 92void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 93 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 94 VI != VE; ++VI) 95 EnumerateValue(VI->getValue()); 96} 97 98void ValueEnumerator::EnumerateValue(const Value *V) { 99 assert(V->getType() != Type::VoidTy && "Can't insert void values!"); 100 101 // Check to see if it's already in! 102 unsigned &ValueID = ValueMap[V]; 103 if (ValueID) { 104 // Increment use count. 105 Values[ValueID-1].second++; 106 return; 107 } 108 109 // Add the value. 110 Values.push_back(std::make_pair(V, 1U)); 111 ValueID = Values.size(); 112 113 if (const Constant *C = dyn_cast<Constant>(V)) { 114 if (isa<GlobalValue>(C)) { 115 // Initializers for globals are handled explicitly elsewhere. 116 } else { 117 // This makes sure that if a constant has uses (for example an array of 118 // const ints), that they are inserted also. 119 for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 120 I != E; ++I) 121 EnumerateValue(*I); 122 } 123 } 124 125 EnumerateType(V->getType()); 126} 127 128 129void ValueEnumerator::EnumerateType(const Type *Ty) { 130 unsigned &TypeID = TypeMap[Ty]; 131 132 if (TypeID) { 133 // If we've already seen this type, just increase its occurrence count. 134 Types[TypeID-1].second++; 135 return; 136 } 137 138 // First time we saw this type, add it. 139 Types.push_back(std::make_pair(Ty, 1U)); 140 TypeID = Types.size(); 141 142 // Enumerate subtypes. 143 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 144 I != E; ++I) 145 EnumerateType(*I); 146} 147 148/// PurgeAggregateValues - If there are any aggregate values at the end of the 149/// value list, remove them and return the count of the remaining values. If 150/// there are none, return -1. 151int ValueEnumerator::PurgeAggregateValues() { 152 // If there are no aggregate values at the end of the list, return -1. 153 if (Values.empty() || Values.back().first->getType()->isFirstClassType()) 154 return -1; 155 156 // Otherwise, remove aggregate values... 157 while (!Values.empty() && !Values.back().first->getType()->isFirstClassType()) 158 Values.pop_back(); 159 160 // ... and return the new size. 161 return Values.size(); 162} 163 164void ValueEnumerator::incorporateFunction(const Function &F) { 165 NumModuleValues = Values.size(); 166 167 // Adding function arguments to the value table. 168 for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 169 I != E; ++I) 170 EnumerateValue(I); 171 172 FirstFuncConstantID = Values.size(); 173 174 // Add all function-level constants to the value table. 175 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 176 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 177 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 178 OI != E; ++OI) { 179 if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 180 isa<InlineAsm>(*OI)) 181 EnumerateValue(*OI); 182 } 183 ValueMap[BB] = BasicBlocks.size(); 184 BasicBlocks.push_back(BB); 185 } 186 187 FirstInstID = Values.size(); 188 189 // Add all of the instructions. 190 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 191 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 192 if (I->getType() != Type::VoidTy) 193 EnumerateValue(I); 194 } 195 } 196} 197 198void ValueEnumerator::purgeFunction() { 199 /// Remove purged values from the ValueMap. 200 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 201 ValueMap.erase(Values[i].first); 202 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 203 ValueMap.erase(BasicBlocks[i]); 204 205 Values.resize(NumModuleValues); 206 BasicBlocks.clear(); 207} 208 209