LLVM API Documentation
00001 //===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the ValueEnumerator class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "ValueEnumerator.h" 00015 #include "llvm/Constants.h" 00016 #include "llvm/DerivedTypes.h" 00017 #include "llvm/Metadata.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/TypeSymbolTable.h" 00020 #include "llvm/ValueSymbolTable.h" 00021 #include "llvm/Instructions.h" 00022 #include <algorithm> 00023 using namespace llvm; 00024 00025 static bool isSingleValueType(const std::pair<const llvm::Type*, 00026 unsigned int> &P) { 00027 return P.first->isSingleValueType(); 00028 } 00029 00030 static bool isIntegerValue(const std::pair<const Value*, unsigned> &V) { 00031 return isa<IntegerType>(V.first->getType()); 00032 } 00033 00034 static bool CompareByFrequency(const std::pair<const llvm::Type*, 00035 unsigned int> &P1, 00036 const std::pair<const llvm::Type*, 00037 unsigned int> &P2) { 00038 return P1.second > P2.second; 00039 } 00040 00041 /// ValueEnumerator - Enumerate module-level information. 00042 ValueEnumerator::ValueEnumerator(const Module *M) { 00043 // Enumerate the global variables. 00044 for (Module::const_global_iterator I = M->global_begin(), 00045 E = M->global_end(); I != E; ++I) 00046 EnumerateValue(I); 00047 00048 // Enumerate the functions. 00049 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { 00050 EnumerateValue(I); 00051 EnumerateAttributes(cast<Function>(I)->getAttributes()); 00052 } 00053 00054 // Enumerate the aliases. 00055 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 00056 I != E; ++I) 00057 EnumerateValue(I); 00058 00059 // Remember what is the cutoff between globalvalue's and other constants. 00060 unsigned FirstConstant = Values.size(); 00061 00062 // Enumerate the global variable initializers. 00063 for (Module::const_global_iterator I = M->global_begin(), 00064 E = M->global_end(); I != E; ++I) 00065 if (I->hasInitializer()) 00066 EnumerateValue(I->getInitializer()); 00067 00068 // Enumerate the aliasees. 00069 for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 00070 I != E; ++I) 00071 EnumerateValue(I->getAliasee()); 00072 00073 // Enumerate types used by the type symbol table. 00074 EnumerateTypeSymbolTable(M->getTypeSymbolTable()); 00075 00076 // Insert constants that are named at module level into the slot pool so that 00077 // the module symbol table can refer to them... 00078 EnumerateValueSymbolTable(M->getValueSymbolTable()); 00079 00080 // Enumerate types used by function bodies and argument lists. 00081 for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) { 00082 00083 for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 00084 I != E; ++I) 00085 EnumerateType(I->getType()); 00086 00087 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 00088 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){ 00089 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 00090 OI != E; ++OI) 00091 EnumerateOperandType(*OI); 00092 EnumerateType(I->getType()); 00093 if (const CallInst *CI = dyn_cast<CallInst>(I)) 00094 EnumerateAttributes(CI->getAttributes()); 00095 else if (const InvokeInst *II = dyn_cast<InvokeInst>(I)) 00096 EnumerateAttributes(II->getAttributes()); 00097 } 00098 } 00099 00100 // Optimize constant ordering. 00101 OptimizeConstants(FirstConstant, Values.size()); 00102 00103 // Sort the type table by frequency so that most commonly used types are early 00104 // in the table (have low bit-width). 00105 std::stable_sort(Types.begin(), Types.end(), CompareByFrequency); 00106 00107 // Partition the Type ID's so that the single-value types occur before the 00108 // aggregate types. This allows the aggregate types to be dropped from the 00109 // type table after parsing the global variable initializers. 00110 std::partition(Types.begin(), Types.end(), isSingleValueType); 00111 00112 // Now that we rearranged the type table, rebuild TypeMap. 00113 for (unsigned i = 0, e = Types.size(); i != e; ++i) 00114 TypeMap[Types[i].first] = i+1; 00115 } 00116 00117 unsigned ValueEnumerator::getValueID(const Value *V) const { 00118 if (isa<MetadataBase>(V)) { 00119 ValueMapType::const_iterator I = MDValueMap.find(V); 00120 assert(I != MDValueMap.end() && "Value not in slotcalculator!"); 00121 return I->second-1; 00122 } 00123 00124 ValueMapType::const_iterator I = ValueMap.find(V); 00125 assert(I != ValueMap.end() && "Value not in slotcalculator!"); 00126 return I->second-1; 00127 } 00128 00129 // Optimize constant ordering. 00130 namespace { 00131 struct CstSortPredicate { 00132 ValueEnumerator &VE; 00133 explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} 00134 bool operator()(const std::pair<const Value*, unsigned> &LHS, 00135 const std::pair<const Value*, unsigned> &RHS) { 00136 // Sort by plane. 00137 if (LHS.first->getType() != RHS.first->getType()) 00138 return VE.getTypeID(LHS.first->getType()) < 00139 VE.getTypeID(RHS.first->getType()); 00140 // Then by frequency. 00141 return LHS.second > RHS.second; 00142 } 00143 }; 00144 } 00145 00146 /// OptimizeConstants - Reorder constant pool for denser encoding. 00147 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 00148 if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 00149 00150 CstSortPredicate P(*this); 00151 std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); 00152 00153 // Ensure that integer constants are at the start of the constant pool. This 00154 // is important so that GEP structure indices come before gep constant exprs. 00155 std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, 00156 isIntegerValue); 00157 00158 // Rebuild the modified portion of ValueMap. 00159 for (; CstStart != CstEnd; ++CstStart) 00160 ValueMap[Values[CstStart].first] = CstStart+1; 00161 } 00162 00163 00164 /// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol 00165 /// table. 00166 void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) { 00167 for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end(); 00168 TI != TE; ++TI) 00169 EnumerateType(TI->second); 00170 } 00171 00172 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 00173 /// table into the values table. 00174 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 00175 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 00176 VI != VE; ++VI) 00177 EnumerateValue(VI->getValue()); 00178 } 00179 00180 void ValueEnumerator::EnumerateMetadata(const MetadataBase *MD) { 00181 // Check to see if it's already in! 00182 unsigned &MDValueID = MDValueMap[MD]; 00183 if (MDValueID) { 00184 // Increment use count. 00185 MDValues[MDValueID-1].second++; 00186 return; 00187 } 00188 00189 // Enumerate the type of this value. 00190 EnumerateType(MD->getType()); 00191 00192 if (const MDNode *N = dyn_cast<MDNode>(MD)) { 00193 MDValues.push_back(std::make_pair(MD, 1U)); 00194 MDValueMap[MD] = MDValues.size(); 00195 MDValueID = MDValues.size(); 00196 for (MDNode::const_elem_iterator I = N->elem_begin(), E = N->elem_end(); 00197 I != E; ++I) { 00198 if (*I) 00199 EnumerateValue(*I); 00200 else 00201 EnumerateType(Type::getVoidTy(MD->getContext())); 00202 } 00203 return; 00204 } else if (const NamedMDNode *N = dyn_cast<NamedMDNode>(MD)) { 00205 for(NamedMDNode::const_elem_iterator I = N->elem_begin(), 00206 E = N->elem_end(); I != E; ++I) { 00207 MetadataBase *M = *I; 00208 EnumerateValue(M); 00209 } 00210 MDValues.push_back(std::make_pair(MD, 1U)); 00211 MDValueMap[MD] = Values.size(); 00212 return; 00213 } 00214 00215 // Add the value. 00216 MDValues.push_back(std::make_pair(MD, 1U)); 00217 MDValueID = MDValues.size(); 00218 } 00219 00220 void ValueEnumerator::EnumerateValue(const Value *V) { 00221 assert(V->getType() != Type::getVoidTy(V->getContext()) && 00222 "Can't insert void values!"); 00223 if (const MetadataBase *MB = dyn_cast<MetadataBase>(V)) 00224 return EnumerateMetadata(MB); 00225 00226 // Check to see if it's already in! 00227 unsigned &ValueID = ValueMap[V]; 00228 if (ValueID) { 00229 // Increment use count. 00230 Values[ValueID-1].second++; 00231 return; 00232 } 00233 00234 // Enumerate the type of this value. 00235 EnumerateType(V->getType()); 00236 00237 if (const Constant *C = dyn_cast<Constant>(V)) { 00238 if (isa<GlobalValue>(C)) { 00239 // Initializers for globals are handled explicitly elsewhere. 00240 } else if (isa<ConstantArray>(C) && cast<ConstantArray>(C)->isString()) { 00241 // Do not enumerate the initializers for an array of simple characters. 00242 // The initializers just polute the value table, and we emit the strings 00243 // specially. 00244 } else if (C->getNumOperands()) { 00245 // If a constant has operands, enumerate them. This makes sure that if a 00246 // constant has uses (for example an array of const ints), that they are 00247 // inserted also. 00248 00249 // We prefer to enumerate them with values before we enumerate the user 00250 // itself. This makes it more likely that we can avoid forward references 00251 // in the reader. We know that there can be no cycles in the constants 00252 // graph that don't go through a global variable. 00253 for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 00254 I != E; ++I) 00255 EnumerateValue(*I); 00256 00257 // Finally, add the value. Doing this could make the ValueID reference be 00258 // dangling, don't reuse it. 00259 Values.push_back(std::make_pair(V, 1U)); 00260 ValueMap[V] = Values.size(); 00261 return; 00262 } 00263 } 00264 00265 // Add the value. 00266 Values.push_back(std::make_pair(V, 1U)); 00267 ValueID = Values.size(); 00268 } 00269 00270 00271 void ValueEnumerator::EnumerateType(const Type *Ty) { 00272 unsigned &TypeID = TypeMap[Ty]; 00273 00274 if (TypeID) { 00275 // If we've already seen this type, just increase its occurrence count. 00276 Types[TypeID-1].second++; 00277 return; 00278 } 00279 00280 // First time we saw this type, add it. 00281 Types.push_back(std::make_pair(Ty, 1U)); 00282 TypeID = Types.size(); 00283 00284 // Enumerate subtypes. 00285 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 00286 I != E; ++I) 00287 EnumerateType(*I); 00288 } 00289 00290 // Enumerate the types for the specified value. If the value is a constant, 00291 // walk through it, enumerating the types of the constant. 00292 void ValueEnumerator::EnumerateOperandType(const Value *V) { 00293 EnumerateType(V->getType()); 00294 if (const Constant *C = dyn_cast<Constant>(V)) { 00295 // If this constant is already enumerated, ignore it, we know its type must 00296 // be enumerated. 00297 if (ValueMap.count(V)) return; 00298 00299 // This constant may have operands, make sure to enumerate the types in 00300 // them. 00301 for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) 00302 EnumerateOperandType(C->getOperand(i)); 00303 00304 if (const MDNode *N = dyn_cast<MDNode>(V)) { 00305 for (unsigned i = 0, e = N->getNumElements(); i != e; ++i) { 00306 Value *Elem = N->getElement(i); 00307 if (Elem) 00308 EnumerateOperandType(Elem); 00309 } 00310 } 00311 } else if (isa<MDString>(V) || isa<MDNode>(V)) 00312 EnumerateValue(V); 00313 } 00314 00315 void ValueEnumerator::EnumerateAttributes(const AttrListPtr &PAL) { 00316 if (PAL.isEmpty()) return; // null is always 0. 00317 // Do a lookup. 00318 unsigned &Entry = AttributeMap[PAL.getRawPointer()]; 00319 if (Entry == 0) { 00320 // Never saw this before, add it. 00321 Attributes.push_back(PAL); 00322 Entry = Attributes.size(); 00323 } 00324 } 00325 00326 00327 void ValueEnumerator::incorporateFunction(const Function &F) { 00328 NumModuleValues = Values.size(); 00329 00330 // Adding function arguments to the value table. 00331 for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 00332 I != E; ++I) 00333 EnumerateValue(I); 00334 00335 FirstFuncConstantID = Values.size(); 00336 00337 // Add all function-level constants to the value table. 00338 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 00339 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 00340 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 00341 OI != E; ++OI) { 00342 if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 00343 isa<InlineAsm>(*OI)) 00344 EnumerateValue(*OI); 00345 } 00346 BasicBlocks.push_back(BB); 00347 ValueMap[BB] = BasicBlocks.size(); 00348 } 00349 00350 // Optimize the constant layout. 00351 OptimizeConstants(FirstFuncConstantID, Values.size()); 00352 00353 // Add the function's parameter attributes so they are available for use in 00354 // the function's instruction. 00355 EnumerateAttributes(F.getAttributes()); 00356 00357 FirstInstID = Values.size(); 00358 00359 // Add all of the instructions. 00360 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 00361 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 00362 if (I->getType() != Type::getVoidTy(F.getContext())) 00363 EnumerateValue(I); 00364 } 00365 } 00366 } 00367 00368 void ValueEnumerator::purgeFunction() { 00369 /// Remove purged values from the ValueMap. 00370 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 00371 ValueMap.erase(Values[i].first); 00372 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 00373 ValueMap.erase(BasicBlocks[i]); 00374 00375 Values.resize(NumModuleValues); 00376 BasicBlocks.clear(); 00377 } 00378