Timer/src/ProcessCallGraph.cc

0001 /*
0002  *
0003  */
0004
0005 #include <cassert>
0006 #include <iostream>
0007 #include <string>
0008 #include <type_traits>
0009 #include <vector>
0010
0011 // boost optional (used by boost graph) results in some false positives with -Wmaybe-uninitialized
0012 #pragma GCC diagnostic push
0013 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
0014 #include <boost/graph/depth_first_search.hpp>
0015 #pragma GCC diagnostic pop
0016
0017 #include "DataFormats/Provenance/interface/ModuleDescription.h"
0018 #include "FWCore/Framework/interface/TriggerNamesService.h"
0019 #include "FWCore/MessageLogger/interface/MessageLogger.h"
0020 #include "FWCore/ParameterSet/interface/ConfigurationDescriptions.h"
0021 #include "FWCore/ParameterSet/interface/ParameterSet.h"
0022 #include "FWCore/ParameterSet/interface/ParameterSetDescription.h"
0023 #include "FWCore/ParameterSet/interface/Registry.h"
0024 #include "FWCore/ServiceRegistry/interface/ActivityRegistry.h"
0025 #include "FWCore/ServiceRegistry/interface/ConsumesInfo.h"
0026 #include "FWCore/ServiceRegistry/interface/PathsAndConsumesOfModulesBase.h"
0027 #include "FWCore/ServiceRegistry/interface/ProcessContext.h"
0028 #include "FWCore/ServiceRegistry/interface/Service.h"
0029 #include "FWCore/Utilities/interface/EDMException.h"
0030 #include "HLTrigger/Timer/interface/ProcessCallGraph.h"
0031
0032 ProcessCallGraph::ProcessCallGraph() = default;
0033
0034 // adaptor to use range-based for loops with boost::graph edges(...) and vertices(...) functions
0035 template <typename I>
0036 struct iterator_pair_as_a_range : std::pair<I, I> {
0037 public:
0038   using std::pair<I, I>::pair;
0039
0040   I begin() { return this->first; }
0041   I end() { return this->second; }
0042 };
0043
0044 template <typename I>
0045 iterator_pair_as_a_range<I> make_range(std::pair<I, I> p) {
0046   return iterator_pair_as_a_range<I>(p);
0047 }
0048
0049 // FIXME
0050 //   - check that the Source has not already been added
0051 void ProcessCallGraph::preSourceConstruction(edm::ModuleDescription const& module) {
0052   // keep track of the Source module id
0053   source_ = module.id();
0054
0055   // create graph vertex for the source module
0056   boost::add_vertex(graph_);
0057   graph_.m_graph[module.id()] = {module, edm::EDMModuleType::kSource, true};
0058 }
0059
0060 // FIXME
0061 //  - check that the Source has already been added
0062 //  - check that all module ids are valid (e.g. subprocesses are not being added in
0063 //    the wrong order)
0064 void ProcessCallGraph::preBeginJob(edm::PathsAndConsumesOfModulesBase const& pathsAndConsumes,
0065                                    edm::ProcessContext const& context) {
0066   unsigned int pid = registerProcess(context);
0067
0068   // work on the full graph (for the main process) or a subgraph (for a subprocess)
0069   GraphType& graph = context.isSubProcess() ? graph_.create_subgraph() : graph_.root();
0070
0071   // set the graph name property to the process name
0072   boost::get_property(graph, boost::graph_name) = context.processName();
0073
0074   // create graph vertices associated to all modules in the process
0075   unsigned int size = pathsAndConsumes.largestModuleID() - boost::num_vertices(graph) + 1;
0076   for (size_t i = 0; i < size; ++i)
0077     boost::add_vertex(graph);
0078
0079   // set the vertices properties (use the module id as the global index into the graph)
0080   std::vector<unsigned int> modules;
0081   modules.reserve(size);
0082   for (edm::ModuleDescription const* module : pathsAndConsumes.allModules()) {
0083     modules.push_back(module->id());
0084     graph_.m_graph[module->id()] = {*module, edmModuleTypeEnum(*module), false};
0085   }
0086
0087   // add graph edges associated to module dependencies
0088   for (edm::ModuleDescription const* consumer : pathsAndConsumes.allModules()) {
0089     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesWhoseProductsAreConsumedBy(consumer->id())) {
0090       // module `consumer' depends on module `module'
0091       boost::add_edge(consumer->id(), module->id(), graph_);
0092     }
0093   }
0094
0095   // extract path names from the TriggerNamesService
0096   edm::service::TriggerNamesService const& tns = *edm::Service<edm::service::TriggerNamesService>();
0097
0098   // extract the details of the paths and endpaths: name, modules on the path, and their dependencies
0099   size = pathsAndConsumes.paths().size();
0100   assert(tns.getTrigPaths().size() == size);
0101   std::vector<PathType> paths;
0102   paths.reserve(size);
0103   for (unsigned int i = 0; i < size; ++i) {
0104     std::vector<unsigned int> modules;
0105     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnPath(i)) {
0106       modules.push_back(module->id());
0107       // mark the modules in the Paths as scheduled
0108       graph_.m_graph[module->id()].scheduled_ = true;
0109     }
0110     auto deps = dependencies(modules);
0111     paths.emplace_back(tns.getTrigPath(i), modules, deps.first, deps.second);
0112   }
0113   size = pathsAndConsumes.endPaths().size();
0114   std::vector<PathType> endPaths;
0115   endPaths.reserve(size);
0116   for (unsigned int i = 0; i < size; ++i) {
0117     std::vector<unsigned int> modules;
0118     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnEndPath(i)) {
0119       modules.push_back(module->id());
0120       // mark the modules in the EndPaths as scheduled
0121       graph_.m_graph[module->id()].scheduled_ = true;
0122     }
0123     auto deps = dependencies(modules);
0124     endPaths.emplace_back(tns.getEndPath(i), modules, deps.first, deps.second);
0125   }
0126
0127   // store the description of process, modules and paths
0128   process_description_.emplace_back(context.processName(), graph, modules, paths, endPaths);
0129   assert(process_description_.size() == pid + 1);
0130
0131   // attach a subprocess to its parent
0132   if (context.isSubProcess()) {
0133     unsigned int parent_pid = processId(context.parentProcessContext());
0134     process_description_[parent_pid].subprocesses_.push_back(pid);
0135   }
0136 }
0137
0138 // number of modules stored in the call graph
0139 unsigned int ProcessCallGraph::size() const { return boost::num_vertices(graph_); }
0140
0141 // retrieve the ModuleDescriptio associated to the given id and vertex
0142 edm::ModuleDescription const& ProcessCallGraph::source() const { return graph_.m_graph[source_].module_; }
0143
0144 // retrieve the ModuleDescription associated to the given id and vertex
0145 edm::ModuleDescription const& ProcessCallGraph::module(unsigned int module) const {
0146   return graph_.m_graph[module].module_;
0147 }
0148
0149 // retrieve the full information for a given module
0150 ProcessCallGraph::NodeType const& ProcessCallGraph::operator[](unsigned int module) const {
0151   return graph_.m_graph[module];
0152 }
0153
0154 // find the dependencies of the given module
0155 std::vector<unsigned int> ProcessCallGraph::depends(unsigned int module) const {
0156   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0157   auto colormap = boost::make_container_vertex_map(colors);
0158
0159   // depht-first visit all vertices starting from the given module
0160   boost::default_dfs_visitor visitor;
0161   boost::depth_first_visit(graph_, module, visitor, colormap);
0162
0163   // count the visited vertices (the `black' ones) in order to properly size the
0164   // output vector; then fill the dependencies with the list of visited nodes
0165   unsigned int size = 0;
0166   for (unsigned int color : colors)
0167     if (boost::black_color == color)
0168       ++size;
0169   std::vector<unsigned int> dependencies(size);
0170   unsigned j = 0;
0171   for (unsigned int i = 0; i < colors.size(); ++i)
0172     if (boost::black_color == colors[i])
0173       dependencies[j++] = i;
0174   assert(size == j);
0175
0176   return dependencies;
0177 }
0178
0179 // find the dependencies of all modules in the given path
0180 //
0181 // return two vector:
0182 //   - the first lists all the dependencies for the whole path
0183 //   - the second lists the one-after-the-last dependency index into the first vector for each module
0184 std::pair<std::vector<unsigned int>, std::vector<unsigned int>> ProcessCallGraph::dependencies(
0185     std::vector<unsigned int> const& path) {
0186   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0187   auto colormap = boost::make_container_vertex_map(colors);
0188
0189   // first, find and count all the path's modules' dependencies
0190   boost::default_dfs_visitor visitor;
0191   for (unsigned int module : path)
0192     boost::depth_first_visit(graph_, module, visitor, colormap);
0193
0194   unsigned int size = 0;
0195   for (unsigned int color : colors)
0196     if (color == 0)
0197       ++size;
0198
0199   // allocate the output vectors
0200   std::vector<unsigned int> dependencies(size);
0201   dependencies.resize(0);
0202   std::vector<unsigned int> indices(path.size());
0203   indices.resize(0);
0204
0205   // reset the color map
0206   for (unsigned int& color : colors)
0207     color = 0;
0208
0209   // find again all the dependencies, and record those associated to each module
0210   struct record_vertices : boost::default_dfs_visitor {
0211     record_vertices(std::vector<unsigned int>& vertices) : vertices_(vertices) {}
0212
0213     void discover_vertex(unsigned int vertex, GraphType const& graph) { vertices_.push_back(vertex); }
0214
0215     std::vector<unsigned int>& vertices_;
0216   };
0217   record_vertices recorder(dependencies);
0218
0219   for (unsigned int module : path) {
0220     // skip modules that have already been added as dependencies
0221     if (colors[module] != boost::black_color)
0222       boost::depth_first_visit(graph_, module, recorder, colormap);
0223     indices.push_back(dependencies.size());
0224   }
0225
0226   return std::make_pair(dependencies, indices);
0227 }
0228
0229 // register a (sub)process and assigns it a "process id"
0230 // if called with a duplicate process name, returns the original process id
0231 unsigned int ProcessCallGraph::registerProcess(edm::ProcessContext const& context) {
0232   static unsigned int s_id = 0;
0233
0234   // registerProcess (called by preBeginJob) must be called for the parent process before its subprocess(es)
0235   if (context.isSubProcess() and process_id_.find(context.parentProcessContext().processName()) == process_id_.end()) {
0236     throw edm::Exception(edm::errors::LogicError)
0237         << "ProcessCallGraph::preBeginJob(): called for subprocess \"" << context.processName() << "\""
0238         << " before being called for its parent process \"" << context.parentProcessContext().processName() << "\"";
0239   }
0240
0241   // registerProcess (called by preBeginJob) should be called once or each (sub)process
0242   auto id = process_id_.find(context.processName());
0243   if (id != process_id_.end()) {
0244     throw edm::Exception(edm::errors::LogicError)
0245         << "ProcessCallGraph::preBeginJob(): called twice for the same "
0246         << (context.isSubProcess() ? "subprocess" : "process") << " " << context.processName();
0247   }
0248
0249   std::tie(id, std::ignore) = process_id_.insert(std::make_pair(context.processName(), s_id++));
0250   return id->second;
0251 }
0252
0253 // retrieve the "process id" of a process, given its ProcessContex
0254 // throws an exception if the (sub)process was not registered
0255 unsigned int ProcessCallGraph::processId(edm::ProcessContext const& context) const {
0256   auto id = process_id_.find(context.processName());
0257   if (id == process_id_.end())
0258     throw edm::Exception(edm::errors::LogicError)
0259         << "ProcessCallGraph::processId(): unexpected " << (context.isSubProcess() ? "subprocess" : "process") << " "
0260         << context.processName();
0261   return id->second;
0262 }
0263
0264 // retrieve the "process id" of a process, given its ProcessContex
0265 // throws an exception if the (sub)process was not registered
0266 unsigned int ProcessCallGraph::processId(std::string const& processName) const {
0267   auto id = process_id_.find(processName);
0268   if (id == process_id_.end())
0269     throw edm::Exception(edm::errors::LogicError)
0270         << "ProcessCallGraph::processId(): unexpected (sub)process " << processName;
0271   return id->second;
0272 }
0273
0274 // retrieve the number of processes
0275 std::vector<ProcessCallGraph::ProcessType> const& ProcessCallGraph::processes() const { return process_description_; }
0276
0277 // retrieve information about a process, given its "process id"
0278 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(unsigned int pid) const {
0279   return process_description_.at(pid);
0280 }
0281
0282 // retrieve information about a process, given its ProcessContex
0283 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(edm::ProcessContext const& context) const {
0284   unsigned int pid = processId(context);
0285   return process_description_[pid];
0286 }
0287
0288 // retrieve information about a process, given its ProcessContex
0289 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(std::string const& processName) const {
0290   unsigned int pid = processId(processName);
0291   return process_description_[pid];
0292 }