ModuleManager.cpp revision cc71dbee441e97285e86bff48eecfbeab82de7ce
198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor//===--- ModuleManager.cpp - Module Manager ---------------------*- C++ -*-===// 298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// 398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// The LLVM Compiler Infrastructure 498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// 598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// This file is distributed under the University of Illinois Open Source 698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// License. See LICENSE.TXT for details. 798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// 898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor//===----------------------------------------------------------------------===// 998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// 1098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// This file defines the ModuleManager class, which manages a set of loaded 1198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// modules for the ASTReader. 1298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor// 1398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor//===----------------------------------------------------------------------===// 1498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor#include "clang/Serialization/ModuleManager.h" 1598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor#include "llvm/Support/MemoryBuffer.h" 1698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor#include "llvm/Support/raw_ostream.h" 1798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor#include "llvm/Support/system_error.h" 1898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 192492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor#ifndef NDEBUG 202492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor#include "llvm/Support/GraphWriter.h" 212492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor#endif 222492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregorusing namespace clang; 2498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregorusing namespace serialization; 2598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 261a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas GregorModuleFile *ModuleManager::lookup(StringRef Name) { 2798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor const FileEntry *Entry = FileMgr.getFile(Name); 2898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return Modules[Entry]; 2998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 3098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 3198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregorllvm::MemoryBuffer *ModuleManager::lookupBuffer(StringRef Name) { 3298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor const FileEntry *Entry = FileMgr.getFile(Name); 3398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return InMemoryBuffers[Entry]; 3498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 3598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 361a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregorstd::pair<ModuleFile *, bool> 3787e2cfcec7231daaa3f367dc32df74b411251e46Douglas GregorModuleManager::addModule(StringRef FileName, ModuleKind Type, 3887e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor SourceLocation ImportLoc, ModuleFile *ImportedBy, 3987e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor unsigned Generation, std::string &ErrorStr) { 4098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor const FileEntry *Entry = FileMgr.getFile(FileName); 4198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (!Entry && FileName != "-") { 4298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ErrorStr = "file not found"; 431a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor return std::make_pair(static_cast<ModuleFile*>(0), false); 4498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 4598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 4698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Check whether we already loaded this module, before 471a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor ModuleFile *&ModuleEntry = Modules[Entry]; 4898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor bool NewModule = false; 4998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (!ModuleEntry) { 5098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Allocate a new module. 51057df20b3107cef764052d271c89b8591b98b3ceDouglas Gregor ModuleFile *New = new ModuleFile(Type, Generation); 52cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor New->Index = Chain.size(); 5398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor New->FileName = FileName.str(); 54d64c26f6676eef69d1713f353ca8a3c2fe963f17Argyrios Kyrtzidis New->File = Entry; 5587e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor New->ImportLoc = ImportLoc; 5698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Chain.push_back(New); 5798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor NewModule = true; 5898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ModuleEntry = New; 5987e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor 6098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Load the contents of the module 6198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (llvm::MemoryBuffer *Buffer = lookupBuffer(FileName)) { 6298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // The buffer was already provided for us. 6398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor assert(Buffer && "Passed null buffer"); 6498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor New->Buffer.reset(Buffer); 6598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } else { 6698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Open the AST file. 6798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor llvm::error_code ec; 6898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (FileName == "-") { 6998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ec = llvm::MemoryBuffer::getSTDIN(New->Buffer); 7098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (ec) 7198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ErrorStr = ec.message(); 7298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } else 7398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor New->Buffer.reset(FileMgr.getBufferForFile(FileName, &ErrorStr)); 7498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 7598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (!New->Buffer) 761a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor return std::make_pair(static_cast<ModuleFile*>(0), false); 7798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 7898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 7998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Initialize the stream 8098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor New->StreamFile.init((const unsigned char *)New->Buffer->getBufferStart(), 8198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor (const unsigned char *)New->Buffer->getBufferEnd()); } 8298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 8398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (ImportedBy) { 8498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ModuleEntry->ImportedBy.insert(ImportedBy); 8598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ImportedBy->Imports.insert(ModuleEntry); 8698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } else { 8787e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor if (!ModuleEntry->DirectlyImported) 8887e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor ModuleEntry->ImportLoc = ImportLoc; 8987e2cfcec7231daaa3f367dc32df74b411251e46Douglas Gregor 9098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor ModuleEntry->DirectlyImported = true; 9198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 9298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 9398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return std::make_pair(ModuleEntry, NewModule); 9498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 9598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 967cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregornamespace { 977cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor /// \brief Predicate that checks whether a module file occurs within 987cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor /// the given set. 997cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor class IsInModuleFileSet : public std::unary_function<ModuleFile *, bool> { 1007cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor llvm::SmallPtrSet<ModuleFile *, 4> &Removed; 1017cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1027cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor public: 1037cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor IsInModuleFileSet(llvm::SmallPtrSet<ModuleFile *, 4> &Removed) 1047cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor : Removed(Removed) { } 1057cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1067cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor bool operator()(ModuleFile *MF) const { 1077cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor return Removed.count(MF); 1087cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor } 1097cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor }; 1107cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor} 1117cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1127cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregorvoid ModuleManager::removeModules(ModuleIterator first, ModuleIterator last) { 1137cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor if (first == last) 1147cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor return; 1157cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1167cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor // Collect the set of module file pointers that we'll be removing. 1177cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last); 1187cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1197cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor // Remove any references to the now-destroyed modules. 1207cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor IsInModuleFileSet checkInSet(victimSet); 1217cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor for (unsigned i = 0, n = Chain.size(); i != n; ++i) { 1227cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor Chain[i]->ImportedBy.remove_if(checkInSet); 1237cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor } 1247cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1257cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor // Delete the modules and erase them from the various structures. 1267cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor for (ModuleIterator victim = first; victim != last; ++victim) { 1277cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor Modules.erase((*victim)->File); 1287cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor delete *victim; 1297cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor } 1307cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 1317cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor // Remove the modules from the chain. 1327cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor Chain.erase(first, last); 1337cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor} 1347cdd28162dc7ade4b14bf237e87b4bbc17b2f023Douglas Gregor 13598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregorvoid ModuleManager::addInMemoryBuffer(StringRef FileName, 13698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor llvm::MemoryBuffer *Buffer) { 13798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 13898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor const FileEntry *Entry = FileMgr.getVirtualFile(FileName, 13998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Buffer->getBufferSize(), 0); 14098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor InMemoryBuffers[Entry] = Buffer; 14198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 14298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 143d64c26f6676eef69d1713f353ca8a3c2fe963f17Argyrios KyrtzidisModuleManager::ModuleManager(FileManager &FileMgr) : FileMgr(FileMgr) { } 14498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 14598339b96a8089a6da715487e432c5abfca0ca0dfDouglas GregorModuleManager::~ModuleManager() { 14698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor for (unsigned i = 0, e = Chain.size(); i != e; ++i) 14798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor delete Chain[e - i - 1]; 14898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 14998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 1501a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregorvoid ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData), 15198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor void *UserData) { 15298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor unsigned N = size(); 15398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 15498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Record the number of incoming edges for each module. When we 15598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // encounter a module with no incoming edges, push it into the queue 15698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // to seed the queue. 1571a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor SmallVector<ModuleFile *, 4> Queue; 15898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Queue.reserve(N); 159cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor llvm::SmallVector<unsigned, 4> UnusedIncomingEdges; 160cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor UnusedIncomingEdges.reserve(size()); 16198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) { 16298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (unsigned Size = (*M)->ImportedBy.size()) 163cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor UnusedIncomingEdges.push_back(Size); 164cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor else { 165cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor UnusedIncomingEdges.push_back(0); 16698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Queue.push_back(*M); 167cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor } 16898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 169cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor 170cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor llvm::SmallVector<bool, 4> Skipped(size(), false); 17198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor unsigned QueueStart = 0; 17298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor while (QueueStart < Queue.size()) { 1731a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor ModuleFile *CurrentModule = Queue[QueueStart++]; 17498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 17598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Check whether this module should be skipped. 176cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor if (Skipped[CurrentModule->Index]) 17798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor continue; 178cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor Skipped[CurrentModule->Index] = true; 17998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 18098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (Visitor(*CurrentModule, UserData)) { 18198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // The visitor has requested that cut off visitation of any 18298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // module that the current module depends on. To indicate this 18398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // behavior, we mark all of the reachable modules as having N 18498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // incoming edges (which is impossible otherwise). 1851a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor SmallVector<ModuleFile *, 4> Stack; 18698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Stack.push_back(CurrentModule); 187cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor Skipped[CurrentModule->Index] = true; 18898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor while (!Stack.empty()) { 1891a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor ModuleFile *NextModule = Stack.back(); 19098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Stack.pop_back(); 19198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 19298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // For any module that this module depends on, push it on the 19398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // stack (if it hasn't already been marked as visited). 1941a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor for (llvm::SetVector<ModuleFile *>::iterator 195cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor M = NextModule->Imports.begin(), 196cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor MEnd = NextModule->Imports.end(); 19798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor M != MEnd; ++M) { 198cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor if (!Skipped[(*M)->Index]) { 19998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Stack.push_back(*M); 200cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor Skipped[(*M)->Index] = true; 201cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor } 20298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 20398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 20498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor continue; 20598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 20698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 20798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // For any module that this module depends on, push it on the 20898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // stack (if it hasn't already been marked as visited). 209cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor for (llvm::SetVector<ModuleFile *>::iterator 210cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor M = CurrentModule->Imports.begin(), 211cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor MEnd = CurrentModule->Imports.end(); 21298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor M != MEnd; ++M) { 21398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 21498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Remove our current module as an impediment to visiting the 21598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // module we depend on. If we were the last unvisited module 21698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // that depends on this particular module, push it into the 21798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // queue to be visited. 218cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index]; 21998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (NumUnusedEdges && (--NumUnusedEdges == 0)) 22098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor Queue.push_back(*M); 22198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 22298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 22398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 22498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 22598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor/// \brief Perform a depth-first visit of the current module. 2261a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregorstatic bool visitDepthFirst(ModuleFile &M, 2271a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor bool (*Visitor)(ModuleFile &M, bool Preorder, 22898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor void *UserData), 22998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor void *UserData, 230cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor SmallVectorImpl<bool> &Visited) { 23198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Preorder visitation 23298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (Visitor(M, /*Preorder=*/true, UserData)) 23398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return true; 23498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 23598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Visit children 2361a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(), 237cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor IMEnd = M.Imports.end(); 23898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor IM != IMEnd; ++IM) { 239cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor if (Visited[(*IM)->Index]) 24098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor continue; 241cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor Visited[(*IM)->Index] = true; 242cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor 24398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (visitDepthFirst(**IM, Visitor, UserData, Visited)) 24498339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return true; 24598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 24698339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 24798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor // Postorder visitation 24898339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return Visitor(M, /*Preorder=*/false, UserData); 24998339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 25098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor 2511a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregorvoid ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder, 25298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor void *UserData), 25398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor void *UserData) { 254cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor SmallVector<bool, 16> Visited(size(), false); 25598339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor for (unsigned I = 0, N = Chain.size(); I != N; ++I) { 256cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor if (Visited[Chain[I]->Index]) 25798339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor continue; 258cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor Visited[Chain[I]->Index] = true; 259cc71dbee441e97285e86bff48eecfbeab82de7ceDouglas Gregor 26098339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited)) 26198339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor return; 26298339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor } 26398339b96a8089a6da715487e432c5abfca0ca0dfDouglas Gregor} 2642492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2652492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor#ifndef NDEBUG 2662492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregornamespace llvm { 2672492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor template<> 2682492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor struct GraphTraits<ModuleManager> { 2691a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor typedef ModuleFile NodeType; 2701a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType; 2712492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor typedef ModuleManager::ModuleConstIterator nodes_iterator; 2722492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2732492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor static ChildIteratorType child_begin(NodeType *Node) { 2742492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return Node->Imports.begin(); 2752492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 2762492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2772492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor static ChildIteratorType child_end(NodeType *Node) { 2782492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return Node->Imports.end(); 2792492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 2802492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2812492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor static nodes_iterator nodes_begin(const ModuleManager &Manager) { 2822492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return Manager.begin(); 2832492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 2842492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2852492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor static nodes_iterator nodes_end(const ModuleManager &Manager) { 2862492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return Manager.end(); 2872492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 2882492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor }; 2892492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2902492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor template<> 2912492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits { 2922492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor explicit DOTGraphTraits(bool IsSimple = false) 2932492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor : DefaultDOTGraphTraits(IsSimple) { } 2942492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2952492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor static bool renderGraphFromBottomUp() { 2962492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return true; 2972492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 2982492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 2991a4761edca58c6b559de825b9abfb66f7f1ba94aDouglas Gregor std::string getNodeLabel(ModuleFile *M, const ModuleManager&) { 3002492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor return llvm::sys::path::stem(M->FileName); 3012492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor } 3022492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor }; 3032492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor} 3042492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor 3052492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregorvoid ModuleManager::viewGraph() { 3062492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor llvm::ViewGraph(*this, "Modules"); 3072492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor} 3082492c89882b5c5ce03afb4704fee67b7eff8f5eeDouglas Gregor#endif 309