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/ADT/STLExtras.h"
00016 #include "llvm/ADT/SmallPtrSet.h"
00017 #include "llvm/IR/Constants.h"
00018 #include "llvm/IR/DerivedTypes.h"
00019 #include "llvm/IR/Instructions.h"
00020 #include "llvm/IR/Module.h"
00021 #include "llvm/IR/ValueSymbolTable.h"
00022 #include "llvm/Support/Debug.h"
00023 #include "llvm/Support/raw_ostream.h"
00024 #include <algorithm>
00025 using namespace llvm;
00026 
00027 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
00028   return V.first->getType()->isIntOrIntVectorTy();
00029 }
00030 
00031 /// ValueEnumerator - Enumerate module-level information.
00032 ValueEnumerator::ValueEnumerator(const Module *M) {
00033   // Enumerate the global variables.
00034   for (Module::const_global_iterator I = M->global_begin(),
00035          E = M->global_end(); I != E; ++I)
00036     EnumerateValue(I);
00037 
00038   // Enumerate the functions.
00039   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
00040     EnumerateValue(I);
00041     EnumerateAttributes(cast<Function>(I)->getAttributes());
00042   }
00043 
00044   // Enumerate the aliases.
00045   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
00046        I != E; ++I)
00047     EnumerateValue(I);
00048 
00049   // Remember what is the cutoff between globalvalue's and other constants.
00050   unsigned FirstConstant = Values.size();
00051 
00052   // Enumerate the global variable initializers.
00053   for (Module::const_global_iterator I = M->global_begin(),
00054          E = M->global_end(); I != E; ++I)
00055     if (I->hasInitializer())
00056       EnumerateValue(I->getInitializer());
00057 
00058   // Enumerate the aliasees.
00059   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
00060        I != E; ++I)
00061     EnumerateValue(I->getAliasee());
00062 
00063   // Enumerate the prefix data constants.
00064   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
00065     if (I->hasPrefixData())
00066       EnumerateValue(I->getPrefixData());
00067 
00068   // Insert constants and metadata that are named at module level into the slot
00069   // pool so that the module symbol table can refer to them...
00070   EnumerateValueSymbolTable(M->getValueSymbolTable());
00071   EnumerateNamedMetadata(M);
00072 
00073   SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
00074 
00075   // Enumerate types used by function bodies and argument lists.
00076   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
00077 
00078     for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00079          I != E; ++I)
00080       EnumerateType(I->getType());
00081 
00082     for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00083       for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
00084         for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
00085              OI != E; ++OI) {
00086           if (MDNode *MD = dyn_cast<MDNode>(*OI))
00087             if (MD->isFunctionLocal() && MD->getFunction())
00088               // These will get enumerated during function-incorporation.
00089               continue;
00090           EnumerateOperandType(*OI);
00091         }
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         // Enumerate metadata attached with this instruction.
00099         MDs.clear();
00100         I->getAllMetadataOtherThanDebugLoc(MDs);
00101         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
00102           EnumerateMetadata(MDs[i].second);
00103 
00104         if (!I->getDebugLoc().isUnknown()) {
00105           MDNode *Scope, *IA;
00106           I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
00107           if (Scope) EnumerateMetadata(Scope);
00108           if (IA) EnumerateMetadata(IA);
00109         }
00110       }
00111   }
00112 
00113   // Optimize constant ordering.
00114   OptimizeConstants(FirstConstant, Values.size());
00115 }
00116 
00117 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
00118   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
00119   assert(I != InstructionMap.end() && "Instruction is not mapped!");
00120   return I->second;
00121 }
00122 
00123 void ValueEnumerator::setInstructionID(const Instruction *I) {
00124   InstructionMap[I] = InstructionCount++;
00125 }
00126 
00127 unsigned ValueEnumerator::getValueID(const Value *V) const {
00128   if (isa<MDNode>(V) || isa<MDString>(V)) {
00129     ValueMapType::const_iterator I = MDValueMap.find(V);
00130     assert(I != MDValueMap.end() && "Value not in slotcalculator!");
00131     return I->second-1;
00132   }
00133 
00134   ValueMapType::const_iterator I = ValueMap.find(V);
00135   assert(I != ValueMap.end() && "Value not in slotcalculator!");
00136   return I->second-1;
00137 }
00138 
00139 void ValueEnumerator::dump() const {
00140   print(dbgs(), ValueMap, "Default");
00141   dbgs() << '\n';
00142   print(dbgs(), MDValueMap, "MetaData");
00143   dbgs() << '\n';
00144 }
00145 
00146 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
00147                             const char *Name) const {
00148 
00149   OS << "Map Name: " << Name << "\n";
00150   OS << "Size: " << Map.size() << "\n";
00151   for (ValueMapType::const_iterator I = Map.begin(),
00152          E = Map.end(); I != E; ++I) {
00153 
00154     const Value *V = I->first;
00155     if (V->hasName())
00156       OS << "Value: " << V->getName();
00157     else
00158       OS << "Value: [null]\n";
00159     V->dump();
00160 
00161     OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
00162     for (const Use &U : V->uses()) {
00163       if (&U != &*V->use_begin())
00164         OS << ",";
00165       if(U->hasName())
00166         OS << " " << U->getName();
00167       else
00168         OS << " [null]";
00169 
00170     }
00171     OS <<  "\n\n";
00172   }
00173 }
00174 
00175 /// OptimizeConstants - Reorder constant pool for denser encoding.
00176 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
00177   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
00178 
00179   std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
00180                    [this](const std::pair<const Value *, unsigned> &LHS,
00181                           const std::pair<const Value *, unsigned> &RHS) {
00182     // Sort by plane.
00183     if (LHS.first->getType() != RHS.first->getType())
00184       return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
00185     // Then by frequency.
00186     return LHS.second > RHS.second;
00187   });
00188 
00189   // Ensure that integer and vector of integer constants are at the start of the
00190   // constant pool.  This is important so that GEP structure indices come before
00191   // gep constant exprs.
00192   std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
00193                  isIntOrIntVectorValue);
00194 
00195   // Rebuild the modified portion of ValueMap.
00196   for (; CstStart != CstEnd; ++CstStart)
00197     ValueMap[Values[CstStart].first] = CstStart+1;
00198 }
00199 
00200 
00201 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
00202 /// table into the values table.
00203 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
00204   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
00205        VI != VE; ++VI)
00206     EnumerateValue(VI->getValue());
00207 }
00208 
00209 /// EnumerateNamedMetadata - Insert all of the values referenced by
00210 /// named metadata in the specified module.
00211 void ValueEnumerator::EnumerateNamedMetadata(const Module *M) {
00212   for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
00213        E = M->named_metadata_end(); I != E; ++I)
00214     EnumerateNamedMDNode(I);
00215 }
00216 
00217 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
00218   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
00219     EnumerateMetadata(MD->getOperand(i));
00220 }
00221 
00222 /// EnumerateMDNodeOperands - Enumerate all non-function-local values
00223 /// and types referenced by the given MDNode.
00224 void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
00225   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00226     if (Value *V = N->getOperand(i)) {
00227       if (isa<MDNode>(V) || isa<MDString>(V))
00228         EnumerateMetadata(V);
00229       else if (!isa<Instruction>(V) && !isa<Argument>(V))
00230         EnumerateValue(V);
00231     } else
00232       EnumerateType(Type::getVoidTy(N->getContext()));
00233   }
00234 }
00235 
00236 void ValueEnumerator::EnumerateMetadata(const Value *MD) {
00237   assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind");
00238 
00239   // Enumerate the type of this value.
00240   EnumerateType(MD->getType());
00241 
00242   const MDNode *N = dyn_cast<MDNode>(MD);
00243 
00244   // In the module-level pass, skip function-local nodes themselves, but
00245   // do walk their operands.
00246   if (N && N->isFunctionLocal() && N->getFunction()) {
00247     EnumerateMDNodeOperands(N);
00248     return;
00249   }
00250 
00251   // Check to see if it's already in!
00252   unsigned &MDValueID = MDValueMap[MD];
00253   if (MDValueID) {
00254     // Increment use count.
00255     MDValues[MDValueID-1].second++;
00256     return;
00257   }
00258   MDValues.push_back(std::make_pair(MD, 1U));
00259   MDValueID = MDValues.size();
00260 
00261   // Enumerate all non-function-local operands.
00262   if (N)
00263     EnumerateMDNodeOperands(N);
00264 }
00265 
00266 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
00267 /// information reachable from the given MDNode.
00268 void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) {
00269   assert(N->isFunctionLocal() && N->getFunction() &&
00270          "EnumerateFunctionLocalMetadata called on non-function-local mdnode!");
00271 
00272   // Enumerate the type of this value.
00273   EnumerateType(N->getType());
00274 
00275   // Check to see if it's already in!
00276   unsigned &MDValueID = MDValueMap[N];
00277   if (MDValueID) {
00278     // Increment use count.
00279     MDValues[MDValueID-1].second++;
00280     return;
00281   }
00282   MDValues.push_back(std::make_pair(N, 1U));
00283   MDValueID = MDValues.size();
00284 
00285   // To incoroporate function-local information visit all function-local
00286   // MDNodes and all function-local values they reference.
00287   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00288     if (Value *V = N->getOperand(i)) {
00289       if (MDNode *O = dyn_cast<MDNode>(V)) {
00290         if (O->isFunctionLocal() && O->getFunction())
00291           EnumerateFunctionLocalMetadata(O);
00292       } else if (isa<Instruction>(V) || isa<Argument>(V))
00293         EnumerateValue(V);
00294     }
00295 
00296   // Also, collect all function-local MDNodes for easy access.
00297   FunctionLocalMDs.push_back(N);
00298 }
00299 
00300 void ValueEnumerator::EnumerateValue(const Value *V) {
00301   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
00302   assert(!isa<MDNode>(V) && !isa<MDString>(V) &&
00303          "EnumerateValue doesn't handle Metadata!");
00304 
00305   // Check to see if it's already in!
00306   unsigned &ValueID = ValueMap[V];
00307   if (ValueID) {
00308     // Increment use count.
00309     Values[ValueID-1].second++;
00310     return;
00311   }
00312 
00313   // Enumerate the type of this value.
00314   EnumerateType(V->getType());
00315 
00316   if (const Constant *C = dyn_cast<Constant>(V)) {
00317     if (isa<GlobalValue>(C)) {
00318       // Initializers for globals are handled explicitly elsewhere.
00319     } else if (C->getNumOperands()) {
00320       // If a constant has operands, enumerate them.  This makes sure that if a
00321       // constant has uses (for example an array of const ints), that they are
00322       // inserted also.
00323 
00324       // We prefer to enumerate them with values before we enumerate the user
00325       // itself.  This makes it more likely that we can avoid forward references
00326       // in the reader.  We know that there can be no cycles in the constants
00327       // graph that don't go through a global variable.
00328       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
00329            I != E; ++I)
00330         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
00331           EnumerateValue(*I);
00332 
00333       // Finally, add the value.  Doing this could make the ValueID reference be
00334       // dangling, don't reuse it.
00335       Values.push_back(std::make_pair(V, 1U));
00336       ValueMap[V] = Values.size();
00337       return;
00338     }
00339   }
00340 
00341   // Add the value.
00342   Values.push_back(std::make_pair(V, 1U));
00343   ValueID = Values.size();
00344 }
00345 
00346 
00347 void ValueEnumerator::EnumerateType(Type *Ty) {
00348   unsigned *TypeID = &TypeMap[Ty];
00349 
00350   // We've already seen this type.
00351   if (*TypeID)
00352     return;
00353 
00354   // If it is a non-anonymous struct, mark the type as being visited so that we
00355   // don't recursively visit it.  This is safe because we allow forward
00356   // references of these in the bitcode reader.
00357   if (StructType *STy = dyn_cast<StructType>(Ty))
00358     if (!STy->isLiteral())
00359       *TypeID = ~0U;
00360 
00361   // Enumerate all of the subtypes before we enumerate this type.  This ensures
00362   // that the type will be enumerated in an order that can be directly built.
00363   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00364        I != E; ++I)
00365     EnumerateType(*I);
00366 
00367   // Refresh the TypeID pointer in case the table rehashed.
00368   TypeID = &TypeMap[Ty];
00369 
00370   // Check to see if we got the pointer another way.  This can happen when
00371   // enumerating recursive types that hit the base case deeper than they start.
00372   //
00373   // If this is actually a struct that we are treating as forward ref'able,
00374   // then emit the definition now that all of its contents are available.
00375   if (*TypeID && *TypeID != ~0U)
00376     return;
00377 
00378   // Add this type now that its contents are all happily enumerated.
00379   Types.push_back(Ty);
00380 
00381   *TypeID = Types.size();
00382 }
00383 
00384 // Enumerate the types for the specified value.  If the value is a constant,
00385 // walk through it, enumerating the types of the constant.
00386 void ValueEnumerator::EnumerateOperandType(const Value *V) {
00387   EnumerateType(V->getType());
00388 
00389   if (const Constant *C = dyn_cast<Constant>(V)) {
00390     // If this constant is already enumerated, ignore it, we know its type must
00391     // be enumerated.
00392     if (ValueMap.count(V)) return;
00393 
00394     // This constant may have operands, make sure to enumerate the types in
00395     // them.
00396     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
00397       const Value *Op = C->getOperand(i);
00398 
00399       // Don't enumerate basic blocks here, this happens as operands to
00400       // blockaddress.
00401       if (isa<BasicBlock>(Op)) continue;
00402 
00403       EnumerateOperandType(Op);
00404     }
00405 
00406     if (const MDNode *N = dyn_cast<MDNode>(V)) {
00407       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00408         if (Value *Elem = N->getOperand(i))
00409           EnumerateOperandType(Elem);
00410     }
00411   } else if (isa<MDString>(V) || isa<MDNode>(V))
00412     EnumerateMetadata(V);
00413 }
00414 
00415 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
00416   if (PAL.isEmpty()) return;  // null is always 0.
00417 
00418   // Do a lookup.
00419   unsigned &Entry = AttributeMap[PAL];
00420   if (Entry == 0) {
00421     // Never saw this before, add it.
00422     Attribute.push_back(PAL);
00423     Entry = Attribute.size();
00424   }
00425 
00426   // Do lookups for all attribute groups.
00427   for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
00428     AttributeSet AS = PAL.getSlotAttributes(i);
00429     unsigned &Entry = AttributeGroupMap[AS];
00430     if (Entry == 0) {
00431       AttributeGroups.push_back(AS);
00432       Entry = AttributeGroups.size();
00433     }
00434   }
00435 }
00436 
00437 void ValueEnumerator::incorporateFunction(const Function &F) {
00438   InstructionCount = 0;
00439   NumModuleValues = Values.size();
00440   NumModuleMDValues = MDValues.size();
00441 
00442   // Adding function arguments to the value table.
00443   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
00444        I != E; ++I)
00445     EnumerateValue(I);
00446 
00447   FirstFuncConstantID = Values.size();
00448 
00449   // Add all function-level constants to the value table.
00450   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
00451     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
00452       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
00453            OI != E; ++OI) {
00454         if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
00455             isa<InlineAsm>(*OI))
00456           EnumerateValue(*OI);
00457       }
00458     BasicBlocks.push_back(BB);
00459     ValueMap[BB] = BasicBlocks.size();
00460   }
00461 
00462   // Optimize the constant layout.
00463   OptimizeConstants(FirstFuncConstantID, Values.size());
00464 
00465   // Add the function's parameter attributes so they are available for use in
00466   // the function's instruction.
00467   EnumerateAttributes(F.getAttributes());
00468 
00469   FirstInstID = Values.size();
00470 
00471   SmallVector<MDNode *, 8> FnLocalMDVector;
00472   // Add all of the instructions.
00473   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
00474     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
00475       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
00476            OI != E; ++OI) {
00477         if (MDNode *MD = dyn_cast<MDNode>(*OI))
00478           if (MD->isFunctionLocal() && MD->getFunction())
00479             // Enumerate metadata after the instructions they might refer to.
00480             FnLocalMDVector.push_back(MD);
00481       }
00482 
00483       SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
00484       I->getAllMetadataOtherThanDebugLoc(MDs);
00485       for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
00486         MDNode *N = MDs[i].second;
00487         if (N->isFunctionLocal() && N->getFunction())
00488           FnLocalMDVector.push_back(N);
00489       }
00490 
00491       if (!I->getType()->isVoidTy())
00492         EnumerateValue(I);
00493     }
00494   }
00495 
00496   // Add all of the function-local metadata.
00497   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
00498     EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
00499 }
00500 
00501 void ValueEnumerator::purgeFunction() {
00502   /// Remove purged values from the ValueMap.
00503   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
00504     ValueMap.erase(Values[i].first);
00505   for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i)
00506     MDValueMap.erase(MDValues[i].first);
00507   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
00508     ValueMap.erase(BasicBlocks[i]);
00509 
00510   Values.resize(NumModuleValues);
00511   MDValues.resize(NumModuleMDValues);
00512   BasicBlocks.clear();
00513   FunctionLocalMDs.clear();
00514 }
00515 
00516 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
00517                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
00518   unsigned Counter = 0;
00519   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00520     IDMap[BB] = ++Counter;
00521 }
00522 
00523 /// getGlobalBasicBlockID - This returns the function-specific ID for the
00524 /// specified basic block.  This is relatively expensive information, so it
00525 /// should only be used by rare constructs such as address-of-label.
00526 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
00527   unsigned &Idx = GlobalBasicBlockIDs[BB];
00528   if (Idx != 0)
00529     return Idx-1;
00530 
00531   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
00532   return getGlobalBasicBlockID(BB);
00533 }
00534