Timer/src/ProcessCallGraph.cc

0001 #include <cassert>
0002 #include <string>
0003 #include <vector>
0004
0005 // boost optional (used by boost graph) results in some false positives with -Wmaybe-uninitialized
0006 #pragma GCC diagnostic push
0007 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
0008 #include <boost/graph/depth_first_search.hpp>
0009 #pragma GCC diagnostic pop
0010
0011 #include "DataFormats/Provenance/interface/ModuleDescription.h"
0012 #include "FWCore/Framework/interface/TriggerNamesService.h"
0013 #include "FWCore/ServiceRegistry/interface/PathsAndConsumesOfModulesBase.h"
0014 #include "FWCore/ServiceRegistry/interface/ProcessContext.h"
0015 #include "FWCore/ServiceRegistry/interface/Service.h"
0016 #include "HLTrigger/Timer/interface/ProcessCallGraph.h"
0017
0018 void ProcessCallGraph::preSourceConstruction(edm::ModuleDescription const& module) {
0019   // check that the Source has not already been added
0020   assert(source_ == edm::ModuleDescription::invalidID());
0021
0022   // keep track of the Source module id
0023   source_ = module.id();
0024
0025   // create graph vertex for the source module
0026   boost::add_vertex(graph_);
0027   graph_.m_graph[module.id()] = {module, edm::EDMModuleType::kSource, true};
0028 }
0029
0030 void ProcessCallGraph::lookupInitializationComplete(edm::PathsAndConsumesOfModulesBase const& pathsAndConsumes,
0031                                                     edm::ProcessContext const& context) {
0032   // check that the Source has already been added
0033   assert(source_ != edm::ModuleDescription::invalidID());
0034
0035   // work on the full graph (for the main process)
0036   GraphType& graph = graph_.root();
0037
0038   // set the graph name property to the process name
0039   boost::get_property(graph, boost::graph_name) = context.processName();
0040
0041   // create graph vertices associated to all modules in the process
0042   unsigned int size = pathsAndConsumes.largestModuleID() - boost::num_vertices(graph) + 1;
0043   for (size_t i = 0; i < size; ++i)
0044     boost::add_vertex(graph);
0045
0046   // set the vertices properties (use the module id as the global index into the graph)
0047   std::vector<unsigned int> modules;
0048   modules.reserve(size);
0049   for (edm::ModuleDescription const* module : pathsAndConsumes.allModules()) {
0050     modules.push_back(module->id());
0051     graph_.m_graph[module->id()] = {*module, edmModuleTypeEnum(*module), false};
0052   }
0053
0054   // add graph edges associated to module dependencies
0055   for (edm::ModuleDescription const* consumer : pathsAndConsumes.allModules()) {
0056     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesWhoseProductsAreConsumedBy(consumer->id())) {
0057       // module `consumer' depends on module `module'
0058       boost::add_edge(consumer->id(), module->id(), graph_);
0059     }
0060   }
0061
0062   // extract path names from the TriggerNamesService
0063   edm::service::TriggerNamesService const& tns = *edm::Service<edm::service::TriggerNamesService>();
0064
0065   // extract the details of the paths and endpaths: name, modules on the path, and their dependencies
0066   size = pathsAndConsumes.paths().size();
0067   assert(tns.getTrigPaths().size() == size);
0068   std::vector<PathType> paths;
0069   paths.reserve(size);
0070   for (unsigned int i = 0; i < size; ++i) {
0071     std::vector<unsigned int> modules;
0072     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnPath(i)) {
0073       modules.push_back(module->id());
0074       // mark the modules in the Paths as scheduled
0075       graph_.m_graph[module->id()].scheduled_ = true;
0076     }
0077     auto deps = dependencies(modules);
0078     paths.emplace_back(tns.getTrigPath(i), modules, deps.first, deps.second);
0079   }
0080   size = pathsAndConsumes.endPaths().size();
0081   std::vector<PathType> endPaths;
0082   endPaths.reserve(size);
0083   for (unsigned int i = 0; i < size; ++i) {
0084     std::vector<unsigned int> modules;
0085     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnEndPath(i)) {
0086       modules.push_back(module->id());
0087       // mark the modules in the EndPaths as scheduled
0088       graph_.m_graph[module->id()].scheduled_ = true;
0089     }
0090     auto deps = dependencies(modules);
0091     endPaths.emplace_back(tns.getEndPath(i), modules, deps.first, deps.second);
0092   }
0093
0094   // store the description of process, modules and paths
0095   process_description_ = std::make_unique<ProcessType>(
0096       context.processName(), graph, std::move(modules), std::move(paths), std::move(endPaths));
0097 }
0098
0099 // number of modules stored in the call graph
0100 unsigned int ProcessCallGraph::size() const { return boost::num_vertices(graph_); }
0101
0102 // retrieve the ModuleDescriptio associated to the given id and vertex
0103 edm::ModuleDescription const& ProcessCallGraph::source() const { return graph_.m_graph[source_].module_; }
0104
0105 // retrieve the ModuleDescription associated to the given id and vertex
0106 edm::ModuleDescription const& ProcessCallGraph::module(unsigned int module) const {
0107   return graph_.m_graph[module].module_;
0108 }
0109
0110 // retrieve the full information for a given module
0111 ProcessCallGraph::NodeType const& ProcessCallGraph::operator[](unsigned int module) const {
0112   return graph_.m_graph[module];
0113 }
0114
0115 // find the dependencies of the given module
0116 std::vector<unsigned int> ProcessCallGraph::depends(unsigned int module) const {
0117   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0118   auto colormap = boost::make_container_vertex_map(colors);
0119
0120   // depht-first visit all vertices starting from the given module
0121   boost::default_dfs_visitor visitor;
0122   boost::depth_first_visit(graph_, module, visitor, colormap);
0123
0124   // count the visited vertices (the `black' ones) in order to properly size the
0125   // output vector; then fill the dependencies with the list of visited nodes
0126   unsigned int size = 0;
0127   for (unsigned int color : colors)
0128     if (boost::black_color == color)
0129       ++size;
0130   std::vector<unsigned int> dependencies(size);
0131   unsigned j = 0;
0132   for (unsigned int i = 0; i < colors.size(); ++i)
0133     if (boost::black_color == colors[i])
0134       dependencies[j++] = i;
0135   assert(size == j);
0136
0137   return dependencies;
0138 }
0139
0140 // find the dependencies of all modules in the given path
0141 //
0142 // return two vector:
0143 //   - the first lists all the dependencies for the whole path
0144 //   - the second lists the one-after-the-last dependency index into the first vector for each module
0145 std::pair<std::vector<unsigned int>, std::vector<unsigned int>> ProcessCallGraph::dependencies(
0146     std::vector<unsigned int> const& path) {
0147   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0148   auto colormap = boost::make_container_vertex_map(colors);
0149
0150   // first, find and count all the path's modules' dependencies
0151   boost::default_dfs_visitor visitor;
0152   for (unsigned int module : path)
0153     boost::depth_first_visit(graph_, module, visitor, colormap);
0154
0155   unsigned int size = 0;
0156   for (unsigned int color : colors)
0157     if (color == 0)
0158       ++size;
0159
0160   std::vector<unsigned int> dependencies;
0161   dependencies.reserve(size);
0162   std::vector<unsigned int> indices;
0163   indices.reserve(path.size());
0164
0165   // reset the color map
0166   for (unsigned int& color : colors)
0167     color = 0;
0168
0169   // find again all the dependencies, and record those associated to each module
0170   struct record_vertices : boost::default_dfs_visitor {
0171     record_vertices(std::vector<unsigned int>& vertices) : vertices_(vertices) {}
0172
0173     void discover_vertex(unsigned int vertex, GraphType const& graph) { vertices_.push_back(vertex); }
0174
0175     std::vector<unsigned int>& vertices_;
0176   };
0177   record_vertices recorder(dependencies);
0178
0179   for (unsigned int module : path) {
0180     // skip modules that have already been added as dependencies
0181     if (colors[module] != boost::black_color)
0182       boost::depth_first_visit(graph_, module, recorder, colormap);
0183     indices.push_back(dependencies.size());
0184   }
0185
0186   return std::make_pair(dependencies, indices);
0187 }
0188
0189 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription() const { return *process_description_; }