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/STLExtras.h" 16 #include "llvm/ADT/SmallPtrSet.h" 17 #include "llvm/IR/Constants.h" 18 #include "llvm/IR/DebugInfoMetadata.h" 19 #include "llvm/IR/DerivedTypes.h" 20 #include "llvm/IR/Instructions.h" 21 #include "llvm/IR/Module.h" 22 #include "llvm/IR/UseListOrder.h" 23 #include "llvm/IR/ValueSymbolTable.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include <algorithm> 27 using namespace llvm; 28 29 namespace { 30 struct OrderMap { 31 DenseMap<const Value *, std::pair<unsigned, bool>> IDs; 32 unsigned LastGlobalConstantID; 33 unsigned LastGlobalValueID; 34 35 OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {} 36 37 bool isGlobalConstant(unsigned ID) const { 38 return ID <= LastGlobalConstantID; 39 } 40 bool isGlobalValue(unsigned ID) const { 41 return ID <= LastGlobalValueID && !isGlobalConstant(ID); 42 } 43 44 unsigned size() const { return IDs.size(); } 45 std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; } 46 std::pair<unsigned, bool> lookup(const Value *V) const { 47 return IDs.lookup(V); 48 } 49 void index(const Value *V) { 50 // Explicitly sequence get-size and insert-value operations to avoid UB. 51 unsigned ID = IDs.size() + 1; 52 IDs[V].first = ID; 53 } 54 }; 55 } 56 57 static void orderValue(const Value *V, OrderMap &OM) { 58 if (OM.lookup(V).first) 59 return; 60 61 if (const Constant *C = dyn_cast<Constant>(V)) 62 if (C->getNumOperands() && !isa<GlobalValue>(C)) 63 for (const Value *Op : C->operands()) 64 if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op)) 65 orderValue(Op, OM); 66 67 // Note: we cannot cache this lookup above, since inserting into the map 68 // changes the map's size, and thus affects the other IDs. 69 OM.index(V); 70 } 71 72 static OrderMap orderModule(const Module &M) { 73 // This needs to match the order used by ValueEnumerator::ValueEnumerator() 74 // and ValueEnumerator::incorporateFunction(). 75 OrderMap OM; 76 77 // In the reader, initializers of GlobalValues are set *after* all the 78 // globals have been read. Rather than awkwardly modeling this behaviour 79 // directly in predictValueUseListOrderImpl(), just assign IDs to 80 // initializers of GlobalValues before GlobalValues themselves to model this 81 // implicitly. 82 for (const GlobalVariable &G : M.globals()) 83 if (G.hasInitializer()) 84 if (!isa<GlobalValue>(G.getInitializer())) 85 orderValue(G.getInitializer(), OM); 86 for (const GlobalAlias &A : M.aliases()) 87 if (!isa<GlobalValue>(A.getAliasee())) 88 orderValue(A.getAliasee(), OM); 89 for (const GlobalIFunc &I : M.ifuncs()) 90 if (!isa<GlobalValue>(I.getResolver())) 91 orderValue(I.getResolver(), OM); 92 for (const Function &F : M) { 93 for (const Use &U : F.operands()) 94 if (!isa<GlobalValue>(U.get())) 95 orderValue(U.get(), OM); 96 } 97 OM.LastGlobalConstantID = OM.size(); 98 99 // Initializers of GlobalValues are processed in 100 // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather 101 // than ValueEnumerator, and match the code in predictValueUseListOrderImpl() 102 // by giving IDs in reverse order. 103 // 104 // Since GlobalValues never reference each other directly (just through 105 // initializers), their relative IDs only matter for determining order of 106 // uses in their initializers. 107 for (const Function &F : M) 108 orderValue(&F, OM); 109 for (const GlobalAlias &A : M.aliases()) 110 orderValue(&A, OM); 111 for (const GlobalIFunc &I : M.ifuncs()) 112 orderValue(&I, OM); 113 for (const GlobalVariable &G : M.globals()) 114 orderValue(&G, OM); 115 OM.LastGlobalValueID = OM.size(); 116 117 for (const Function &F : M) { 118 if (F.isDeclaration()) 119 continue; 120 // Here we need to match the union of ValueEnumerator::incorporateFunction() 121 // and WriteFunction(). Basic blocks are implicitly declared before 122 // anything else (by declaring their size). 123 for (const BasicBlock &BB : F) 124 orderValue(&BB, OM); 125 for (const Argument &A : F.args()) 126 orderValue(&A, OM); 127 for (const BasicBlock &BB : F) 128 for (const Instruction &I : BB) 129 for (const Value *Op : I.operands()) 130 if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) || 131 isa<InlineAsm>(*Op)) 132 orderValue(Op, OM); 133 for (const BasicBlock &BB : F) 134 for (const Instruction &I : BB) 135 orderValue(&I, OM); 136 } 137 return OM; 138 } 139 140 static void predictValueUseListOrderImpl(const Value *V, const Function *F, 141 unsigned ID, const OrderMap &OM, 142 UseListOrderStack &Stack) { 143 // Predict use-list order for this one. 144 typedef std::pair<const Use *, unsigned> Entry; 145 SmallVector<Entry, 64> List; 146 for (const Use &U : V->uses()) 147 // Check if this user will be serialized. 148 if (OM.lookup(U.getUser()).first) 149 List.push_back(std::make_pair(&U, List.size())); 150 151 if (List.size() < 2) 152 // We may have lost some users. 153 return; 154 155 bool IsGlobalValue = OM.isGlobalValue(ID); 156 std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) { 157 const Use *LU = L.first; 158 const Use *RU = R.first; 159 if (LU == RU) 160 return false; 161 162 auto LID = OM.lookup(LU->getUser()).first; 163 auto RID = OM.lookup(RU->getUser()).first; 164 165 // Global values are processed in reverse order. 166 // 167 // Moreover, initializers of GlobalValues are set *after* all the globals 168 // have been read (despite having earlier IDs). Rather than awkwardly 169 // modeling this behaviour here, orderModule() has assigned IDs to 170 // initializers of GlobalValues before GlobalValues themselves. 171 if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) 172 return LID < RID; 173 174 // If ID is 4, then expect: 7 6 5 1 2 3. 175 if (LID < RID) { 176 if (RID <= ID) 177 if (!IsGlobalValue) // GlobalValue uses don't get reversed. 178 return true; 179 return false; 180 } 181 if (RID < LID) { 182 if (LID <= ID) 183 if (!IsGlobalValue) // GlobalValue uses don't get reversed. 184 return false; 185 return true; 186 } 187 188 // LID and RID are equal, so we have different operands of the same user. 189 // Assume operands are added in order for all instructions. 190 if (LID <= ID) 191 if (!IsGlobalValue) // GlobalValue uses don't get reversed. 192 return LU->getOperandNo() < RU->getOperandNo(); 193 return LU->getOperandNo() > RU->getOperandNo(); 194 }); 195 196 if (std::is_sorted( 197 List.begin(), List.end(), 198 [](const Entry &L, const Entry &R) { return L.second < R.second; })) 199 // Order is already correct. 200 return; 201 202 // Store the shuffle. 203 Stack.emplace_back(V, F, List.size()); 204 assert(List.size() == Stack.back().Shuffle.size() && "Wrong size"); 205 for (size_t I = 0, E = List.size(); I != E; ++I) 206 Stack.back().Shuffle[I] = List[I].second; 207 } 208 209 static void predictValueUseListOrder(const Value *V, const Function *F, 210 OrderMap &OM, UseListOrderStack &Stack) { 211 auto &IDPair = OM[V]; 212 assert(IDPair.first && "Unmapped value"); 213 if (IDPair.second) 214 // Already predicted. 215 return; 216 217 // Do the actual prediction. 218 IDPair.second = true; 219 if (!V->use_empty() && std::next(V->use_begin()) != V->use_end()) 220 predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack); 221 222 // Recursive descent into constants. 223 if (const Constant *C = dyn_cast<Constant>(V)) 224 if (C->getNumOperands()) // Visit GlobalValues. 225 for (const Value *Op : C->operands()) 226 if (isa<Constant>(Op)) // Visit GlobalValues. 227 predictValueUseListOrder(Op, F, OM, Stack); 228 } 229 230 static UseListOrderStack predictUseListOrder(const Module &M) { 231 OrderMap OM = orderModule(M); 232 233 // Use-list orders need to be serialized after all the users have been added 234 // to a value, or else the shuffles will be incomplete. Store them per 235 // function in a stack. 236 // 237 // Aside from function order, the order of values doesn't matter much here. 238 UseListOrderStack Stack; 239 240 // We want to visit the functions backward now so we can list function-local 241 // constants in the last Function they're used in. Module-level constants 242 // have already been visited above. 243 for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) { 244 const Function &F = *I; 245 if (F.isDeclaration()) 246 continue; 247 for (const BasicBlock &BB : F) 248 predictValueUseListOrder(&BB, &F, OM, Stack); 249 for (const Argument &A : F.args()) 250 predictValueUseListOrder(&A, &F, OM, Stack); 251 for (const BasicBlock &BB : F) 252 for (const Instruction &I : BB) 253 for (const Value *Op : I.operands()) 254 if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues. 255 predictValueUseListOrder(Op, &F, OM, Stack); 256 for (const BasicBlock &BB : F) 257 for (const Instruction &I : BB) 258 predictValueUseListOrder(&I, &F, OM, Stack); 259 } 260 261 // Visit globals last, since the module-level use-list block will be seen 262 // before the function bodies are processed. 263 for (const GlobalVariable &G : M.globals()) 264 predictValueUseListOrder(&G, nullptr, OM, Stack); 265 for (const Function &F : M) 266 predictValueUseListOrder(&F, nullptr, OM, Stack); 267 for (const GlobalAlias &A : M.aliases()) 268 predictValueUseListOrder(&A, nullptr, OM, Stack); 269 for (const GlobalIFunc &I : M.ifuncs()) 270 predictValueUseListOrder(&I, nullptr, OM, Stack); 271 for (const GlobalVariable &G : M.globals()) 272 if (G.hasInitializer()) 273 predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack); 274 for (const GlobalAlias &A : M.aliases()) 275 predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack); 276 for (const GlobalIFunc &I : M.ifuncs()) 277 predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack); 278 for (const Function &F : M) { 279 for (const Use &U : F.operands()) 280 predictValueUseListOrder(U.get(), nullptr, OM, Stack); 281 } 282 283 return Stack; 284 } 285 286 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { 287 return V.first->getType()->isIntOrIntVectorTy(); 288 } 289 290 ValueEnumerator::ValueEnumerator(const Module &M, 291 bool ShouldPreserveUseListOrder) 292 : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) { 293 if (ShouldPreserveUseListOrder) 294 UseListOrders = predictUseListOrder(M); 295 296 // Enumerate the global variables. 297 for (const GlobalVariable &GV : M.globals()) 298 EnumerateValue(&GV); 299 300 // Enumerate the functions. 301 for (const Function & F : M) { 302 EnumerateValue(&F); 303 EnumerateAttributes(F.getAttributes()); 304 } 305 306 // Enumerate the aliases. 307 for (const GlobalAlias &GA : M.aliases()) 308 EnumerateValue(&GA); 309 310 // Enumerate the ifuncs. 311 for (const GlobalIFunc &GIF : M.ifuncs()) 312 EnumerateValue(&GIF); 313 314 // Remember what is the cutoff between globalvalue's and other constants. 315 unsigned FirstConstant = Values.size(); 316 317 // Enumerate the global variable initializers. 318 for (const GlobalVariable &GV : M.globals()) 319 if (GV.hasInitializer()) 320 EnumerateValue(GV.getInitializer()); 321 322 // Enumerate the aliasees. 323 for (const GlobalAlias &GA : M.aliases()) 324 EnumerateValue(GA.getAliasee()); 325 326 // Enumerate the ifunc resolvers. 327 for (const GlobalIFunc &GIF : M.ifuncs()) 328 EnumerateValue(GIF.getResolver()); 329 330 // Enumerate any optional Function data. 331 for (const Function &F : M) 332 for (const Use &U : F.operands()) 333 EnumerateValue(U.get()); 334 335 // Enumerate the metadata type. 336 // 337 // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode 338 // only encodes the metadata type when it's used as a value. 339 EnumerateType(Type::getMetadataTy(M.getContext())); 340 341 // Insert constants and metadata that are named at module level into the slot 342 // pool so that the module symbol table can refer to them... 343 EnumerateValueSymbolTable(M.getValueSymbolTable()); 344 EnumerateNamedMetadata(M); 345 346 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs; 347 for (const GlobalVariable &GV : M.globals()) { 348 MDs.clear(); 349 GV.getAllMetadata(MDs); 350 for (const auto &I : MDs) 351 // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer 352 // to write metadata to the global variable's own metadata block 353 // (PR28134). 354 EnumerateMetadata(nullptr, I.second); 355 } 356 357 // Enumerate types used by function bodies and argument lists. 358 for (const Function &F : M) { 359 for (const Argument &A : F.args()) 360 EnumerateType(A.getType()); 361 362 // Enumerate metadata attached to this function. 363 MDs.clear(); 364 F.getAllMetadata(MDs); 365 for (const auto &I : MDs) 366 EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second); 367 368 for (const BasicBlock &BB : F) 369 for (const Instruction &I : BB) { 370 for (const Use &Op : I.operands()) { 371 auto *MD = dyn_cast<MetadataAsValue>(&Op); 372 if (!MD) { 373 EnumerateOperandType(Op); 374 continue; 375 } 376 377 // Local metadata is enumerated during function-incorporation. 378 if (isa<LocalAsMetadata>(MD->getMetadata())) 379 continue; 380 381 EnumerateMetadata(&F, MD->getMetadata()); 382 } 383 EnumerateType(I.getType()); 384 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 385 EnumerateAttributes(CI->getAttributes()); 386 else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) 387 EnumerateAttributes(II->getAttributes()); 388 389 // Enumerate metadata attached with this instruction. 390 MDs.clear(); 391 I.getAllMetadataOtherThanDebugLoc(MDs); 392 for (unsigned i = 0, e = MDs.size(); i != e; ++i) 393 EnumerateMetadata(&F, MDs[i].second); 394 395 // Don't enumerate the location directly -- it has a special record 396 // type -- but enumerate its operands. 397 if (DILocation *L = I.getDebugLoc()) 398 for (const Metadata *Op : L->operands()) 399 EnumerateMetadata(&F, Op); 400 } 401 } 402 403 // Optimize constant ordering. 404 OptimizeConstants(FirstConstant, Values.size()); 405 406 // Organize metadata ordering. 407 organizeMetadata(); 408 } 409 410 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { 411 InstructionMapType::const_iterator I = InstructionMap.find(Inst); 412 assert(I != InstructionMap.end() && "Instruction is not mapped!"); 413 return I->second; 414 } 415 416 unsigned ValueEnumerator::getComdatID(const Comdat *C) const { 417 unsigned ComdatID = Comdats.idFor(C); 418 assert(ComdatID && "Comdat not found!"); 419 return ComdatID; 420 } 421 422 void ValueEnumerator::setInstructionID(const Instruction *I) { 423 InstructionMap[I] = InstructionCount++; 424 } 425 426 unsigned ValueEnumerator::getValueID(const Value *V) const { 427 if (auto *MD = dyn_cast<MetadataAsValue>(V)) 428 return getMetadataID(MD->getMetadata()); 429 430 ValueMapType::const_iterator I = ValueMap.find(V); 431 assert(I != ValueMap.end() && "Value not in slotcalculator!"); 432 return I->second-1; 433 } 434 435 LLVM_DUMP_METHOD void ValueEnumerator::dump() const { 436 print(dbgs(), ValueMap, "Default"); 437 dbgs() << '\n'; 438 print(dbgs(), MetadataMap, "MetaData"); 439 dbgs() << '\n'; 440 } 441 442 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, 443 const char *Name) const { 444 445 OS << "Map Name: " << Name << "\n"; 446 OS << "Size: " << Map.size() << "\n"; 447 for (ValueMapType::const_iterator I = Map.begin(), 448 E = Map.end(); I != E; ++I) { 449 450 const Value *V = I->first; 451 if (V->hasName()) 452 OS << "Value: " << V->getName(); 453 else 454 OS << "Value: [null]\n"; 455 V->dump(); 456 457 OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):"; 458 for (const Use &U : V->uses()) { 459 if (&U != &*V->use_begin()) 460 OS << ","; 461 if(U->hasName()) 462 OS << " " << U->getName(); 463 else 464 OS << " [null]"; 465 466 } 467 OS << "\n\n"; 468 } 469 } 470 471 void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map, 472 const char *Name) const { 473 474 OS << "Map Name: " << Name << "\n"; 475 OS << "Size: " << Map.size() << "\n"; 476 for (auto I = Map.begin(), E = Map.end(); I != E; ++I) { 477 const Metadata *MD = I->first; 478 OS << "Metadata: slot = " << I->second.ID << "\n"; 479 OS << "Metadata: function = " << I->second.F << "\n"; 480 MD->print(OS); 481 OS << "\n"; 482 } 483 } 484 485 /// OptimizeConstants - Reorder constant pool for denser encoding. 486 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 487 if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 488 489 if (ShouldPreserveUseListOrder) 490 // Optimizing constants makes the use-list order difficult to predict. 491 // Disable it for now when trying to preserve the order. 492 return; 493 494 std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd, 495 [this](const std::pair<const Value *, unsigned> &LHS, 496 const std::pair<const Value *, unsigned> &RHS) { 497 // Sort by plane. 498 if (LHS.first->getType() != RHS.first->getType()) 499 return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType()); 500 // Then by frequency. 501 return LHS.second > RHS.second; 502 }); 503 504 // Ensure that integer and vector of integer constants are at the start of the 505 // constant pool. This is important so that GEP structure indices come before 506 // gep constant exprs. 507 std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd, 508 isIntOrIntVectorValue); 509 510 // Rebuild the modified portion of ValueMap. 511 for (; CstStart != CstEnd; ++CstStart) 512 ValueMap[Values[CstStart].first] = CstStart+1; 513 } 514 515 516 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 517 /// table into the values table. 518 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 519 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 520 VI != VE; ++VI) 521 EnumerateValue(VI->getValue()); 522 } 523 524 /// Insert all of the values referenced by named metadata in the specified 525 /// module. 526 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) { 527 for (const auto &I : M.named_metadata()) 528 EnumerateNamedMDNode(&I); 529 } 530 531 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { 532 for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) 533 EnumerateMetadata(nullptr, MD->getOperand(i)); 534 } 535 536 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const { 537 return F ? getValueID(F) + 1 : 0; 538 } 539 540 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) { 541 EnumerateMetadata(getMetadataFunctionID(F), MD); 542 } 543 544 void ValueEnumerator::EnumerateFunctionLocalMetadata( 545 const Function &F, const LocalAsMetadata *Local) { 546 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local); 547 } 548 549 void ValueEnumerator::dropFunctionFromMetadata( 550 MetadataMapType::value_type &FirstMD) { 551 SmallVector<const MDNode *, 64> Worklist; 552 auto push = [this, &Worklist](MetadataMapType::value_type &MD) { 553 auto &Entry = MD.second; 554 555 // Nothing to do if this metadata isn't tagged. 556 if (!Entry.F) 557 return; 558 559 // Drop the function tag. 560 Entry.F = 0; 561 562 // If this is has an ID and is an MDNode, then its operands have entries as 563 // well. We need to drop the function from them too. 564 if (Entry.ID) 565 if (auto *N = dyn_cast<MDNode>(MD.first)) 566 Worklist.push_back(N); 567 }; 568 push(FirstMD); 569 while (!Worklist.empty()) 570 for (const Metadata *Op : Worklist.pop_back_val()->operands()) { 571 if (!Op) 572 continue; 573 auto MD = MetadataMap.find(Op); 574 if (MD != MetadataMap.end()) 575 push(*MD); 576 } 577 } 578 579 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) { 580 // It's vital for reader efficiency that uniqued subgraphs are done in 581 // post-order; it's expensive when their operands have forward references. 582 // If a distinct node is referenced from a uniqued node, it'll be delayed 583 // until the uniqued subgraph has been completely traversed. 584 SmallVector<const MDNode *, 32> DelayedDistinctNodes; 585 586 // Start by enumerating MD, and then work through its transitive operands in 587 // post-order. This requires a depth-first search. 588 SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist; 589 if (const MDNode *N = enumerateMetadataImpl(F, MD)) 590 Worklist.push_back(std::make_pair(N, N->op_begin())); 591 592 while (!Worklist.empty()) { 593 const MDNode *N = Worklist.back().first; 594 595 // Enumerate operands until we hit a new node. We need to traverse these 596 // nodes' operands before visiting the rest of N's operands. 597 MDNode::op_iterator I = std::find_if( 598 Worklist.back().second, N->op_end(), 599 [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); }); 600 if (I != N->op_end()) { 601 auto *Op = cast<MDNode>(*I); 602 Worklist.back().second = ++I; 603 604 // Delay traversing Op if it's a distinct node and N is uniqued. 605 if (Op->isDistinct() && !N->isDistinct()) 606 DelayedDistinctNodes.push_back(Op); 607 else 608 Worklist.push_back(std::make_pair(Op, Op->op_begin())); 609 continue; 610 } 611 612 // All the operands have been visited. Now assign an ID. 613 Worklist.pop_back(); 614 MDs.push_back(N); 615 MetadataMap[N].ID = MDs.size(); 616 617 // Flush out any delayed distinct nodes; these are all the distinct nodes 618 // that are leaves in last uniqued subgraph. 619 if (Worklist.empty() || Worklist.back().first->isDistinct()) { 620 for (const MDNode *N : DelayedDistinctNodes) 621 Worklist.push_back(std::make_pair(N, N->op_begin())); 622 DelayedDistinctNodes.clear(); 623 } 624 } 625 } 626 627 const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) { 628 if (!MD) 629 return nullptr; 630 631 assert( 632 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) && 633 "Invalid metadata kind"); 634 635 auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F))); 636 MDIndex &Entry = Insertion.first->second; 637 if (!Insertion.second) { 638 // Already mapped. If F doesn't match the function tag, drop it. 639 if (Entry.hasDifferentFunction(F)) 640 dropFunctionFromMetadata(*Insertion.first); 641 return nullptr; 642 } 643 644 // Don't assign IDs to metadata nodes. 645 if (auto *N = dyn_cast<MDNode>(MD)) 646 return N; 647 648 // Save the metadata. 649 MDs.push_back(MD); 650 Entry.ID = MDs.size(); 651 652 // Enumerate the constant, if any. 653 if (auto *C = dyn_cast<ConstantAsMetadata>(MD)) 654 EnumerateValue(C->getValue()); 655 656 return nullptr; 657 } 658 659 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata 660 /// information reachable from the metadata. 661 void ValueEnumerator::EnumerateFunctionLocalMetadata( 662 unsigned F, const LocalAsMetadata *Local) { 663 assert(F && "Expected a function"); 664 665 // Check to see if it's already in! 666 MDIndex &Index = MetadataMap[Local]; 667 if (Index.ID) { 668 assert(Index.F == F && "Expected the same function"); 669 return; 670 } 671 672 MDs.push_back(Local); 673 Index.F = F; 674 Index.ID = MDs.size(); 675 676 EnumerateValue(Local->getValue()); 677 } 678 679 static unsigned getMetadataTypeOrder(const Metadata *MD) { 680 // Strings are emitted in bulk and must come first. 681 if (isa<MDString>(MD)) 682 return 0; 683 684 // ConstantAsMetadata doesn't reference anything. We may as well shuffle it 685 // to the front since we can detect it. 686 auto *N = dyn_cast<MDNode>(MD); 687 if (!N) 688 return 1; 689 690 // The reader is fast forward references for distinct node operands, but slow 691 // when uniqued operands are unresolved. 692 return N->isDistinct() ? 2 : 3; 693 } 694 695 void ValueEnumerator::organizeMetadata() { 696 assert(MetadataMap.size() == MDs.size() && 697 "Metadata map and vector out of sync"); 698 699 if (MDs.empty()) 700 return; 701 702 // Copy out the index information from MetadataMap in order to choose a new 703 // order. 704 SmallVector<MDIndex, 64> Order; 705 Order.reserve(MetadataMap.size()); 706 for (const Metadata *MD : MDs) 707 Order.push_back(MetadataMap.lookup(MD)); 708 709 // Partition: 710 // - by function, then 711 // - by isa<MDString> 712 // and then sort by the original/current ID. Since the IDs are guaranteed to 713 // be unique, the result of std::sort will be deterministic. There's no need 714 // for std::stable_sort. 715 std::sort(Order.begin(), Order.end(), [this](MDIndex LHS, MDIndex RHS) { 716 return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) < 717 std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID); 718 }); 719 720 // Rebuild MDs, index the metadata ranges for each function in FunctionMDs, 721 // and fix up MetadataMap. 722 std::vector<const Metadata *> OldMDs = std::move(MDs); 723 MDs.reserve(OldMDs.size()); 724 for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) { 725 auto *MD = Order[I].get(OldMDs); 726 MDs.push_back(MD); 727 MetadataMap[MD].ID = I + 1; 728 if (isa<MDString>(MD)) 729 ++NumMDStrings; 730 } 731 732 // Return early if there's nothing for the functions. 733 if (MDs.size() == Order.size()) 734 return; 735 736 // Build the function metadata ranges. 737 MDRange R; 738 FunctionMDs.reserve(OldMDs.size()); 739 unsigned PrevF = 0; 740 for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E; 741 ++I) { 742 unsigned F = Order[I].F; 743 if (!PrevF) { 744 PrevF = F; 745 } else if (PrevF != F) { 746 R.Last = FunctionMDs.size(); 747 std::swap(R, FunctionMDInfo[PrevF]); 748 R.First = FunctionMDs.size(); 749 750 ID = MDs.size(); 751 PrevF = F; 752 } 753 754 auto *MD = Order[I].get(OldMDs); 755 FunctionMDs.push_back(MD); 756 MetadataMap[MD].ID = ++ID; 757 if (isa<MDString>(MD)) 758 ++R.NumStrings; 759 } 760 R.Last = FunctionMDs.size(); 761 FunctionMDInfo[PrevF] = R; 762 } 763 764 void ValueEnumerator::incorporateFunctionMetadata(const Function &F) { 765 NumModuleMDs = MDs.size(); 766 767 auto R = FunctionMDInfo.lookup(getValueID(&F) + 1); 768 NumMDStrings = R.NumStrings; 769 MDs.insert(MDs.end(), FunctionMDs.begin() + R.First, 770 FunctionMDs.begin() + R.Last); 771 } 772 773 void ValueEnumerator::EnumerateValue(const Value *V) { 774 assert(!V->getType()->isVoidTy() && "Can't insert void values!"); 775 assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!"); 776 777 // Check to see if it's already in! 778 unsigned &ValueID = ValueMap[V]; 779 if (ValueID) { 780 // Increment use count. 781 Values[ValueID-1].second++; 782 return; 783 } 784 785 if (auto *GO = dyn_cast<GlobalObject>(V)) 786 if (const Comdat *C = GO->getComdat()) 787 Comdats.insert(C); 788 789 // Enumerate the type of this value. 790 EnumerateType(V->getType()); 791 792 if (const Constant *C = dyn_cast<Constant>(V)) { 793 if (isa<GlobalValue>(C)) { 794 // Initializers for globals are handled explicitly elsewhere. 795 } else if (C->getNumOperands()) { 796 // If a constant has operands, enumerate them. This makes sure that if a 797 // constant has uses (for example an array of const ints), that they are 798 // inserted also. 799 800 // We prefer to enumerate them with values before we enumerate the user 801 // itself. This makes it more likely that we can avoid forward references 802 // in the reader. We know that there can be no cycles in the constants 803 // graph that don't go through a global variable. 804 for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 805 I != E; ++I) 806 if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. 807 EnumerateValue(*I); 808 809 // Finally, add the value. Doing this could make the ValueID reference be 810 // dangling, don't reuse it. 811 Values.push_back(std::make_pair(V, 1U)); 812 ValueMap[V] = Values.size(); 813 return; 814 } 815 } 816 817 // Add the value. 818 Values.push_back(std::make_pair(V, 1U)); 819 ValueID = Values.size(); 820 } 821 822 823 void ValueEnumerator::EnumerateType(Type *Ty) { 824 unsigned *TypeID = &TypeMap[Ty]; 825 826 // We've already seen this type. 827 if (*TypeID) 828 return; 829 830 // If it is a non-anonymous struct, mark the type as being visited so that we 831 // don't recursively visit it. This is safe because we allow forward 832 // references of these in the bitcode reader. 833 if (StructType *STy = dyn_cast<StructType>(Ty)) 834 if (!STy->isLiteral()) 835 *TypeID = ~0U; 836 837 // Enumerate all of the subtypes before we enumerate this type. This ensures 838 // that the type will be enumerated in an order that can be directly built. 839 for (Type *SubTy : Ty->subtypes()) 840 EnumerateType(SubTy); 841 842 // Refresh the TypeID pointer in case the table rehashed. 843 TypeID = &TypeMap[Ty]; 844 845 // Check to see if we got the pointer another way. This can happen when 846 // enumerating recursive types that hit the base case deeper than they start. 847 // 848 // If this is actually a struct that we are treating as forward ref'able, 849 // then emit the definition now that all of its contents are available. 850 if (*TypeID && *TypeID != ~0U) 851 return; 852 853 // Add this type now that its contents are all happily enumerated. 854 Types.push_back(Ty); 855 856 *TypeID = Types.size(); 857 } 858 859 // Enumerate the types for the specified value. If the value is a constant, 860 // walk through it, enumerating the types of the constant. 861 void ValueEnumerator::EnumerateOperandType(const Value *V) { 862 EnumerateType(V->getType()); 863 864 assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand"); 865 866 const Constant *C = dyn_cast<Constant>(V); 867 if (!C) 868 return; 869 870 // If this constant is already enumerated, ignore it, we know its type must 871 // be enumerated. 872 if (ValueMap.count(C)) 873 return; 874 875 // This constant may have operands, make sure to enumerate the types in 876 // them. 877 for (const Value *Op : C->operands()) { 878 // Don't enumerate basic blocks here, this happens as operands to 879 // blockaddress. 880 if (isa<BasicBlock>(Op)) 881 continue; 882 883 EnumerateOperandType(Op); 884 } 885 } 886 887 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { 888 if (PAL.isEmpty()) return; // null is always 0. 889 890 // Do a lookup. 891 unsigned &Entry = AttributeMap[PAL]; 892 if (Entry == 0) { 893 // Never saw this before, add it. 894 Attribute.push_back(PAL); 895 Entry = Attribute.size(); 896 } 897 898 // Do lookups for all attribute groups. 899 for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) { 900 AttributeSet AS = PAL.getSlotAttributes(i); 901 unsigned &Entry = AttributeGroupMap[AS]; 902 if (Entry == 0) { 903 AttributeGroups.push_back(AS); 904 Entry = AttributeGroups.size(); 905 } 906 } 907 } 908 909 void ValueEnumerator::incorporateFunction(const Function &F) { 910 InstructionCount = 0; 911 NumModuleValues = Values.size(); 912 913 // Add global metadata to the function block. This doesn't include 914 // LocalAsMetadata. 915 incorporateFunctionMetadata(F); 916 917 // Adding function arguments to the value table. 918 for (const auto &I : F.args()) 919 EnumerateValue(&I); 920 921 FirstFuncConstantID = Values.size(); 922 923 // Add all function-level constants to the value table. 924 for (const BasicBlock &BB : F) { 925 for (const Instruction &I : BB) 926 for (const Use &OI : I.operands()) { 927 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI)) 928 EnumerateValue(OI); 929 } 930 BasicBlocks.push_back(&BB); 931 ValueMap[&BB] = BasicBlocks.size(); 932 } 933 934 // Optimize the constant layout. 935 OptimizeConstants(FirstFuncConstantID, Values.size()); 936 937 // Add the function's parameter attributes so they are available for use in 938 // the function's instruction. 939 EnumerateAttributes(F.getAttributes()); 940 941 FirstInstID = Values.size(); 942 943 SmallVector<LocalAsMetadata *, 8> FnLocalMDVector; 944 // Add all of the instructions. 945 for (const BasicBlock &BB : F) { 946 for (const Instruction &I : BB) { 947 for (const Use &OI : I.operands()) { 948 if (auto *MD = dyn_cast<MetadataAsValue>(&OI)) 949 if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) 950 // Enumerate metadata after the instructions they might refer to. 951 FnLocalMDVector.push_back(Local); 952 } 953 954 if (!I.getType()->isVoidTy()) 955 EnumerateValue(&I); 956 } 957 } 958 959 // Add all of the function-local metadata. 960 for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) { 961 // At this point, every local values have been incorporated, we shouldn't 962 // have a metadata operand that references a value that hasn't been seen. 963 assert(ValueMap.count(FnLocalMDVector[i]->getValue()) && 964 "Missing value for metadata operand"); 965 EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]); 966 } 967 } 968 969 void ValueEnumerator::purgeFunction() { 970 /// Remove purged values from the ValueMap. 971 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 972 ValueMap.erase(Values[i].first); 973 for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i) 974 MetadataMap.erase(MDs[i]); 975 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 976 ValueMap.erase(BasicBlocks[i]); 977 978 Values.resize(NumModuleValues); 979 MDs.resize(NumModuleMDs); 980 BasicBlocks.clear(); 981 NumMDStrings = 0; 982 } 983 984 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F, 985 DenseMap<const BasicBlock*, unsigned> &IDMap) { 986 unsigned Counter = 0; 987 for (const BasicBlock &BB : *F) 988 IDMap[&BB] = ++Counter; 989 } 990 991 /// getGlobalBasicBlockID - This returns the function-specific ID for the 992 /// specified basic block. This is relatively expensive information, so it 993 /// should only be used by rare constructs such as address-of-label. 994 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { 995 unsigned &Idx = GlobalBasicBlockIDs[BB]; 996 if (Idx != 0) 997 return Idx-1; 998 999 IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); 1000 return getGlobalBasicBlockID(BB); 1001 } 1002 1003 uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const { 1004 return Log2_32_Ceil(getTypes().size() + 1); 1005 } 1006