LLVM API Documentation

ValueEnumerator.cpp

Go to the documentation of this file.
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