source: icGREP/icgrep-devel/icgrep/kernels/pipeline/pipeline_analysis.hpp @ 6186

Last change on this file since 6186 was 6186, checked in by cameron, 5 months ago

Various clean-ups

File size: 10.8 KB
Line 
1#include "pipeline_compiler.hpp"
2#include <boost/graph/topological_sort.hpp>
3#include <util/extended_boost_graph_containers.h>
4
5namespace kernel {
6
7#warning TODO: support call bindings that produce output that are inputs of other call bindings or become scalar outputs of the pipeline
8
9namespace {
10
11    using ScalarDependencyMap = RelationshipMap<ScalarDependencyGraph::vertex_descriptor>;
12
13    void enumerateScalarProducerBindings(const unsigned producerVertex, const Bindings & bindings, ScalarDependencyGraph & G, ScalarDependencyMap & M) {
14        const auto n = bindings.size();
15        for (unsigned i = 0; i < n; ++i) {
16            const Relationship * const rel = getRelationship(bindings[i]);
17            assert (M.count(rel) == 0);
18            Constant * const value = isa<ScalarConstant>(rel) ? cast<ScalarConstant>(rel)->value() : nullptr;
19            const auto bufferVertex = add_vertex(value, G);
20            add_edge(producerVertex, bufferVertex, i, G);
21            M.emplace(rel, bufferVertex);
22        }
23    }
24
25    ScalarDependencyGraph::vertex_descriptor makeIfConstant(const Relationship * const rel, ScalarDependencyGraph & G, ScalarDependencyMap & M) {
26        const auto f = M.find(rel);
27        if (LLVM_LIKELY(f != M.end())) {
28            return f->second;
29        } else if (LLVM_LIKELY(isa<ScalarConstant>(rel))) {
30            const auto bufferVertex = add_vertex(cast<ScalarConstant>(rel)->value(), G);
31            M.emplace(rel, bufferVertex);
32            return bufferVertex;
33        } else {
34            report_fatal_error("unknown scalar value");
35        }
36    }
37
38    template <typename Array>
39    void enumerateScalarConsumerBindings(const unsigned consumerVertex, const Array & array, ScalarDependencyGraph & G, ScalarDependencyMap & M) {
40        const auto n = array.size();
41        for (unsigned i = 0; i < n; ++i) {
42            const auto bufferVertex = makeIfConstant(getRelationship(array[i]), G, M);
43            assert (bufferVertex < num_vertices(G));
44            add_edge(bufferVertex, consumerVertex, i, G);
45        }
46    }
47
48}
49
50/** ------------------------------------------------------------------------------------------------------------- *
51 * @brief makeScalarDependencyGraph
52 ** ------------------------------------------------------------------------------------------------------------- */
53ScalarDependencyGraph PipelineCompiler::makeScalarDependencyGraph() const {
54
55    const auto numOfKernels = mPipeline.size();
56    const auto & callBindings = mPipelineKernel->getCallBindings();
57    const auto numOfCallBindings = callBindings.size();
58    const auto initialSize = numOfKernels + numOfCallBindings + 1;
59
60    ScalarDependencyGraph G(initialSize);
61    ScalarDependencyMap M;
62
63    enumerateScalarProducerBindings(numOfKernels, mPipelineKernel->getInputScalarBindings(), G, M);
64    // verify each scalar input of the kernel is an input to the pipeline
65    for (unsigned i = 0; i < numOfKernels; ++i) {
66        enumerateScalarConsumerBindings(i, mPipeline[i]->getInputScalarBindings(), G, M);
67    }
68    // enumerate the output scalars
69    for (unsigned i = 0; i < numOfKernels; ++i) {
70        enumerateScalarProducerBindings(i, mPipeline[i]->getOutputScalarBindings(), G, M);
71    }
72    // enumerate the call bindings
73    for (unsigned k = 0; k < numOfCallBindings; ++k) {
74        const CallBinding & call = callBindings[k];
75        enumerateScalarConsumerBindings(numOfKernels + 1 + k, call.Args, G, M);
76    }
77    // enumerate the pipeline outputs
78    enumerateScalarConsumerBindings(numOfKernels, mPipelineKernel->getOutputScalarBindings(), G, M);
79    return G;
80}
81
82
83
84/** ------------------------------------------------------------------------------------------------------------- *
85 * @brief makePortDependencyGraph
86 ** ------------------------------------------------------------------------------------------------------------- */
87PortDependencyGraph PipelineCompiler::makePortDependencyGraph() const {
88
89    const auto n = mKernel->getNumOfStreamInputs();
90    const auto m = mKernel->getNumOfStreamOutputs();
91    const auto l = n + m;
92
93    PortDependencyGraph G(l);
94
95    // enumerate the input relations
96    for (unsigned i = 0; i < n; ++i) {
97        const Binding & input = mKernel->getInputStreamSetBinding(i);
98        const ProcessingRate & rate = input.getRate();
99        if (rate.hasReference()) {
100            Port port; unsigned j;
101            std::tie(port, j) = mKernel->getStreamPort(rate.getReference());
102            assert ("input stream cannot refer to an output stream" && port == Port::Input);
103            add_edge(i, j, rate.getKind(), G);
104        }
105    }
106    // and then enumerate the output relations
107    for (unsigned i = 0; i < m; ++i) {
108        const Binding & output = mKernel->getOutputStreamSetBinding(i);
109        const ProcessingRate & rate = output.getRate();
110        if (rate.hasReference()) {
111            Port port; unsigned j;
112            std::tie(port, j) = mKernel->getStreamPort(rate.getReference());
113            add_edge((i + n), j + ((port == Port::Output) ? n : 0), rate.getKind(), G);
114        }
115    }
116    return G;
117}
118
119
120namespace {
121
122    using TerminationMap = RelationshipMap<TerminationGraph::vertex_descriptor>;
123
124    void enumerateTerminationProducerBindings(const unsigned producerVertex, const Bindings & bindings, TerminationGraph & G, TerminationMap & M) {
125        const auto n = bindings.size();
126        for (unsigned i = 0; i < n; ++i) {
127            const Relationship * const rel = getRelationship(bindings[i]);
128            if (LLVM_UNLIKELY(isa<ScalarConstant>(rel))) continue;
129            assert (M.count(rel) == 0);
130            const auto bufferVertex = add_vertex(G);
131            add_edge(producerVertex, bufferVertex, G); // producer -> buffer ordering
132            M.emplace(rel, bufferVertex);
133        }
134    }
135
136    template <typename Array>
137    void enumerateTerminationConsumerBindings(const unsigned consumerVertex, const Array & array, TerminationGraph & G, TerminationMap & M) {
138        const auto n = array.size();
139        for (unsigned i = 0; i < n; ++i) {
140            const Relationship * const rel = getRelationship(array[i]);
141            if (LLVM_UNLIKELY(isa<ScalarConstant>(rel))) continue;
142            const auto f = M.find(rel);
143            const auto bufferVertex = f->second;
144            add_edge(bufferVertex, consumerVertex, G); // buffer -> consumer ordering
145        }
146    }
147
148    void printTerminationGraph(const TerminationGraph & G, const std::vector<Kernel *> & pipeline, const unsigned index) {
149
150        auto & out = errs();
151
152        const auto numOfKernels = pipeline.size();
153
154        out << "digraph G" << index << " {\n";
155        for (auto u : make_iterator_range(vertices(G))) {
156            out << "v" << u << " [label=\"" << u << ": ";
157            if (u < numOfKernels) {
158                out << pipeline[u]->getName();
159            } else if (u == numOfKernels) {
160                out << "Pipeline";
161            } else {
162                out << "B" << (u - numOfKernels);
163            }
164            out << "\"];\n";
165        }
166
167        for (auto e : make_iterator_range(edges(G))) {
168            const auto s = source(e, G);
169            const auto t = target(e, G);
170            out << "v" << s << " -> v" << t;
171           // out << " label=\"" << G[e] << "\"";
172            out << ";\n";
173        }
174
175        out << "}\n\n";
176        out.flush();
177
178    }
179
180
181}
182
183/** ------------------------------------------------------------------------------------------------------------- *
184 * @brief makeTerminationGraph
185 *
186 * The termination graph is a transitive reduction of I/O dependency graph. It models which kernels to be checked
187 * to determine whether it is safe to terminate once it has finished processing its current input.
188 ** ------------------------------------------------------------------------------------------------------------- */
189TerminationGraph PipelineCompiler::makeTerminationGraph() const {
190    using VertexVector = std::vector<TerminationGraph::vertex_descriptor>;
191
192    const auto numOfKernels = mPipeline.size();
193    TerminationGraph G(numOfKernels + 1);
194    TerminationMap M;
195
196    // make an edge from the pipeline input to a buffer vertex
197    enumerateTerminationProducerBindings(numOfKernels, mPipelineKernel->getInputScalarBindings(), G, M);
198    enumerateTerminationProducerBindings(numOfKernels, mPipelineKernel->getInputStreamSetBindings(), G, M);
199    G[numOfKernels] = nullptr;
200
201    // make an edge from each producing kernel to a buffer vertex
202    for (unsigned i = 0; i < numOfKernels; ++i) {
203        const auto & producer = mPipeline[i];
204        enumerateTerminationProducerBindings(i, producer->getOutputStreamSetBindings(), G, M);
205        enumerateTerminationProducerBindings(i, producer->getOutputScalarBindings(), G, M);
206        G[i] = nullptr;
207    }
208
209    // make an edge from each buffer to its consuming kernel(s)
210    for (unsigned i = 0; i < numOfKernels; ++i) {
211        const auto & consumer = mPipeline[i];
212        enumerateTerminationConsumerBindings(i, consumer->getInputScalarBindings(), G, M);
213        enumerateTerminationConsumerBindings(i, consumer->getInputStreamSetBindings(), G, M);
214        if (LLVM_UNLIKELY(consumer->hasAttribute(AttrId::SideEffecting))) {
215            add_edge(i, numOfKernels, G);
216        }
217    }
218
219    // make an edge from a buffer vertex to each pipeline output
220    for (const CallBinding & call : mPipelineKernel->getCallBindings()) {
221        enumerateTerminationConsumerBindings(numOfKernels, call.Args, G, M);
222    }
223
224    clear_out_edges(numOfKernels, G);
225    enumerateTerminationConsumerBindings(numOfKernels, mPipelineKernel->getOutputStreamSetBindings(), G, M);
226    enumerateTerminationConsumerBindings(numOfKernels, mPipelineKernel->getOutputScalarBindings(), G, M);
227
228    VertexVector ordering;
229    ordering.reserve(num_vertices(G));
230    topological_sort(G, std::back_inserter(ordering));
231
232    // generate a transitive closure
233    for (unsigned u : ordering) {
234        for (auto e : make_iterator_range(in_edges(u, G))) {
235            const auto s = source(e, G);
236            for (auto f : make_iterator_range(out_edges(u, G))) {
237                add_edge(s, target(f, G), G);
238            }
239        }
240    }
241
242    // delete all buffer edges
243    const auto firstBuffer = numOfKernels + 1;
244    const auto lastBuffer = num_vertices(G);
245    for (auto i = firstBuffer; i < lastBuffer; ++i) {
246        clear_vertex(i, G);
247    }
248
249    // then take the transitive reduction
250    VertexVector sources;
251    for (unsigned u = firstBuffer; u--; ) {
252        for (auto e : make_iterator_range(in_edges(u, G))) {
253            sources.push_back(source(e, G));
254        }
255        std::sort(sources.begin(), sources.end());
256        for (auto e : make_iterator_range(out_edges(u, G))) {
257            remove_in_edge_if(target(e, G), [&G, &sources](const TerminationGraph::edge_descriptor f) {
258                return std::binary_search(sources.begin(), sources.end(), source(f, G));
259            }, G);
260        }
261        sources.clear();
262    }
263
264    return G;
265}
266
267} // end of namespace
Note: See TracBrowser for help on using the repository browser.