lib/Bitcode/Writer/ValueEnumerator.cpp

   1 //===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Module.h"
  20 #include "llvm/TypeSymbolTable.h"
  21 #include "llvm/ValueSymbolTable.h"
  22 #include "llvm/Instructions.h"
  23 #include <algorithm>
  24 using namespace llvm;
  25
  26 static bool isIntegerValue(const std::pair<const Value*, unsigned> &V) {
  27   return V.first->getType()->isIntegerTy();
  28 }
  29
  30 /// ValueEnumerator - Enumerate module-level information.
  31 ValueEnumerator::ValueEnumerator(const Module *M) {
  32   // Enumerate the global variables.
  33   for (Module::const_global_iterator I = M->global_begin(),
  34          E = M->global_end(); I != E; ++I)
  35     EnumerateValue(I);
  36
  37   // Enumerate the functions.
  38   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
  39     EnumerateValue(I);
  40     EnumerateAttributes(cast<Function>(I)->getAttributes());
  41   }
  42
  43   // Enumerate the aliases.
  44   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
  45        I != E; ++I)
  46     EnumerateValue(I);
  47
  48   // Remember what is the cutoff between globalvalue's and other constants.
  49   unsigned FirstConstant = Values.size();
  50
  51   // Enumerate the global variable initializers.
  52   for (Module::const_global_iterator I = M->global_begin(),
  53          E = M->global_end(); I != E; ++I)
  54     if (I->hasInitializer())
  55       EnumerateValue(I->getInitializer());
  56
  57   // Enumerate the aliasees.
  58   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
  59        I != E; ++I)
  60     EnumerateValue(I->getAliasee());
  61
  62   // Enumerate types used by the type symbol table.
  63   EnumerateTypeSymbolTable(M->getTypeSymbolTable());
  64
  65   // Insert constants and metadata that are named at module level into the slot
  66   // pool so that the module symbol table can refer to them...
  67   EnumerateValueSymbolTable(M->getValueSymbolTable());
  68   EnumerateNamedMetadata(M);
  69
  70   SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
  71
  72   // Enumerate types used by function bodies and argument lists.
  73   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
  74
  75     for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
  76          I != E; ++I)
  77       EnumerateType(I->getType());
  78
  79     for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
  80       for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
  81         for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
  82              OI != E; ++OI) {
  83           if (MDNode *MD = dyn_cast<MDNode>(*OI))
  84             if (MD->isFunctionLocal() && MD->getFunction())
  85               // These will get enumerated during function-incorporation.
  86               continue;
  87           EnumerateOperandType(*OI);
  88         }
  89         EnumerateType(I->getType());
  90         if (const CallInst *CI = dyn_cast<CallInst>(I))
  91           EnumerateAttributes(CI->getAttributes());
  92         else if (const InvokeInst *II = dyn_cast<InvokeInst>(I))
  93           EnumerateAttributes(II->getAttributes());
  94
  95         // Enumerate metadata attached with this instruction.
  96         MDs.clear();
  97         I->getAllMetadataOtherThanDebugLoc(MDs);
  98         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
  99           EnumerateMetadata(MDs[i].second);
 100
 101         if (!I->getDebugLoc().isUnknown()) {
 102           MDNode *Scope, *IA;
 103           I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
 104           if (Scope) EnumerateMetadata(Scope);
 105           if (IA) EnumerateMetadata(IA);
 106         }
 107       }
 108   }
 109
 110   // Optimize constant ordering.
 111   OptimizeConstants(FirstConstant, Values.size());
 112
 113   OptimizeTypes();
 114
 115   // Now that we rearranged the type table, rebuild TypeMap.
 116   for (unsigned i = 0, e = Types.size(); i != e; ++i)
 117     TypeMap[Types[i]] = i+1;
 118 }
 119
 120 struct TypeAndDeps {
 121   const Type *Ty;
 122   unsigned NumDeps;
 123 };
 124
 125 static int CompareByDeps(const void *a, const void *b) {
 126   const TypeAndDeps &ta = *(const TypeAndDeps*) a;
 127   const TypeAndDeps &tb = *(const TypeAndDeps*) b;
 128   return ta.NumDeps - tb.NumDeps;
 129 }
 130
 131 static void VisitType(const Type *Ty, SmallPtrSet<const Type*, 16> &Visited,
 132                       std::vector<const Type*> &Out) {
 133   if (Visited.count(Ty))
 134     return;
 135
 136   Visited.insert(Ty);
 137
 138   for (Type::subtype_iterator I2 = Ty->subtype_begin(),
 139          E2 = Ty->subtype_end(); I2 != E2; ++I2) {
 140     const Type *InnerType = I2->get();
 141     VisitType(InnerType, Visited, Out);
 142   }
 143
 144   Out.push_back(Ty);
 145 }
 146
 147 void ValueEnumerator::OptimizeTypes(void) {
 148   // If the types form a DAG, this will compute a topological sort and
 149   // no forward references will be needed when reading them in.
 150   // If there are cycles, this is a simple but reasonable heuristic for
 151   // the minimum feedback arc set problem.
 152   const unsigned NumTypes = Types.size();
 153   std::vector<TypeAndDeps> TypeDeps;
 154   TypeDeps.resize(NumTypes);
 155
 156   for (unsigned I = 0; I < NumTypes; ++I) {
 157     const Type *Ty = Types[I];
 158     TypeDeps[I].Ty = Ty;
 159     TypeDeps[I].NumDeps = 0;
 160   }
 161
 162   for (unsigned I = 0; I < NumTypes; ++I) {
 163     const Type *Ty = TypeDeps[I].Ty;
 164     for (Type::subtype_iterator I2 = Ty->subtype_begin(),
 165            E2 = Ty->subtype_end(); I2 != E2; ++I2) {
 166       const Type *InnerType = I2->get();
 167       unsigned InnerIndex = TypeMap.lookup(InnerType) - 1;
 168       TypeDeps[InnerIndex].NumDeps++;
 169     }
 170   }
 171   array_pod_sort(TypeDeps.begin(), TypeDeps.end(), CompareByDeps);
 172
 173   SmallPtrSet<const Type*, 16> Visited;
 174   Types.clear();
 175   Types.reserve(NumTypes);
 176   for (unsigned I = 0; I < NumTypes; ++I) {
 177     VisitType(TypeDeps[I].Ty, Visited, Types);
 178   }
 179 }
 180
 181 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
 182   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
 183   assert (I != InstructionMap.end() && "Instruction is not mapped!");
 184   return I->second;
 185 }
 186
 187 void ValueEnumerator::setInstructionID(const Instruction *I) {
 188   InstructionMap[I] = InstructionCount++;
 189 }
 190
 191 unsigned ValueEnumerator::getValueID(const Value *V) const {
 192   if (isa<MDNode>(V) || isa<MDString>(V)) {
 193     ValueMapType::const_iterator I = MDValueMap.find(V);
 194     assert(I != MDValueMap.end() && "Value not in slotcalculator!");
 195     return I->second-1;
 196   }
 197
 198   ValueMapType::const_iterator I = ValueMap.find(V);
 199   assert(I != ValueMap.end() && "Value not in slotcalculator!");
 200   return I->second-1;
 201 }
 202
 203 // Optimize constant ordering.
 204 namespace {
 205   struct CstSortPredicate {
 206     ValueEnumerator &VE;
 207     explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {}
 208     bool operator()(const std::pair<const Value*, unsigned> &LHS,
 209                     const std::pair<const Value*, unsigned> &RHS) {
 210       // Sort by plane.
 211       if (LHS.first->getType() != RHS.first->getType())
 212         return VE.getTypeID(LHS.first->getType()) <
 213                VE.getTypeID(RHS.first->getType());
 214       // Then by frequency.
 215       return LHS.second > RHS.second;
 216     }
 217   };
 218 }
 219
 220 /// OptimizeConstants - Reorder constant pool for denser encoding.
 221 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
 222   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
 223
 224   CstSortPredicate P(*this);
 225   std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P);
 226
 227   // Ensure that integer constants are at the start of the constant pool.  This
 228   // is important so that GEP structure indices come before gep constant exprs.
 229   std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
 230                  isIntegerValue);
 231
 232   // Rebuild the modified portion of ValueMap.
 233   for (; CstStart != CstEnd; ++CstStart)
 234     ValueMap[Values[CstStart].first] = CstStart+1;
 235 }
 236
 237
 238 /// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol
 239 /// table.
 240 void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) {
 241   for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
 242        TI != TE; ++TI)
 243     EnumerateType(TI->second);
 244 }
 245
 246 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
 247 /// table into the values table.
 248 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
 249   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
 250        VI != VE; ++VI)
 251     EnumerateValue(VI->getValue());
 252 }
 253
 254 /// EnumerateNamedMetadata - Insert all of the values referenced by
 255 /// named metadata in the specified module.
 256 void ValueEnumerator::EnumerateNamedMetadata(const Module *M) {
 257   for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
 258        E = M->named_metadata_end(); I != E; ++I)
 259     EnumerateNamedMDNode(I);
 260 }
 261
 262 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
 263   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
 264     EnumerateMetadata(MD->getOperand(i));
 265 }
 266
 267 /// EnumerateMDNodeOperands - Enumerate all non-function-local values
 268 /// and types referenced by the given MDNode.
 269 void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
 270   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 271     if (Value *V = N->getOperand(i)) {
 272       if (isa<MDNode>(V) || isa<MDString>(V))
 273         EnumerateMetadata(V);
 274       else if (!isa<Instruction>(V) && !isa<Argument>(V))
 275         EnumerateValue(V);
 276     } else
 277       EnumerateType(Type::getVoidTy(N->getContext()));
 278   }
 279 }
 280
 281 void ValueEnumerator::EnumerateMetadata(const Value *MD) {
 282   assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind");
 283
 284   // Enumerate the type of this value.
 285   EnumerateType(MD->getType());
 286
 287   const MDNode *N = dyn_cast<MDNode>(MD);
 288
 289   // In the module-level pass, skip function-local nodes themselves, but
 290   // do walk their operands.
 291   if (N && N->isFunctionLocal() && N->getFunction()) {
 292     EnumerateMDNodeOperands(N);
 293     return;
 294   }
 295
 296   // Check to see if it's already in!
 297   unsigned &MDValueID = MDValueMap[MD];
 298   if (MDValueID) {
 299     // Increment use count.
 300     MDValues[MDValueID-1].second++;
 301     return;
 302   }
 303   MDValues.push_back(std::make_pair(MD, 1U));
 304   MDValueID = MDValues.size();
 305
 306   // Enumerate all non-function-local operands.
 307   if (N)
 308     EnumerateMDNodeOperands(N);
 309 }
 310
 311 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
 312 /// information reachable from the given MDNode.
 313 void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) {
 314   assert(N->isFunctionLocal() && N->getFunction() &&
 315          "EnumerateFunctionLocalMetadata called on non-function-local mdnode!");
 316
 317   // Enumerate the type of this value.
 318   EnumerateType(N->getType());
 319
 320   // Check to see if it's already in!
 321   unsigned &MDValueID = MDValueMap[N];
 322   if (MDValueID) {
 323     // Increment use count.
 324     MDValues[MDValueID-1].second++;
 325     return;
 326   }
 327   MDValues.push_back(std::make_pair(N, 1U));
 328   MDValueID = MDValues.size();
 329
 330   // To incoroporate function-local information visit all function-local
 331   // MDNodes and all function-local values they reference.
 332   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 333     if (Value *V = N->getOperand(i)) {
 334       if (MDNode *O = dyn_cast<MDNode>(V)) {
 335         if (O->isFunctionLocal() && O->getFunction())
 336           EnumerateFunctionLocalMetadata(O);
 337       } else if (isa<Instruction>(V) || isa<Argument>(V))
 338         EnumerateValue(V);
 339     }
 340
 341   // Also, collect all function-local MDNodes for easy access.
 342   FunctionLocalMDs.push_back(N);
 343 }
 344
 345 void ValueEnumerator::EnumerateValue(const Value *V) {
 346   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
 347   assert(!isa<MDNode>(V) && !isa<MDString>(V) &&
 348          "EnumerateValue doesn't handle Metadata!");
 349
 350   // Check to see if it's already in!
 351   unsigned &ValueID = ValueMap[V];
 352   if (ValueID) {
 353     // Increment use count.
 354     Values[ValueID-1].second++;
 355     return;
 356   }
 357
 358   // Enumerate the type of this value.
 359   EnumerateType(V->getType());
 360
 361   if (const Constant *C = dyn_cast<Constant>(V)) {
 362     if (isa<GlobalValue>(C)) {
 363       // Initializers for globals are handled explicitly elsewhere.
 364     } else if (isa<ConstantArray>(C) && cast<ConstantArray>(C)->isString()) {
 365       // Do not enumerate the initializers for an array of simple characters.
 366       // The initializers just pollute the value table, and we emit the strings
 367       // specially.
 368     } else if (C->getNumOperands()) {
 369       // If a constant has operands, enumerate them.  This makes sure that if a
 370       // constant has uses (for example an array of const ints), that they are
 371       // inserted also.
 372
 373       // We prefer to enumerate them with values before we enumerate the user
 374       // itself.  This makes it more likely that we can avoid forward references
 375       // in the reader.  We know that there can be no cycles in the constants
 376       // graph that don't go through a global variable.
 377       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
 378            I != E; ++I)
 379         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
 380           EnumerateValue(*I);
 381
 382       // Finally, add the value.  Doing this could make the ValueID reference be
 383       // dangling, don't reuse it.
 384       Values.push_back(std::make_pair(V, 1U));
 385       ValueMap[V] = Values.size();
 386       return;
 387     }
 388   }
 389
 390   // Add the value.
 391   Values.push_back(std::make_pair(V, 1U));
 392   ValueID = Values.size();
 393 }
 394
 395
 396 void ValueEnumerator::EnumerateType(const Type *Ty) {
 397   unsigned &TypeID = TypeMap[Ty];
 398
 399   // We've already seen this type.
 400   if (TypeID)
 401     return;
 402
 403   // First time we saw this type, add it.
 404   Types.push_back(Ty);
 405   TypeID = Types.size();
 406
 407   // Enumerate subtypes.
 408   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 409        I != E; ++I)
 410     EnumerateType(*I);
 411 }
 412
 413 // Enumerate the types for the specified value.  If the value is a constant,
 414 // walk through it, enumerating the types of the constant.
 415 void ValueEnumerator::EnumerateOperandType(const Value *V) {
 416   EnumerateType(V->getType());
 417
 418   if (const Constant *C = dyn_cast<Constant>(V)) {
 419     // If this constant is already enumerated, ignore it, we know its type must
 420     // be enumerated.
 421     if (ValueMap.count(V)) return;
 422
 423     // This constant may have operands, make sure to enumerate the types in
 424     // them.
 425     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
 426       const Value *Op = C->getOperand(i);
 427
 428       // Don't enumerate basic blocks here, this happens as operands to
 429       // blockaddress.
 430       if (isa<BasicBlock>(Op)) continue;
 431
 432       EnumerateOperandType(Op);
 433     }
 434
 435     if (const MDNode *N = dyn_cast<MDNode>(V)) {
 436       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 437         if (Value *Elem = N->getOperand(i))
 438           EnumerateOperandType(Elem);
 439     }
 440   } else if (isa<MDString>(V) || isa<MDNode>(V))
 441     EnumerateMetadata(V);
 442 }
 443
 444 void ValueEnumerator::EnumerateAttributes(const AttrListPtr &PAL) {
 445   if (PAL.isEmpty()) return;  // null is always 0.
 446   // Do a lookup.
 447   unsigned &Entry = AttributeMap[PAL.getRawPointer()];
 448   if (Entry == 0) {
 449     // Never saw this before, add it.
 450     Attributes.push_back(PAL);
 451     Entry = Attributes.size();
 452   }
 453 }
 454
 455
 456 void ValueEnumerator::incorporateFunction(const Function &F) {
 457   InstructionCount = 0;
 458   NumModuleValues = Values.size();
 459   NumModuleMDValues = MDValues.size();
 460
 461   // Adding function arguments to the value table.
 462   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
 463        I != E; ++I)
 464     EnumerateValue(I);
 465
 466   FirstFuncConstantID = Values.size();
 467
 468   // Add all function-level constants to the value table.
 469   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 470     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
 471       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
 472            OI != E; ++OI) {
 473         if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
 474             isa<InlineAsm>(*OI))
 475           EnumerateValue(*OI);
 476       }
 477     BasicBlocks.push_back(BB);
 478     ValueMap[BB] = BasicBlocks.size();
 479   }
 480
 481   // Optimize the constant layout.
 482   OptimizeConstants(FirstFuncConstantID, Values.size());
 483
 484   // Add the function's parameter attributes so they are available for use in
 485   // the function's instruction.
 486   EnumerateAttributes(F.getAttributes());
 487
 488   FirstInstID = Values.size();
 489
 490   SmallVector<MDNode *, 8> FnLocalMDVector;
 491   // Add all of the instructions.
 492   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 493     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
 494       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
 495            OI != E; ++OI) {
 496         if (MDNode *MD = dyn_cast<MDNode>(*OI))
 497           if (MD->isFunctionLocal() && MD->getFunction())
 498             // Enumerate metadata after the instructions they might refer to.
 499             FnLocalMDVector.push_back(MD);
 500       }
 501
 502       SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
 503       I->getAllMetadataOtherThanDebugLoc(MDs);
 504       for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
 505         MDNode *N = MDs[i].second;
 506         if (N->isFunctionLocal() && N->getFunction())
 507           FnLocalMDVector.push_back(N);
 508       }
 509
 510       if (!I->getType()->isVoidTy())
 511         EnumerateValue(I);
 512     }
 513   }
 514
 515   // Add all of the function-local metadata.
 516   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
 517     EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
 518 }
 519
 520 void ValueEnumerator::purgeFunction() {
 521   /// Remove purged values from the ValueMap.
 522   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
 523     ValueMap.erase(Values[i].first);
 524   for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i)
 525     MDValueMap.erase(MDValues[i].first);
 526   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
 527     ValueMap.erase(BasicBlocks[i]);
 528
 529   Values.resize(NumModuleValues);
 530   MDValues.resize(NumModuleMDValues);
 531   BasicBlocks.clear();
 532   FunctionLocalMDs.clear();
 533 }
 534
 535 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
 536                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
 537   unsigned Counter = 0;
 538   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 539     IDMap[BB] = ++Counter;
 540 }
 541
 542 /// getGlobalBasicBlockID - This returns the function-specific ID for the
 543 /// specified basic block.  This is relatively expensive information, so it
 544 /// should only be used by rare constructs such as address-of-label.
 545 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
 546   unsigned &Idx = GlobalBasicBlockIDs[BB];
 547   if (Idx != 0)
 548     return Idx-1;
 549
 550   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
 551   return getGlobalBasicBlockID(BB);
 552 }
 553