source: icGREP/icgrep-devel/icgrep/kernels/pipeline/pipeline_builder.cpp @ 6237

Last change on this file since 6237 was 6237, checked in by nmedfort, 4 months ago

Re-enabled segment pipeline parallelism; moved logical segment number into pipeline kernel.

File size: 14.7 KB
Line 
1#include <kernels/pipeline_builder.h>
2#include <kernels/kernel_builder.h>
3#include <boost/container/flat_map.hpp>
4#include <boost/function_output_iterator.hpp>
5#include <boost/graph/adjacency_list.hpp>
6#include <boost/graph/topological_sort.hpp>
7#include <llvm/Support/raw_ostream.h>
8#include <llvm/IR/Module.h>
9#include <llvm/IR/Constants.h>
10#include <queue>
11
12
13#warning if two kernels have an identical signature and take the same inputs, they ought to produce the same outputs unless they are nondeterministic.
14
15#warning the pipeline ordering should be canonicalized to ensure that when multiple kernels could be scheduled the same one will always be chosen.
16
17
18using namespace llvm;
19using namespace boost;
20using namespace boost::container;
21
22namespace kernel {
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief initializeKernel
26 ** ------------------------------------------------------------------------------------------------------------- */
27Kernel * PipelineBuilder::initializeKernel(Kernel * const kernel) {
28    kernel->initializeBindings(mDriver);
29    mDriver.addKernel(kernel);
30    mKernels.emplace_back(kernel);
31    return kernel;
32}
33
34#warning TODO: make a templated method to automatically validate and cast the main function to the correct type?
35
36/** ------------------------------------------------------------------------------------------------------------- *
37 * @brief finalizeObject
38 ** ------------------------------------------------------------------------------------------------------------- */
39void * PipelineBuilder::compile() {
40    PipelineKernel * const pk = makePipelineKernel();
41    pk->initializeBindings(mDriver);
42    mDriver.addKernel(pk);
43    mDriver.generateUncachedKernels();
44    Function * const main = addOrDeclareMainFunction(pk);
45    return mDriver.finalizeObject(main);
46}
47
48using Kernels = PipelineBuilder::Kernels;
49
50enum class VertexType { Kernel, StreamSet, Scalar };
51
52using AttrId = Attribute::KindId;
53
54struct PipelineVertexData {
55    bool active;
56    VertexType type;
57    PipelineVertexData() : active(false), type(VertexType::Kernel) { }
58};
59
60using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PipelineVertexData, unsigned>;
61
62using Vertex = Graph::vertex_descriptor;
63using Map = flat_map<const Relationship *, Vertex>;
64using Queue = std::queue<Vertex>;
65
66inline const Relationship * getRelationship(not_null<const Relationship *> r) {
67    return r.get();
68}
69
70inline const Relationship * getRelationship(const Binding & b) {
71    return getRelationship(b.getRelationship());
72}
73
74template <typename Graph>
75inline typename graph_traits<Graph>::edge_descriptor out_edge(const typename graph_traits<Graph>::vertex_descriptor u, const Graph & G) {
76    assert (out_degree(u, G) == 1);
77    return *out_edges(u, G).first;
78}
79
80void enumerateProducerBindings(const VertexType type, const Vertex producerVertex, const Bindings & bindings, Graph & G, Map & M, const Kernels & K) {
81    const auto n = bindings.size();
82    for (unsigned i = 0; i < n; ++i) {
83        const Relationship * const rel = getRelationship(bindings[i]);
84        if (LLVM_UNLIKELY(isa<ScalarConstant>(rel))) continue;
85        const auto f = M.find(rel);
86        if (LLVM_UNLIKELY(f != M.end())) {
87            std::string tmp;
88            raw_string_ostream out(tmp);
89            const auto existingProducer = target(out_edge(f->second, G), G);
90            out << "Both " << K[existingProducer]->getName() <<
91                   " and " << K[producerVertex]->getName() <<
92                   " produce the same stream.";
93            throw std::runtime_error(out.str());
94        }
95        const auto bufferVertex = add_vertex(G);
96        M.emplace(rel, bufferVertex);
97        G[bufferVertex].type = type;
98        add_edge(bufferVertex, producerVertex, i, G); // buffer -> producer ordering
99    }
100}
101
102template <typename Array>
103void enumerateConsumerBindings(const VertexType type, const Vertex consumerVertex, const Array & array, Graph & G, Map & M) {
104    const auto n = array.size();
105    for (unsigned i = 0; i < n; ++i) {
106        const Relationship * const rel = getRelationship(array[i]);
107        if (LLVM_UNLIKELY(isa<ScalarConstant>(rel))) continue;
108        const auto f = M.find(rel); assert (f != M.end());
109        const auto bufferVertex = f->second;
110        assert (bufferVertex < num_vertices(G));
111        assert (G[bufferVertex].type == type);
112        add_edge(consumerVertex, bufferVertex, i, G); // consumer -> buffer ordering
113    }
114}
115
116void markActiveKernels(const Vertex initial, Queue & Q, Graph & G) {
117    assert (Q.empty());
118    if (G[initial].active) return;
119    G[initial].active = true;
120    auto u = initial;
121    for (;;) {
122        for (const auto e : make_iterator_range(out_edges(u, G))) {
123            const auto v = target(e, G);
124            if (G[v].active) {
125                continue;
126            }
127            G[v].active = true;
128            Q.push(v);
129        }
130        if (Q.empty()) {
131            break;
132        }
133        u = Q.front();
134        Q.pop();
135    }
136}
137
138inline void markActiveKernels(const unsigned numOfKernels, const unsigned numOfCalls, const Vertex pipelineVertex, const PipelineKernel::Kernels & K, Graph & G) {
139    Queue Q;
140    for (unsigned i = 0; i < numOfKernels; ++i) {
141        if (K[i]->hasAttribute(AttrId::SideEffecting)) {
142            markActiveKernels(vertex(i, G), Q, G);
143        }
144    }
145    for (unsigned i = 0; i < numOfCalls; ++i) {
146        markActiveKernels(vertex(numOfKernels + i, G), Q, G);
147    }
148    markActiveKernels(pipelineVertex, Q, G);
149}
150
151inline void clearUnmarkedVertices(const Vertex pipelineVertex, Graph & G) {
152    G[pipelineVertex].active = false;
153    for (auto i : make_iterator_range(vertices(G))) {
154        if (LLVM_UNLIKELY(!G[i].active)) {
155            clear_vertex(i, G);
156        }
157    }
158}
159
160inline std::vector<Vertex> getTopologicalOrdering(const unsigned limit, Graph & G) {
161    // now take a topological ordering of the graph
162    std::vector<Vertex> ordering;
163    ordering.reserve(limit);
164    auto inserter = make_function_output_iterator([&](const Vertex i) {
165        if (i < limit && G[i].active) {
166            ordering.push_back(i);
167        }
168    });
169    topological_sort(G, inserter);
170    assert (ordering.size() <= limit);
171    return ordering;
172}
173
174inline char getRelationshipType(const VertexType type) {
175    switch (type) {
176        case VertexType::StreamSet:
177            return 'S';
178        case VertexType::Scalar:
179            return 'V';
180        default: llvm_unreachable("unknown relationship type");
181    }
182}
183
184/** ------------------------------------------------------------------------------------------------------------- *
185 * @brief finalizeObject
186 ** ------------------------------------------------------------------------------------------------------------- */
187PipelineKernel * PipelineBuilder::makePipelineKernel() {
188
189    const auto numOfKernels = mKernels.size();
190    const auto numOfCalls = mCallBindings.size();
191    const auto pipelineVertex = numOfKernels + numOfCalls;
192
193    Graph G(pipelineVertex + 1);
194    Map M;
195
196    enumerateProducerBindings(VertexType::Scalar, pipelineVertex, mInputScalars, G, M, mKernels);
197    enumerateProducerBindings(VertexType::StreamSet, pipelineVertex, mInputStreamSets, G, M, mKernels);
198    for (unsigned i = 0; i < numOfKernels; ++i) {
199        enumerateProducerBindings(VertexType::Scalar, i, mKernels[i]->getOutputScalarBindings(), G, M, mKernels);
200        enumerateProducerBindings(VertexType::StreamSet, i, mKernels[i]->getOutputStreamSetBindings(), G, M, mKernels);
201    }
202    for (unsigned i = 0; i < numOfKernels; ++i) {
203        enumerateConsumerBindings(VertexType::Scalar, i, mKernels[i]->getInputScalarBindings(), G, M);
204        enumerateConsumerBindings(VertexType::StreamSet, i, mKernels[i]->getInputStreamSetBindings(), G, M);
205    }
206    for (unsigned i = 0; i < numOfCalls; ++i) {
207        enumerateConsumerBindings(VertexType::Scalar, numOfKernels + i, mCallBindings[i].Args, G, M);
208    }
209    enumerateConsumerBindings(VertexType::Scalar, pipelineVertex, mOutputScalars, G, M);
210    enumerateConsumerBindings(VertexType::StreamSet, pipelineVertex, mOutputStreamSets, G, M);
211
212    clear_in_edges(pipelineVertex, G);
213    markActiveKernels(numOfKernels, numOfCalls, pipelineVertex, mKernels, G);
214    clearUnmarkedVertices(pipelineVertex, G);
215
216    const auto ordering = getTopologicalOrdering(numOfKernels + numOfCalls, G);
217
218    std::string signature;
219    raw_string_ostream out(signature);
220
221    out << 'P' << mNumOfThreads;
222    for (auto i : ordering) {
223        if (LLVM_LIKELY(i < numOfKernels)) {
224            const auto & k = mKernels[i];
225            out << "_K";
226            if (k->hasFamilyName()) {
227                out << k->getFamilyName();
228            } else {
229                out << k->getName();
230            }
231        } else {
232            const auto j = i - numOfKernels;
233            assert (j < numOfCalls);
234            out << "_C" << mCallBindings[j].Name;
235        }
236    }
237
238    #ifndef NDEBUG
239    std::vector<unsigned> index(numOfKernels + numOfCalls, std::numeric_limits<unsigned>::max());
240    #else
241    std::vector<unsigned> index(numOfKernels + numOfCalls);
242    #endif
243
244    unsigned j = 0;
245    for (unsigned i : ordering) {
246        index[i] = j++;
247    }
248
249    const auto firstRelationship = pipelineVertex + 1;
250    const auto lastRelationship = num_vertices(G);
251
252    for (auto i = firstRelationship; i != lastRelationship; ++i) {
253        if (LLVM_UNLIKELY(out_degree(i, G) == 0)) continue;
254        const PipelineVertexData & vd = G[i];
255        assert (vd.active);
256        out << '@' << getRelationshipType(vd.type);
257        const auto e = out_edge(i, G);
258        const auto j = target(e, G);
259        assert (j < numOfKernels);
260        const auto s = index[j];
261        assert (s != std::numeric_limits<unsigned>::max());
262        out << s << '.' << G[e];
263        for (const auto e : make_iterator_range(in_edges(i, G))) {
264            const auto j = source(e, G);
265            assert (j < pipelineVertex);
266            const auto t = index[j];
267            assert (t != std::numeric_limits<unsigned>::max());
268            out << '_' << t << '.' << G[e];
269        }
270    }
271    out.flush();
272
273    Kernels pipeline;
274    pipeline.reserve(ordering.size());
275
276    const std::unique_ptr<kernel::KernelBuilder> & b = mDriver.getBuilder();
277    Type * const addrPtrTy = b->getVoidPtrTy(); // is voidptrty sufficient?
278    for (auto i : ordering) {
279        if (LLVM_LIKELY(i < numOfKernels)) {
280            Kernel * const k = mKernels[i];
281            if (k->hasFamilyName()) {
282                const auto kn = PipelineKernel::makeKernelName(k, index[i]);
283                addInputScalar(addrPtrTy, kn);
284                addInputScalar(addrPtrTy, kn + INITIALIZE_FUNCTION_POINTER_SUFFIX);
285                addInputScalar(addrPtrTy, kn + DO_SEGMENT_FUNCTION_POINTER_SUFFIX);
286                addInputScalar(addrPtrTy, kn + FINALIZE_FUNCTION_POINTER_SUFFIX);
287            }
288            pipeline.emplace_back(k);
289        }
290    }
291
292    PipelineKernel * const pk =
293        new PipelineKernel(std::move(signature), mNumOfThreads,
294                           std::move(pipeline), std::move(mCallBindings),
295                           std::move(mInputStreamSets), std::move(mOutputStreamSets),
296                           std::move(mInputScalars), std::move(mOutputScalars));
297
298    return pk;
299}
300
301inline void PipelineBuilder::addInputScalar(llvm::Type * type, std::string name) {
302    mInputScalars.emplace_back(name, CreateConstant(Constant::getNullValue(type)), FixedRate(1), Family());
303}
304
305/** ------------------------------------------------------------------------------------------------------------- *
306 * @brief makeMainFunction
307 ** ------------------------------------------------------------------------------------------------------------- */
308Function * PipelineBuilder::addOrDeclareMainFunction(PipelineKernel * const k) {
309    auto & b = mDriver.getBuilder();
310    b->setModule(mDriver.getMainModule());
311    k->addKernelDeclarations(b);
312    const auto method = k->hasStaticMain() ? PipelineKernel::DeclareExternal : PipelineKernel::AddInternal;
313    return k->addOrDeclareMainFunction(b, method);
314}
315
316
317Scalar * PipelineBuilder::getInputScalar(const std::string & name) {
318    for (Binding & input : mInputScalars) {
319        if (input.getName() == name) {
320            if (input.getRelationship() == nullptr) {
321                input.setRelationship(mDriver.CreateScalar(input.getType()));
322            }
323            return cast<Scalar>(input.getRelationship());
324        }
325    }
326    return nullptr;
327}
328
329void PipelineBuilder::setInputScalar(const std::string & name, Scalar * value) {
330    for (Binding & input : mInputScalars) {
331        if (input.getName() == name) {
332            input.setRelationship(value);
333            break;
334        }
335    }
336}
337
338Scalar * PipelineBuilder::getOutputScalar(const std::string & name) {
339    for (Binding & output : mOutputScalars) {
340        if (output.getName() == name) {
341            if (output.getRelationship() == nullptr) {
342                output.setRelationship(mDriver.CreateScalar(output.getType()));
343            }
344            return cast<Scalar>(output.getRelationship());
345        }
346    }
347    return nullptr;
348}
349
350void PipelineBuilder::setOutputScalar(const std::string & name, Scalar * value) {
351    for (Binding & output : mOutputScalars) {
352        if (output.getName() == name) {
353            output.setRelationship(value);
354            break;
355        }
356    }
357}
358
359
360PipelineBuilder::PipelineBuilder(BaseDriver & driver,
361                                 Bindings && stream_inputs, Bindings && stream_outputs,
362                                 Bindings && scalar_inputs, Bindings && scalar_outputs,
363                                 const unsigned numOfThreads)
364: mDriver(driver)
365, mNumOfThreads(numOfThreads)
366, mInputStreamSets(stream_inputs)
367, mOutputStreamSets(stream_outputs)
368, mInputScalars(scalar_inputs)
369, mOutputScalars(scalar_outputs) {
370
371    for (unsigned i = 0; i < mInputScalars.size(); i++) {
372        Binding & input = mInputScalars[i];
373        if (input.getRelationship() == nullptr) {
374            input.setRelationship(driver.CreateScalar(input.getType()));
375        }
376    }
377    for (unsigned i = 0; i < mInputStreamSets.size(); i++) {
378        Binding & input = mInputStreamSets[i];
379        if (LLVM_UNLIKELY(input.getRelationship() == nullptr)) {
380            report_fatal_error(input.getName() + " must be set upon construction");
381        }
382    }
383    for (unsigned i = 0; i < mOutputStreamSets.size(); i++) {
384        Binding & output = mOutputStreamSets[i];
385        if (LLVM_UNLIKELY(output.getRelationship() == nullptr)) {
386            report_fatal_error(output.getName() + " must be set upon construction");
387        }
388    }
389    for (unsigned i = 0; i < mOutputScalars.size(); i++) {
390        Binding & output = mOutputScalars[i];
391        if (output.getRelationship() == nullptr) {
392            output.setRelationship(driver.CreateScalar(output.getType()));
393        }
394    }
395
396}
397
398
399}
Note: See TracBrowser for help on using the repository browser.