source: icGREP/icgrep-devel/icgrep/toolchain/pipeline.cpp @ 5996

Last change on this file since 5996 was 5996, checked in by cameron, 13 months ago

moving a temporary object prevents copy elision

File size: 49.4 KB
Line 
1/*
2 *  Copyright (c) 2016 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5
6#include "pipeline.h"
7#include <toolchain/toolchain.h>
8#include <kernels/kernel.h>
9#include <kernels/streamset.h>
10#include <llvm/IR/Module.h>
11#include <boost/container/flat_set.hpp>
12#include <boost/container/flat_map.hpp>
13#include <boost/graph/adjacency_list.hpp>
14#include <boost/range/adaptor/reversed.hpp>
15#include <kernels/kernel_builder.h>
16#include <llvm/Support/raw_ostream.h>
17
18using namespace kernel;
19using namespace parabix;
20using namespace llvm;
21using namespace boost;
22using namespace boost::container;
23
24#define DISABLE_COPY_TO_OVERFLOW
25
26using Port = Kernel::Port;
27
28Function * makeThreadFunction(const std::unique_ptr<kernel::KernelBuilder> & b, const std::string & name) {
29    Function * const f = Function::Create(FunctionType::get(b->getVoidTy(), {b->getVoidPtrTy()}, false), Function::InternalLinkage, name, b->getModule());
30    f->setCallingConv(CallingConv::C);
31    f->arg_begin()->setName("state");
32    return f;
33}
34
35class PipelineGenerator {
36public:
37
38    template <typename Value>
39    using StreamSetBufferMap = flat_map<const StreamSetBuffer *, Value>;
40
41    using RateValue = ProcessingRate::RateValue;
42
43    PipelineGenerator(const std::vector<Kernel *> & kernels)
44    : kernels(kernels)
45    , terminated(nullptr)
46    , noMore(nullptr)
47    , deadLockCounter(nullptr)
48    , anyProgress(nullptr)
49    , madeProgress(nullptr) {
50
51    }
52
53    struct Channel {
54        Channel() = default;
55        Channel(const RateValue & ratio, const StreamSetBuffer * const buffer = nullptr, const unsigned operand = 0)
56        : ratio(ratio), buffer(buffer), operand(operand) { }
57
58        RateValue               ratio;
59        const StreamSetBuffer * buffer;
60        unsigned                operand;
61    };
62
63    using ChannelGraph = adjacency_list<vecS, vecS, bidirectionalS, const Kernel *, Channel>;
64
65    using DependencyGraph = adjacency_list<hash_setS, vecS, bidirectionalS, Value *>;
66
67    using KernelMap = flat_map<const Kernel *, unsigned>;
68
69    void initialize(const std::unique_ptr<KernelBuilder> & b, BasicBlock * const entryBlock);
70
71    void execute(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
72
73    Value * finalize(const std::unique_ptr<KernelBuilder> & b);
74
75protected:
76
77    ChannelGraph makeInputGraph() const;
78
79    ChannelGraph makeOutputGraph() const;
80
81    DependencyGraph makeDependencyGraph() const;
82
83    template<class VertexList>
84    ChannelGraph pruneGraph(ChannelGraph && G, VertexList && V) const;
85
86    void checkIfAllInputKernelsAreTerminated(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
87
88    void checkAvailableInputData(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
89
90    void checkAvailableOutputSpace(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
91
92    Value * getStrideLength(const std::unique_ptr<KernelBuilder> & b, const Kernel * const kernel, const Binding & binding);
93
94    Value * callKernel(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
95
96    void applyOutputBufferExpansions(const std::unique_ptr<KernelBuilder> & b, const unsigned index);
97
98    Value * getFullyProcessedItemCount(const std::unique_ptr<KernelBuilder> & b, const Binding & binding, Value * const final) const;
99
100    void printGraph(const ChannelGraph & G) const;
101
102    void printGraph(const DependencyGraph & G) const;
103
104private:
105
106    const std::vector<Kernel *> &       kernels;
107    PHINode *                           terminated;
108
109    Value *                             noMore;
110
111    DependencyGraph                     dependencyGraph;
112    ChannelGraph                        inputGraph;
113    ChannelGraph                        outputGraph;
114
115    BasicBlock *                        kernelFinished;
116
117    PHINode *                           deadLockCounter;
118    Value *                             anyProgress;
119    PHINode *                           madeProgress;
120
121    StreamSetBufferMap<Value *>         producedItemCount;
122    StreamSetBufferMap<Value *>         consumedItemCount;
123    StreamSetBufferMap<const Kernel *>  lastConsumer;
124    flat_set<const StreamSetBuffer *>   isConsumedAtNonFixedRate;
125};
126
127/** ------------------------------------------------------------------------------------------------------------- *
128 * @brief generateSegmentParallelPipeline
129 *
130 * Given a computation expressed as a logical pipeline of K kernels k0, k_1, ...k_(K-1)
131 * operating over an input stream set S, a segment-parallel implementation divides the input
132 * into segments and coordinates a set of T <= K threads to each process one segment at a time.
133 * Let S_0, S_1, ... S_N be the segments of S.   Segments are assigned to threads in a round-robin
134 * fashion such that processing of segment S_i by the full pipeline is carried out by thread i mod T.
135 ** ------------------------------------------------------------------------------------------------------------- */
136void generateSegmentParallelPipeline(const std::unique_ptr<KernelBuilder> & b, const std::vector<Kernel *> & kernels) {
137
138    const unsigned n = kernels.size();
139    Module * const m = b->getModule();
140    IntegerType * const sizeTy = b->getSizeTy();
141    PointerType * const voidPtrTy = b->getVoidPtrTy();
142    Constant * nullVoidPtrVal = ConstantPointerNull::getNullValue(voidPtrTy);
143    std::vector<Type *> structTypes;
144    codegen::BufferSegments = std::max(codegen::BufferSegments, codegen::ThreadNum);
145
146    Value * instance[n];
147    for (unsigned i = 0; i < n; ++i) {
148        instance[i] = kernels[i]->getInstance();
149        structTypes.push_back(instance[i]->getType());
150    }
151    StructType * const sharedStructType = StructType::get(m->getContext(), structTypes);
152    StructType * const threadStructType = StructType::get(m->getContext(), {sharedStructType->getPointerTo(), sizeTy});
153
154    const auto ip = b->saveIP();
155
156    Function * const threadFunc = makeThreadFunction(b, "segment");
157    auto args = threadFunc->arg_begin();
158
159    // -------------------------------------------------------------------------------------------------------------------------
160    // MAKE SEGMENT PARALLEL PIPELINE THREAD
161    // -------------------------------------------------------------------------------------------------------------------------
162
163     // Create the basic blocks for the thread function.
164    BasicBlock * entryBlock = BasicBlock::Create(b->getContext(), "entry", threadFunc);
165    b->SetInsertPoint(entryBlock);
166
167    Value * const threadStruct = b->CreateBitCast(&*(args), threadStructType->getPointerTo());
168
169    Value * const sharedStatePtr = b->CreateLoad(b->CreateGEP(threadStruct, {b->getInt32(0), b->getInt32(0)}));
170    for (unsigned k = 0; k < n; ++k) {
171        Value * ptr = b->CreateLoad(b->CreateGEP(sharedStatePtr, {b->getInt32(0), b->getInt32(k)}));
172        kernels[k]->setInstance(ptr);
173    }
174    Value * const segOffset = b->CreateLoad(b->CreateGEP(threadStruct, {b->getInt32(0), b->getInt32(1)}));
175
176    PipelineGenerator G(kernels);
177
178    BasicBlock * const segmentLoop = b->CreateBasicBlock("segmentLoop");
179    b->CreateBr(segmentLoop);
180
181    b->SetInsertPoint(segmentLoop);   
182    PHINode * const segNo = b->CreatePHI(b->getSizeTy(), 2, "segNo");
183    segNo->addIncoming(segOffset, entryBlock);
184    G.initialize(b, entryBlock);
185
186    Value * cycleCountStart = nullptr;
187    Value * cycleCountEnd = nullptr;
188    if (DebugOptionIsSet(codegen::EnableCycleCounter)) {
189        cycleCountStart = b->CreateReadCycleCounter();
190    }
191
192    const bool serialize = codegen::DebugOptionIsSet(codegen::SerializeThreads);
193
194    for (unsigned k = 0; k < n; ++k) {
195
196        const Kernel * const kernel = kernels[k];
197
198        BasicBlock * const kernelWait = b->CreateBasicBlock(kernel->getName() + "Wait");
199        b->CreateBr(kernelWait);
200
201        b->SetInsertPoint(kernelWait);
202        b->setKernel(kernels[serialize ? (n - 1) : k]);
203        Value * const processedSegmentCount = b->acquireLogicalSegmentNo();
204        assert (processedSegmentCount->getType() == segNo->getType());
205        Value * const ready = b->CreateICmpEQ(segNo, processedSegmentCount);
206
207        BasicBlock * const kernelCheck = b->CreateBasicBlock(kernel->getName() + "Check");
208        b->CreateCondBr(ready, kernelCheck, kernelWait);
209
210        b->SetInsertPoint(kernelCheck);
211
212        G.execute(b, k);
213
214        b->releaseLogicalSegmentNo(b->CreateAdd(segNo, b->getSize(1)));
215
216        if (DebugOptionIsSet(codegen::EnableCycleCounter)) {
217            cycleCountEnd = b->CreateReadCycleCounter();
218            Value * counterPtr = b->getCycleCountPtr();
219            b->CreateStore(b->CreateAdd(b->CreateLoad(counterPtr), b->CreateSub(cycleCountEnd, cycleCountStart)), counterPtr);
220            cycleCountStart = cycleCountEnd;
221        }
222
223    }
224
225    segNo->addIncoming(b->CreateAdd(segNo, b->getSize(codegen::ThreadNum)), b->GetInsertBlock());
226    Value * const finished = G.finalize(b);
227    BasicBlock * const segmentExit = b->CreateBasicBlock("segmentExit");
228    b->CreateUnlikelyCondBr(finished, segmentExit, segmentLoop);
229
230    b->SetInsertPoint(segmentExit);
231    // only call pthread_exit() within spawned threads; otherwise it'll be equivalent to calling exit() within the process
232    BasicBlock * const exitThread = b->CreateBasicBlock("ExitThread");
233    BasicBlock * const exitFunction = b->CreateBasicBlock("ExitProcessFunction");   
234    b->CreateCondBr(b->CreateIsNull(segOffset), exitFunction, exitThread);
235    b->SetInsertPoint(exitThread);
236    b->CreatePThreadExitCall(nullVoidPtrVal);
237    b->CreateBr(exitFunction);   
238    b->SetInsertPoint(exitFunction);
239    b->CreateRetVoid();
240
241    // -------------------------------------------------------------------------------------------------------------------------
242    b->restoreIP(ip);
243
244    for (unsigned i = 0; i < n; ++i) {
245        kernels[i]->setInstance(instance[i]);
246    }
247
248    // -------------------------------------------------------------------------------------------------------------------------
249    // MAKE SEGMENT PARALLEL PIPELINE DRIVER
250    // -------------------------------------------------------------------------------------------------------------------------
251    const unsigned threads = codegen::ThreadNum - 1;
252    assert (codegen::ThreadNum > 0);
253    Type * const pthreadsTy = ArrayType::get(sizeTy, threads);
254    AllocaInst * const pthreads = b->CreateAlloca(pthreadsTy);
255    Value * threadIdPtr[threads];
256
257    for (unsigned i = 0; i < threads; ++i) {
258        threadIdPtr[i] = b->CreateGEP(pthreads, {b->getInt32(0), b->getInt32(i)});
259    }
260
261    for (unsigned i = 0; i < n; ++i) {
262        b->setKernel(kernels[i]);
263        b->releaseLogicalSegmentNo(b->getSize(0));
264    }
265
266    AllocaInst * const sharedStruct = b->CreateCacheAlignedAlloca(sharedStructType);
267    for (unsigned i = 0; i < n; ++i) {
268        Value * ptr = b->CreateGEP(sharedStruct, {b->getInt32(0), b->getInt32(i)});
269        b->CreateStore(kernels[i]->getInstance(), ptr);
270    }
271
272    // use the process thread to handle the initial segment function after spawning (n - 1) threads to handle the subsequent offsets
273    for (unsigned i = 0; i < threads; ++i) {
274        AllocaInst * const threadState = b->CreateAlloca(threadStructType);
275        b->CreateStore(sharedStruct, b->CreateGEP(threadState, {b->getInt32(0), b->getInt32(0)}));
276        b->CreateStore(b->getSize(i + 1), b->CreateGEP(threadState, {b->getInt32(0), b->getInt32(1)}));
277        b->CreatePThreadCreateCall(threadIdPtr[i], nullVoidPtrVal, threadFunc, threadState);
278    }
279
280    AllocaInst * const threadState = b->CreateAlloca(threadStructType);
281    b->CreateStore(sharedStruct, b->CreateGEP(threadState, {b->getInt32(0), b->getInt32(0)}));
282    b->CreateStore(b->getSize(0), b->CreateGEP(threadState, {b->getInt32(0), b->getInt32(1)}));
283    b->CreateCall(threadFunc, b->CreatePointerCast(threadState, voidPtrTy));
284
285    AllocaInst * const status = b->CreateAlloca(voidPtrTy);
286    for (unsigned i = 0; i < threads; ++i) {
287        Value * threadId = b->CreateLoad(threadIdPtr[i]);
288        b->CreatePThreadJoinCall(threadId, status);
289    }
290   
291    if (LLVM_UNLIKELY(DebugOptionIsSet(codegen::EnableCycleCounter))) {
292        for (const Kernel * kernel : kernels) {
293            b->setKernel(kernel);
294            const auto & inputs = kernel->getStreamInputs();
295            const auto & outputs = kernel->getStreamOutputs();
296            Value * items = nullptr;
297            if (inputs.empty()) {
298                items = b->getProducedItemCount(outputs[0].getName());
299            } else {
300                items = b->getProcessedItemCount(inputs[0].getName());
301            }
302            Value * fItems = b->CreateUIToFP(items, b->getDoubleTy());
303            Value * cycles = b->CreateLoad(b->getCycleCountPtr());
304            Value * fCycles = b->CreateUIToFP(cycles, b->getDoubleTy());
305            const auto formatString = kernel->getName() + ": %7.2e items processed; %7.2e CPU cycles,  %6.2f cycles per item.\n";
306            Value * stringPtr = b->CreatePointerCast(b->GetString(formatString), b->getInt8PtrTy());
307            b->CreateCall(b->GetDprintf(), {b->getInt32(2), stringPtr, fItems, fCycles, b->CreateFDiv(fCycles, fItems)});
308        }
309    }
310   
311}
312
313
314/** ------------------------------------------------------------------------------------------------------------- *
315 * @brief generatePipelineLoop
316 ** ------------------------------------------------------------------------------------------------------------- */
317void generatePipelineLoop(const std::unique_ptr<KernelBuilder> & b, const std::vector<Kernel *> & kernels) {
318
319    // Create the basic blocks for the loop.
320    BasicBlock * const entryBlock = b->GetInsertBlock();
321    BasicBlock * const pipelineLoop = b->CreateBasicBlock("pipelineLoop");
322
323    PipelineGenerator G(kernels);
324
325    b->CreateBr(pipelineLoop);
326
327    b->SetInsertPoint(pipelineLoop);   
328    PHINode * const segNo = b->CreatePHI(b->getSizeTy(), 2, "segNo");
329    segNo->addIncoming(b->getSize(0), entryBlock);
330    G.initialize(b, entryBlock);
331
332    Value * const nextSegNo = b->CreateAdd(segNo, b->getSize(1));
333
334    Value * cycleCountStart = nullptr;
335    Value * cycleCountEnd = nullptr;
336    if (LLVM_UNLIKELY(DebugOptionIsSet(codegen::EnableCycleCounter))) {
337        cycleCountStart = b->CreateReadCycleCounter();
338    }
339
340    for (unsigned i = 0; i < kernels.size(); ++i) {
341
342        G.execute(b, i);
343
344        b->releaseLogicalSegmentNo(nextSegNo);
345
346        if (LLVM_UNLIKELY(DebugOptionIsSet(codegen::EnableCycleCounter))) {
347            cycleCountEnd = b->CreateReadCycleCounter();
348            Value * counterPtr = b->getCycleCountPtr();
349            b->CreateStore(b->CreateAdd(b->CreateLoad(counterPtr), b->CreateSub(cycleCountEnd, cycleCountStart)), counterPtr);
350            cycleCountStart = cycleCountEnd;
351        }
352    }
353
354    segNo->addIncoming(nextSegNo, b->GetInsertBlock());
355    BasicBlock * const pipelineExit = b->CreateBasicBlock("pipelineExit");
356    Value * const finished = G.finalize(b);
357    b->CreateCondBr(finished, pipelineExit, pipelineLoop);
358
359    b->SetInsertPoint(pipelineExit);
360    if (LLVM_UNLIKELY(DebugOptionIsSet(codegen::EnableCycleCounter))) {
361        for (unsigned k = 0; k < kernels.size(); k++) {
362            auto & kernel = kernels[k];
363            b->setKernel(kernel);
364            const auto & inputs = kernel->getStreamInputs();
365            const auto & outputs = kernel->getStreamOutputs();
366            Value * items = nullptr;
367            if (inputs.empty()) {
368                items = b->getProducedItemCount(outputs[0].getName());
369            } else {
370                items = b->getProcessedItemCount(inputs[0].getName());
371            }
372            Value * fItems = b->CreateUIToFP(items, b->getDoubleTy());
373            Value * cycles = b->CreateLoad(b->getCycleCountPtr());
374            Value * fCycles = b->CreateUIToFP(cycles, b->getDoubleTy());
375            const auto formatString = kernel->getName() + ": %7.2e items processed; %7.2e CPU cycles,  %6.2f cycles per item.\n";
376            Value * stringPtr = b->CreatePointerCast(b->GetString(formatString), b->getInt8PtrTy());
377            b->CreateCall(b->GetDprintf(), {b->getInt32(2), stringPtr, fItems, fCycles, b->CreateFDiv(fCycles, fItems)});
378        }
379    }
380
381}
382
383/** ------------------------------------------------------------------------------------------------------------- *
384 * @brief initialize
385 ** ------------------------------------------------------------------------------------------------------------- */
386void PipelineGenerator::initialize(const std::unique_ptr<KernelBuilder> & b, BasicBlock * const entryBlock) {
387
388    dependencyGraph = makeDependencyGraph();
389    inputGraph = makeInputGraph();
390    outputGraph = makeOutputGraph();
391
392    for (Kernel * const kernel : kernels) {
393        const auto & inputs = kernel->getStreamInputs();
394        for (unsigned i = 0; i < inputs.size(); ++i) {
395            const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
396            if (kernel->requiresCopyBack(inputs[i]) && !buffer->isUnbounded()) {
397                if (LLVM_LIKELY(buffer->supportsCopyBack())) {
398                    isConsumedAtNonFixedRate.insert(buffer);
399                } else {
400    //                std::string tmp;
401    //                raw_string_ostream out(tmp);
402    //                out << kernel->getName() << " : " << name << " must have an overflow";
403    //                report_fatal_error(out.str());
404                }
405            }
406        }
407        // if this kernel consumes this buffer, update the last consumer
408        for (const StreamSetBuffer * const buffer : kernel->getStreamSetInputBuffers()) {
409            auto f = lastConsumer.find(buffer);
410            assert (f != lastConsumer.end());
411            f->second = kernel;
412        }
413        // incase some output is never consumed, make the kernel that produced it the initial "last consumer"
414        for (const StreamSetBuffer * const buffer : kernel->getStreamSetOutputBuffers()) {
415            assert (buffer->getProducer() == kernel);
416            assert (lastConsumer.count(buffer) == 0);
417            lastConsumer.emplace(buffer, kernel);
418        }
419    }
420
421    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
422        deadLockCounter = b->CreatePHI(b->getSizeTy(), 2, "deadLockCounter");
423        deadLockCounter->addIncoming(b->getSize(0), entryBlock);
424        anyProgress = b->getFalse();
425    }
426
427}
428
429/** ------------------------------------------------------------------------------------------------------------- *
430 * @brief makeTerminationGraph
431 *
432 * The input graph models whether a kernel could *consume* more data than may be produced by a preceeding kernel.
433 ** ------------------------------------------------------------------------------------------------------------- */
434PipelineGenerator::DependencyGraph PipelineGenerator::makeDependencyGraph() const {
435    const auto n = kernels.size();
436    DependencyGraph G(n);
437    KernelMap M;
438    // construct a kernel dependency graph
439    for (unsigned v = 0; v < n; ++v) {
440        const Kernel * const kernel = kernels[v];       
441        for (const StreamSetBuffer * buf : kernel->getStreamSetInputBuffers()) {
442            const auto f = M.find(buf->getProducer()); assert (f != M.end());
443            add_edge(f->second, v, G);
444        }
445        M.emplace(kernel, v);
446    }
447    // generate a transitive closure
448    for (unsigned u = 0; u < n; ++u) {
449        for (auto e : make_iterator_range(in_edges(u, G))) {
450            const auto s = source(e, G);
451            for (auto f : make_iterator_range(out_edges(u, G))) {
452                add_edge(s, target(f, G), G);
453            }
454        }
455    }
456    // then take the transitive reduction
457    std::vector<unsigned> sources;
458    for (unsigned u = n; u-- > 0; ) {
459        if (in_degree(u, G) > 0 && out_degree(u, G) > 0) {
460            for (auto e : make_iterator_range(in_edges(u, G))) {
461                sources.push_back(source(e, G));
462            }
463            std::sort(sources.begin(), sources.end());
464            for (auto e : make_iterator_range(out_edges(u, G))) {
465                remove_in_edge_if(target(e, G), [&G, &sources](const DependencyGraph::edge_descriptor f) {
466                    return std::binary_search(sources.begin(), sources.end(), source(f, G));
467                }, G);
468            }
469            sources.clear();
470        }
471    }
472    return G;
473}
474
475/** ------------------------------------------------------------------------------------------------------------- *
476 * @brief makeInputGraph
477 *
478 * The input graph models whether a kernel could *consume* more data than may be produced by a preceeding kernel.
479 ** ------------------------------------------------------------------------------------------------------------- */
480PipelineGenerator::ChannelGraph PipelineGenerator::makeInputGraph() const {
481    const auto n = kernels.size();
482    ChannelGraph G(n);
483    KernelMap M;
484    for (unsigned v = 0; v < n; ++v) {
485
486        const Kernel * const consumer = kernels[v];
487        G[v] = consumer;
488        M.emplace(consumer, v);
489
490        const auto & inputs = consumer->getStreamInputs();
491        for (unsigned i = 0; i < inputs.size(); ++i) {
492
493            const Binding & input = inputs[i];
494            auto ub_in = consumer->getUpperBound(input.getRate()) * consumer->getStride() * codegen::SegmentSize; assert (ub_in > 0);
495            if (input.hasLookahead()) {
496                ub_in += input.getLookahead();
497            }
498
499            const auto buffer = consumer->getStreamSetInputBuffer(i);
500            const Kernel * const producer = buffer->getProducer();
501            const Binding & output = producer->getStreamOutput(buffer);
502            const auto lb_out = producer->getLowerBound(output.getRate()) * producer->getStride() * codegen::SegmentSize;
503
504            const auto min_oi_ratio = lb_out / ub_in;
505            const auto f = M.find(producer); assert (f != M.end());
506            const auto u = f->second;
507            // If we have multiple inputs from the same kernel, we only need to consider the "slowest" one
508            bool slowest = true;
509            for (const auto e : make_iterator_range(in_edges(v, G))) {
510                if (source(e, G) == u) {
511                    const Channel & p = G[e];
512                    if (min_oi_ratio > p.ratio) {
513                        slowest = false;
514                    } else if (min_oi_ratio < p.ratio) {
515                        clear_in_edges(v, G);
516                    }
517                    break;
518                }
519            }
520            if (slowest) {
521                add_edge(u, v, Channel{min_oi_ratio, buffer, i}, G);
522            }
523        }
524    }
525
526    return pruneGraph(std::move(G), make_iterator_range(vertices(G)));
527}
528
529/** ------------------------------------------------------------------------------------------------------------- *
530 * @brief makeOutputGraph
531 *
532 * The output graph models whether a kernel could *produce* more data than may be consumed by a subsequent kernel.
533 ** ------------------------------------------------------------------------------------------------------------- */
534PipelineGenerator::ChannelGraph PipelineGenerator::makeOutputGraph() const {
535    const auto n = kernels.size();
536    ChannelGraph G(n);
537    KernelMap M;
538    for (unsigned v = 0; v < n; ++v) {
539        const Kernel * const consumer = kernels[v];
540        G[v] = consumer;
541        M.emplace(consumer, v);
542
543        const auto & inputs = consumer->getStreamInputs();
544        for (unsigned i = 0; i < inputs.size(); ++i) {
545            const auto buffer = consumer->getStreamSetInputBuffer(i);
546            if (isa<SourceBuffer>(buffer)) continue;
547            const Kernel * const producer = buffer->getProducer();
548            assert (consumer != producer);
549            const Binding & output = producer->getStreamOutput(buffer);
550            auto ub_out = producer->getUpperBound(output.getRate()) * producer->getStride() * codegen::SegmentSize;
551            if (ub_out > 0) { // unknown output rates are handled by reallocating their buffers
552                const Binding & input = inputs[i];
553                if (input.hasLookahead()) {
554                    const auto la = input.getLookahead();
555                    if (LLVM_UNLIKELY(ub_out <= la)) {
556                        llvm::report_fatal_error("lookahead exceeds segment size");
557                    }
558                    ub_out += la;
559                }
560                const auto lb_in = consumer->getLowerBound(input.getRate()) * consumer->getStride() * codegen::SegmentSize;
561                const auto min_io_ratio = lb_in / ub_out;
562                const auto f = M.find(producer); assert (f != M.end());
563                const auto u = f->second;
564                assert (v != u);
565                assert (G[u] == producer);
566                // If we have multiple inputs from the same kernel, we only need to consider the "fastest" one
567                bool fastest = true;
568                for (const auto e : make_iterator_range(in_edges(v, G))) {
569                    if (source(e, G) == u) {
570                        const Channel & p = G[e];
571                        if (min_io_ratio > p.ratio) {
572                            fastest = false;
573                        } else if (min_io_ratio < p.ratio) {
574                            clear_in_edges(v, G);
575                        }
576                        break;
577                    }
578                }
579                if (fastest) {
580                    add_edge(v, u, Channel{min_io_ratio, buffer, i}, G);
581                }
582            }
583        }
584    }
585
586    return pruneGraph(std::move(G), boost::adaptors::reverse(make_iterator_range(vertices(G))));
587}
588
589/** ------------------------------------------------------------------------------------------------------------- *
590 * @brief pruneGraph
591 ** ------------------------------------------------------------------------------------------------------------- */
592template<class VertexList>
593inline PipelineGenerator::ChannelGraph PipelineGenerator::pruneGraph(ChannelGraph && G, VertexList && V) const {
594    // Take a transitive closure of G but whenever we attempt to insert an edge into the closure
595    // that already exists, check instead whether the rate of our proposed edge is <= the existing
596    // edge's rate. If so, the data availability/consumption is transitively guaranteed.
597    for (const auto u : V) {
598        for (auto ei : make_iterator_range(in_edges(u, G))) {
599            const auto v = source(ei, G);
600            const Channel & ci = G[ei];
601            for (auto ej : make_iterator_range(out_edges(u, G))) {
602                const auto w = target(ej, G);
603                // ci.rate = BOUND_RATIO(u, v) * (STRIDE(u) / STRIDE(v))
604                const auto scaling = RateValue(G[v]->getStride(), G[w]->getStride());
605                const auto rate = ci.ratio * scaling;
606                bool insert = true;
607                for (auto ek : make_iterator_range(in_edges(w, G))) {
608                    // do we already have a vw edge?
609                    if (source(ek, G) == v) {
610                        Channel & ck = G[ek];
611                        if (rate <= ck.ratio) {
612                            ck.buffer = nullptr;
613                        }
614                        insert = false;
615                    }
616                }
617                if (insert) {
618                    add_edge(v, w, Channel{rate}, G);
619                }
620            }
621        }
622    }
623
624    // remove any closure edges from G
625    remove_edge_if([&G](const ChannelGraph::edge_descriptor e) { return G[e].buffer == nullptr; }, G);
626
627    for (const auto u : V) {
628        if (in_degree(u, G) == 0) {
629            // If we do not need to check any of its inputs, we can avoid testing any output of a kernel
630            // with a rate ratio of at least 1
631            remove_out_edge_if(u, [&G](const ChannelGraph::edge_descriptor e) {
632                return G[e].ratio >= RateValue{1, 1};
633            }, G);
634        }
635    }
636
637    return G;
638}
639
640/** ------------------------------------------------------------------------------------------------------------- *
641 * @brief executeKernel
642 ** ------------------------------------------------------------------------------------------------------------- */
643void PipelineGenerator::execute(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
644
645    const Kernel * const kernel = kernels[index];
646    b->setKernel(kernel);
647
648    const auto & inputs = kernel->getStreamInputs();
649    const auto & outputs = kernel->getStreamOutputs();
650
651    BasicBlock * const kernelEntry = b->GetInsertBlock();
652    BasicBlock * const kernelCode = b->CreateBasicBlock(kernel->getName());
653    kernelFinished = b->CreateBasicBlock(kernel->getName() + "Finished");
654    BasicBlock * const kernelExit = b->CreateBasicBlock(kernel->getName() + "Exit");
655
656    b->CreateUnlikelyCondBr(b->getTerminationSignal(), kernelExit, kernelCode);
657
658    b->SetInsertPoint(kernelFinished);
659    terminated = b->CreatePHI(b->getInt1Ty(), 2);
660    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
661        madeProgress = b->CreatePHI(b->getInt1Ty(), 3);
662    }
663    b->SetInsertPoint(kernelExit);
664    PHINode * const isFinal = b->CreatePHI(b->getInt1Ty(), 2, kernel->getName() + "_isFinal");
665    isFinal->addIncoming(b->getTrue(), kernelEntry);
666    isFinal->addIncoming(terminated, kernelFinished);
667
668    PHINode * progress = nullptr;
669    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
670        progress = b->CreatePHI(b->getInt1Ty(), 2, kernel->getName() + "_anyProgress");
671        progress->addIncoming(anyProgress, kernelEntry);
672        progress->addIncoming(madeProgress, kernelFinished);
673    }
674
675    // Since it is possible that a sole consumer of some stream could terminate early, set the
676    // initial consumed amount to the amount produced in this iteration.
677
678    // First determine the priorConsumedItemCounts, making sure
679    // that none of them are previous input buffers of this kernel!
680    std::vector<Value *> priorConsumedItemCount(inputs.size());
681
682    for (unsigned i = 0; i < inputs.size(); ++i) {
683        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
684        auto c = consumedItemCount.find(buffer);
685        if (c == consumedItemCount.end()) {
686            const auto p = producedItemCount.find(buffer);
687            assert (p != producedItemCount.end());
688            priorConsumedItemCount[i] = p->second;
689        } else {
690            priorConsumedItemCount[i] = c->second;
691        }
692    }
693
694    std::vector<PHINode *> consumedItemCountPhi(inputs.size());
695
696    for (unsigned i = 0; i < inputs.size(); ++i) {
697        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
698        PHINode * const consumedPhi = b->CreatePHI(b->getSizeTy(), 2);
699        auto c = consumedItemCount.find(buffer);
700        if (c == consumedItemCount.end()) {
701            consumedItemCount.emplace(buffer, consumedPhi);
702        } else {
703            c->second = consumedPhi;
704        }
705        consumedPhi->addIncoming(priorConsumedItemCount[i], kernelEntry);
706        consumedItemCountPhi[i] = consumedPhi;
707    }
708
709    b->SetInsertPoint(kernelCode);
710
711    checkIfAllInputKernelsAreTerminated(b, index);
712
713    checkAvailableInputData(b, index);
714
715    checkAvailableOutputSpace(b, index);
716
717    applyOutputBufferExpansions(b, index);
718
719    Value * const finalStride = callKernel(b, index);
720
721    // TODO: add in some checks to verify the kernel actually adheres to its rate
722
723    BasicBlock * const kernelCodeExit = b->GetInsertBlock();
724    terminated->addIncoming(finalStride, kernelCodeExit);
725    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
726        madeProgress->addIncoming(b->getTrue(), kernelCodeExit);
727        anyProgress = progress;
728    }
729    b->CreateBr(kernelFinished);
730
731    b->SetInsertPoint(kernelFinished);
732
733    // update the consumed item counts
734    for (unsigned i = 0; i < inputs.size(); ++i) {
735        const Binding & input = inputs[i];
736        Value * const fullyProcessed = getFullyProcessedItemCount(b, input, terminated);
737        Value * const consumed = b->CreateUMin(priorConsumedItemCount[i], fullyProcessed);
738        consumedItemCountPhi[i]->addIncoming(consumed, kernelFinished);
739    }
740    b->CreateBr(kernelExit);
741
742    kernelExit->moveAfter(kernelFinished);
743
744    b->SetInsertPoint(kernelExit);
745
746    for (unsigned i = 0; i < outputs.size(); ++i) {
747        const Binding & output = outputs[i];
748        Value * const produced = b->getProducedItemCount(output.getName());
749        const StreamSetBuffer * const buffer = kernel->getStreamSetOutputBuffer(i);
750        // if some stream has no consumer, set the consumed item count to the produced item count
751        const auto c = lastConsumer.find(buffer);
752        assert (c != lastConsumer.end());
753        if (LLVM_UNLIKELY(c->second == kernel)) {
754            assert (buffer->getProducer() == kernel);
755            if (LLVM_UNLIKELY(output.getRate().isRelative())) {
756                continue;
757            }
758            b->setConsumedItemCount(output.getName(), produced);
759        } else { // otherwise record how many items were produced
760            assert (producedItemCount.count(buffer) == 0);
761            producedItemCount.emplace(buffer, produced);
762        }
763
764    }
765
766
767    // TODO: if all consumers process the data at a fixed rate, we can just set the consumed item count
768    // by the strideNo rather than tracking it.
769
770
771    // If this kernel is the last consumer of a input buffer, update the consumed count for that buffer.
772    // NOTE: unless we can prove that this kernel cannot terminate before any prior consumer, we cannot
773    // put this code into the kernelFinished block.
774    for (unsigned i = 0; i < inputs.size(); ++i) {
775        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
776        const auto c = lastConsumer.find(buffer);
777        assert (c != lastConsumer.end());
778        if (LLVM_LIKELY(c->second == kernel)) {
779            Kernel * const producer = buffer->getProducer();
780            assert (producer != kernel);
781            const auto & output = producer->getStreamOutput(buffer);
782            if (output.getRate().isRelative()) continue;
783            b->setKernel(producer);
784            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
785                Value * const alreadyConsumed = b->getConsumedItemCount(output.getName());
786                b->CreateAssert(b->CreateICmpULE(alreadyConsumed, consumedItemCountPhi[i]),
787                                producer->getName() + ": " + output.getName() + " consumed item count is not monotonically non-decreasing!");
788            }
789            b->setConsumedItemCount(output.getName(), consumedItemCountPhi[i]);
790            b->setKernel(kernel);
791        }
792    }
793
794    dependencyGraph[index] = isFinal;
795}
796
797/** ------------------------------------------------------------------------------------------------------------- *
798 * @brief checkAvailableInputData
799 ** ------------------------------------------------------------------------------------------------------------- */
800void PipelineGenerator::checkIfAllInputKernelsAreTerminated(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
801    const auto n = in_degree(index, dependencyGraph);
802    if (LLVM_UNLIKELY(n == 0)) {
803        noMore = b->getFalse();
804    } else {
805        noMore = b->getTrue();
806        for (auto e : make_iterator_range(in_edges(index, dependencyGraph))) {
807            const auto u = source(e, dependencyGraph);
808            Value * const finished = dependencyGraph[u];
809            //b->CallPrintInt("* " + kernels[u]->getName() + "_hasFinished", finished);
810            noMore = b->CreateAnd(noMore, finished);
811        }
812    }
813}
814
815/** ------------------------------------------------------------------------------------------------------------- *
816 * @brief checkAvailableInputData
817 ** ------------------------------------------------------------------------------------------------------------- */
818void PipelineGenerator::checkAvailableInputData(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
819    const Kernel * const kernel = kernels[index];
820    b->setKernel(kernel);
821    for (auto e : make_iterator_range(in_edges(index, inputGraph))) {
822        const Channel & c = inputGraph[e];
823        const Binding & input = kernel->getStreamInput(c.operand);
824
825        Value * requiredInput = getStrideLength(b, kernel, input);
826        if (LLVM_UNLIKELY(input.hasLookahead())) {
827            Constant * const lookahead = b->getSize(input.getLookahead());
828            requiredInput = b->CreateAdd(requiredInput, lookahead);
829        }
830        const auto p = producedItemCount.find(c.buffer);
831        assert (p != producedItemCount.end());
832        Value * const produced = p->second;
833        Value * const processed = b->getNonDeferredProcessedItemCount(input);
834        Value * const unprocessed = b->CreateSub(produced, processed);
835        Value * const hasEnough = b->CreateICmpUGE(unprocessed, requiredInput);
836        Value * const check = b->CreateOr(hasEnough, noMore);
837        terminated->addIncoming(b->getFalse(), b->GetInsertBlock());
838        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
839            madeProgress->addIncoming(anyProgress, b->GetInsertBlock());
840        }
841        BasicBlock * const hasSufficientInput = b->CreateBasicBlock(kernel->getName() + "_" + input.getName() + "_hasSufficientInput");
842        b->CreateLikelyCondBr(check, hasSufficientInput, kernelFinished);
843        b->SetInsertPoint(hasSufficientInput);
844    }
845}
846
847/** ------------------------------------------------------------------------------------------------------------- *
848 * @brief checkAvailableOutputSpace
849 ** ------------------------------------------------------------------------------------------------------------- */
850void PipelineGenerator::checkAvailableOutputSpace(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
851    const Kernel * const kernel = kernels[index];
852    b->setKernel(kernel);
853    for (auto e : make_iterator_range(in_edges(index, outputGraph))) {
854        const Channel & c = outputGraph[e];
855        assert (c.buffer->getProducer() == kernel);
856        const Binding & output = kernel->getStreamOutput(c.buffer);
857
858        Value * requiredSpace = getStrideLength(b, kernel, output);
859        const auto & name = output.getName();
860        Value * const produced = b->getNonDeferredProducedItemCount(output);
861        Value * const consumed = b->getConsumedItemCount(name);
862        Value * const unconsumed = b->CreateSub(produced, consumed);
863        requiredSpace = b->CreateAdd(requiredSpace, unconsumed);
864        Value * const capacity = b->getBufferedSize(name);
865        Value * const check = b->CreateICmpULE(requiredSpace, capacity);
866        terminated->addIncoming(b->getFalse(), b->GetInsertBlock());
867        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
868            madeProgress->addIncoming(anyProgress, b->GetInsertBlock());
869        }
870        BasicBlock * const hasOutputSpace = b->CreateBasicBlock(kernel->getName() + "_" + name + "_hasOutputSpace");
871        b->CreateLikelyCondBr(check, hasOutputSpace, kernelFinished);
872        b->SetInsertPoint(hasOutputSpace);
873    }
874}
875
876/** ------------------------------------------------------------------------------------------------------------- *
877 * @brief getStrideLength
878 ** ------------------------------------------------------------------------------------------------------------- */
879Value * PipelineGenerator::getStrideLength(const std::unique_ptr<KernelBuilder> & b, const Kernel * const kernel, const Binding & binding) {
880    Value * strideLength = nullptr;
881    const ProcessingRate & rate = binding.getRate();
882    if (rate.isPopCount() || rate.isNegatedPopCount()) {
883        Port refPort; unsigned refIndex;
884        std::tie(refPort, refIndex) = kernel->getStreamPort(rate.getReference());
885        const Binding & ref = kernel->getStreamInput(refIndex);
886        Value * markers = b->loadInputStreamBlock(ref.getName(), b->getSize(0));
887        if (rate.isNegatedPopCount()) {
888            markers = b->CreateNot(markers);
889        }
890        strideLength = b->bitblock_popcount(markers);
891    } else if (binding.hasAttribute(kernel::Attribute::KindId::AlwaysConsume)) {
892        const auto lb = kernel->getLowerBound(rate);
893        strideLength = b->getSize(ceiling(lb * kernel->getStride()));
894    } else {
895        const auto ub = kernel->getUpperBound(rate); assert (ub > 0);
896        strideLength = b->getSize(ceiling(ub * kernel->getStride()));
897    }
898    return strideLength;
899}
900
901/** ------------------------------------------------------------------------------------------------------------- *
902 * @brief callKernel
903 ** ------------------------------------------------------------------------------------------------------------- */
904Value * PipelineGenerator::callKernel(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
905
906    const Kernel * const kernel = kernels[index];
907    b->setKernel(kernel);
908
909    #ifndef DISABLE_COPY_TO_OVERFLOW
910    // Store how many items we produced by this kernel in the prior iteration. We'll use this to determine when
911    // to mirror the first K segments
912    const auto & outputs = kernel->getStreamOutputs();
913    const auto m = outputs.size();
914
915    std::vector<Value *> initiallyProducedItemCount(m, nullptr);
916    for (unsigned i = 0; i < m; ++i) {
917        const Binding & output = outputs[i];
918        const auto & name = output.getName();
919        const StreamSetBuffer * const buffer = kernel->getOutputStreamSetBuffer(name);
920        if (isConsumedAtNonFixedRate.count(buffer)) {
921            initiallyProducedItemCount[i] = b->getProducedItemCount(name);
922        }
923    }
924    #endif
925
926    const auto & inputs = kernel->getStreamInputs();
927    const auto n = inputs.size();
928    std::vector<Value *> arguments(n + 2);
929
930    Value * isFinal = noMore;
931    for (unsigned i = 0; i < n; ++i) {
932        const Binding & input = inputs[i];
933        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
934
935        const auto p = producedItemCount.find(buffer);
936        assert (p != producedItemCount.end());
937        Value * const produced = p->second;
938
939        const ProcessingRate & rate = input.getRate();
940        if (rate.isPopCount()) {
941            arguments[i + 2] = produced;
942        } else {
943            const unsigned strideSize = ceiling(kernel->getUpperBound(rate) * kernel->getStride());
944            Value * const processed = b->getNonDeferredProcessedItemCount(input);
945            Value * const limit = b->CreateAdd(processed, b->getSize(strideSize * codegen::SegmentSize));
946            Value * const partial = b->CreateICmpULT(produced, limit);
947            arguments[i + 2] = b->CreateSelect(partial, produced, limit);
948            isFinal = b->CreateAnd(isFinal, partial);
949        }
950    }
951
952    // TODO: pass in a strideNo for fixed rate streams to allow the kernel to calculate the current avail,
953    // processed, and produced counts
954
955    arguments[0] = kernel->getInstance();
956    arguments[1] = isFinal;
957
958    b->createDoSegmentCall(arguments);
959
960    #ifndef DISABLE_COPY_TO_OVERFLOW
961    // For each buffer with an overflow region of K blocks, overwrite the overflow with the first K blocks of
962    // data to ensure that even if this stream is produced at a fixed rate but consumed at a bounded rate,
963    // every kernel has a consistent view of the stream data.
964    for (unsigned i = 0; i < m; ++i) {
965        const Binding & output = outputs[i];
966        const auto & name = output.getName();
967        if (initiallyProducedItemCount[i]) {
968            Value * const bufferSize = b->getBufferedSize(name);
969            Value * const prior = initiallyProducedItemCount[i];
970            Value * const offset = b->CreateURem(prior, bufferSize);
971            Value * const produced = b->getNonDeferredProducedItemCount(output);
972            Value * const buffered = b->CreateAdd(offset, b->CreateSub(produced, prior));
973            BasicBlock * const copyBack = b->CreateBasicBlock(name + "MirrorOverflow");
974            BasicBlock * const done = b->CreateBasicBlock(name + "MirrorOverflowDone");
975            b->CreateCondBr(b->CreateICmpUGT(buffered, bufferSize), copyBack, done);
976            b->SetInsertPoint(copyBack);
977            b->CreateCopyToOverflow(name);
978            b->CreateBr(done);
979            b->SetInsertPoint(done);
980        }
981    }
982    #endif
983
984    return b->getTerminationSignal();
985}
986
987/** ------------------------------------------------------------------------------------------------------------- *
988 * @brief applyOutputBufferExpansions
989 ** ------------------------------------------------------------------------------------------------------------- */
990void PipelineGenerator::applyOutputBufferExpansions(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
991    const Kernel * const kernel = kernels[index];
992    const auto & outputs = kernel->getStreamSetOutputBuffers();
993    for (unsigned i = 0; i < outputs.size(); i++) {
994        if (isa<DynamicBuffer>(outputs[i])) {
995
996
997            const auto baseSize = ceiling(kernel->getUpperBound(kernel->getStreamOutput(i).getRate()) * kernel->getStride() * codegen::SegmentSize);
998            if (LLVM_LIKELY(baseSize > 0)) {
999
1000                const auto & name = kernel->getStreamOutput(i).getName();
1001
1002                BasicBlock * const doExpand = b->CreateBasicBlock(name + "Expand");
1003                BasicBlock * const nextBlock = b->GetInsertBlock()->getNextNode();
1004                doExpand->moveAfter(b->GetInsertBlock());
1005                BasicBlock * const bufferReady = b->CreateBasicBlock(name + "Ready");
1006                bufferReady->moveAfter(doExpand);
1007                if (nextBlock) nextBlock->moveAfter(bufferReady);
1008
1009                Value * const produced = b->getProducedItemCount(name);
1010                Value * const consumed = b->getConsumedItemCount(name);
1011                Value * const required = b->CreateAdd(b->CreateSub(produced, consumed), b->getSize(2 * baseSize));
1012
1013                b->CreateCondBr(b->CreateICmpUGT(required, b->getBufferedSize(name)), doExpand, bufferReady);
1014                b->SetInsertPoint(doExpand);
1015
1016                b->doubleCapacity(name);
1017                // Ensure that capacity is sufficient by successive doubling, if necessary.
1018                b->CreateCondBr(b->CreateICmpUGT(required, b->getBufferedSize(name)), doExpand, bufferReady);
1019
1020                b->SetInsertPoint(bufferReady);
1021
1022            }
1023        }
1024    }
1025}
1026
1027
1028/** ------------------------------------------------------------------------------------------------------------- *
1029 * @brief getFullyProcessedItemCount
1030 ** ------------------------------------------------------------------------------------------------------------- */
1031inline Value * PipelineGenerator::getFullyProcessedItemCount(const std::unique_ptr<KernelBuilder> & b, const Binding & input, Value * const isFinal) const {
1032    Value * const processed = b->getProcessedItemCount(input.getName());
1033    if (LLVM_UNLIKELY(input.hasAttribute(kernel::Attribute::KindId::BlockSize))) {
1034        // If the input rate has a block size attribute then --- for the purpose of determining how many
1035        // items have been consumed --- we consider a stream set to be fully processed when an entire
1036        // block (stride?) has been processed.
1037        Constant * const BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
1038        Value * const partial = b->CreateAnd(processed, ConstantExpr::getNeg(BLOCK_WIDTH));
1039        return b->CreateSelect(isFinal, processed, partial);
1040    }
1041    return processed;
1042}
1043
1044/** ------------------------------------------------------------------------------------------------------------- *
1045 * @brief finalize
1046 ** ------------------------------------------------------------------------------------------------------------- */
1047Value * PipelineGenerator::finalize(const std::unique_ptr<KernelBuilder> & b) {
1048    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1049        ConstantInt * const ZERO = b->getSize(0);
1050        ConstantInt * const ONE = b->getSize(1);
1051        ConstantInt * const TWO = b->getSize(2);
1052        Value * const count = b->CreateSelect(anyProgress, ZERO, b->CreateAdd(deadLockCounter, ONE));
1053        b->CreateAssert(b->CreateICmpNE(count, TWO), "Dead lock detected: pipeline could not progress after two iterations");
1054        deadLockCounter->addIncoming(count, b->GetInsertBlock());
1055    }
1056    // return whether each sink has terminated
1057    Value * final = b->getTrue();
1058    for (const auto u : make_iterator_range(vertices(dependencyGraph))) {
1059        if (out_degree(u, dependencyGraph) == 0) {
1060            final = b->CreateAnd(final, dependencyGraph[u]);
1061        }
1062    }
1063    return final;
1064
1065}
1066
1067/** ------------------------------------------------------------------------------------------------------------- *
1068 * @brief printGraph
1069 ** ------------------------------------------------------------------------------------------------------------- */
1070void PipelineGenerator::printGraph(const ChannelGraph & G) const {
1071
1072    auto & out = errs();
1073
1074    out << "digraph G {\n";
1075    for (auto u : make_iterator_range(vertices(G))) {
1076        assert (G[u] == kernels[u]);
1077        if (in_degree(u, G) > 0 || out_degree(u, G) > 0) {
1078            out << "v" << u << " [label=\"" << u << ": "
1079                << G[u]->getName() << "\"];\n";
1080        }
1081    }
1082
1083    for (auto e : make_iterator_range(edges(G))) {
1084        const Channel & c = G[e];
1085        const auto s = source(e, G);
1086        const auto t = target(e, G);
1087
1088        out << "v" << s << " -> v" << t
1089            << " [label=\""
1090
1091
1092
1093            << c.ratio.numerator() << " / " << c.ratio.denominator()
1094            << "\"];\n";
1095    }
1096
1097    out << "}\n\n";
1098    out.flush();
1099
1100}
1101
1102/** ------------------------------------------------------------------------------------------------------------- *
1103 * @brief printGraph
1104 ** ------------------------------------------------------------------------------------------------------------- */
1105void PipelineGenerator::printGraph(const DependencyGraph & G) const {
1106
1107    auto & out = errs();
1108
1109    out << "digraph G {\n";
1110    for (auto u : make_iterator_range(vertices(G))) {
1111            out << "v" << u << " [label=\"" << u << ": "
1112                << kernels[u]->getName() << "\"];\n";
1113    }
1114
1115    for (auto e : make_iterator_range(edges(G))) {
1116        const auto s = source(e, G);
1117        const auto t = target(e, G);
1118        out << "v" << s << " -> v" << t << ";\n";
1119    }
1120
1121    out << "}\n\n";
1122    out.flush();
1123
1124}
Note: See TracBrowser for help on using the repository browser.