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

Last change on this file since 5995 was 5995, checked in by cameron, 18 months ago

Fix a pipeline bug when two kernel inputs have the same buffer!

File size: 49.5 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), std::move(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), std::move(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            const auto p = producedItemCount.find(buffer);
702            assert (p != producedItemCount.end());
703            consumedItemCount.emplace(buffer, consumedPhi);
704        } else {
705            c->second = consumedPhi;
706        }
707        consumedPhi->addIncoming(priorConsumedItemCount[i], kernelEntry);
708        consumedItemCountPhi[i] = consumedPhi;
709    }
710
711    b->SetInsertPoint(kernelCode);
712
713    checkIfAllInputKernelsAreTerminated(b, index);
714
715    checkAvailableInputData(b, index);
716
717    checkAvailableOutputSpace(b, index);
718
719    applyOutputBufferExpansions(b, index);
720
721    Value * const finalStride = callKernel(b, index);
722
723    // TODO: add in some checks to verify the kernel actually adheres to its rate
724
725    BasicBlock * const kernelCodeExit = b->GetInsertBlock();
726    terminated->addIncoming(finalStride, kernelCodeExit);
727    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
728        madeProgress->addIncoming(b->getTrue(), kernelCodeExit);
729        anyProgress = progress;
730    }
731    b->CreateBr(kernelFinished);
732
733    b->SetInsertPoint(kernelFinished);
734
735    // update the consumed item counts
736    for (unsigned i = 0; i < inputs.size(); ++i) {
737        const Binding & input = inputs[i];
738        Value * const fullyProcessed = getFullyProcessedItemCount(b, input, terminated);
739        Value * const consumed = b->CreateUMin(priorConsumedItemCount[i], fullyProcessed);
740        consumedItemCountPhi[i]->addIncoming(consumed, kernelFinished);
741    }
742    b->CreateBr(kernelExit);
743
744    kernelExit->moveAfter(kernelFinished);
745
746    b->SetInsertPoint(kernelExit);
747
748    for (unsigned i = 0; i < outputs.size(); ++i) {
749        const Binding & output = outputs[i];
750        Value * const produced = b->getProducedItemCount(output.getName());
751        const StreamSetBuffer * const buffer = kernel->getStreamSetOutputBuffer(i);
752        // if some stream has no consumer, set the consumed item count to the produced item count
753        const auto c = lastConsumer.find(buffer);
754        assert (c != lastConsumer.end());
755        if (LLVM_UNLIKELY(c->second == kernel)) {
756            assert (buffer->getProducer() == kernel);
757            if (LLVM_UNLIKELY(output.getRate().isRelative())) {
758                continue;
759            }
760            b->setConsumedItemCount(output.getName(), produced);
761        } else { // otherwise record how many items were produced
762            assert (producedItemCount.count(buffer) == 0);
763            producedItemCount.emplace(buffer, produced);
764        }
765
766    }
767
768
769    // TODO: if all consumers process the data at a fixed rate, we can just set the consumed item count
770    // by the strideNo rather than tracking it.
771
772
773    // If this kernel is the last consumer of a input buffer, update the consumed count for that buffer.
774    // NOTE: unless we can prove that this kernel cannot terminate before any prior consumer, we cannot
775    // put this code into the kernelFinished block.
776    for (unsigned i = 0; i < inputs.size(); ++i) {
777        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
778        const auto c = lastConsumer.find(buffer);
779        assert (c != lastConsumer.end());
780        if (LLVM_LIKELY(c->second == kernel)) {
781            Kernel * const producer = buffer->getProducer();
782            assert (producer != kernel);
783            const auto & output = producer->getStreamOutput(buffer);
784            if (output.getRate().isRelative()) continue;
785            b->setKernel(producer);
786            if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
787                Value * const alreadyConsumed = b->getConsumedItemCount(output.getName());
788                b->CreateAssert(b->CreateICmpULE(alreadyConsumed, consumedItemCountPhi[i]),
789                                producer->getName() + ": " + output.getName() + " consumed item count is not monotonically non-decreasing!");
790            }
791            b->setConsumedItemCount(output.getName(), consumedItemCountPhi[i]);
792            b->setKernel(kernel);
793        }
794    }
795
796    dependencyGraph[index] = isFinal;
797}
798
799/** ------------------------------------------------------------------------------------------------------------- *
800 * @brief checkAvailableInputData
801 ** ------------------------------------------------------------------------------------------------------------- */
802void PipelineGenerator::checkIfAllInputKernelsAreTerminated(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
803    const auto n = in_degree(index, dependencyGraph);
804    if (LLVM_UNLIKELY(n == 0)) {
805        noMore = b->getFalse();
806    } else {
807        noMore = b->getTrue();
808        for (auto e : make_iterator_range(in_edges(index, dependencyGraph))) {
809            const auto u = source(e, dependencyGraph);
810            Value * const finished = dependencyGraph[u];
811            //b->CallPrintInt("* " + kernels[u]->getName() + "_hasFinished", finished);
812            noMore = b->CreateAnd(noMore, finished);
813        }
814    }
815}
816
817/** ------------------------------------------------------------------------------------------------------------- *
818 * @brief checkAvailableInputData
819 ** ------------------------------------------------------------------------------------------------------------- */
820void PipelineGenerator::checkAvailableInputData(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
821    const Kernel * const kernel = kernels[index];
822    b->setKernel(kernel);
823    for (auto e : make_iterator_range(in_edges(index, inputGraph))) {
824        const Channel & c = inputGraph[e];
825        const Binding & input = kernel->getStreamInput(c.operand);
826
827        Value * requiredInput = getStrideLength(b, kernel, input);
828        if (LLVM_UNLIKELY(input.hasLookahead())) {
829            Constant * const lookahead = b->getSize(input.getLookahead());
830            requiredInput = b->CreateAdd(requiredInput, lookahead);
831        }
832        const auto p = producedItemCount.find(c.buffer);
833        assert (p != producedItemCount.end());
834        Value * const produced = p->second;
835        Value * const processed = b->getNonDeferredProcessedItemCount(input);
836        Value * const unprocessed = b->CreateSub(produced, processed);
837        Value * const hasEnough = b->CreateICmpUGE(unprocessed, requiredInput);
838        Value * const check = b->CreateOr(hasEnough, noMore);
839        terminated->addIncoming(b->getFalse(), b->GetInsertBlock());
840        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
841            madeProgress->addIncoming(anyProgress, b->GetInsertBlock());
842        }
843        BasicBlock * const hasSufficientInput = b->CreateBasicBlock(kernel->getName() + "_" + input.getName() + "_hasSufficientInput");
844        b->CreateLikelyCondBr(check, hasSufficientInput, kernelFinished);
845        b->SetInsertPoint(hasSufficientInput);
846    }
847}
848
849/** ------------------------------------------------------------------------------------------------------------- *
850 * @brief checkAvailableOutputSpace
851 ** ------------------------------------------------------------------------------------------------------------- */
852void PipelineGenerator::checkAvailableOutputSpace(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
853    const Kernel * const kernel = kernels[index];
854    b->setKernel(kernel);
855    for (auto e : make_iterator_range(in_edges(index, outputGraph))) {
856        const Channel & c = outputGraph[e];
857        assert (c.buffer->getProducer() == kernel);
858        const Binding & output = kernel->getStreamOutput(c.buffer);
859
860        Value * requiredSpace = getStrideLength(b, kernel, output);
861        const auto & name = output.getName();
862        Value * const produced = b->getNonDeferredProducedItemCount(output);
863        Value * const consumed = b->getConsumedItemCount(name);
864        Value * const unconsumed = b->CreateSub(produced, consumed);
865        requiredSpace = b->CreateAdd(requiredSpace, unconsumed);
866        Value * const capacity = b->getBufferedSize(name);
867        Value * const check = b->CreateICmpULE(requiredSpace, capacity);
868        terminated->addIncoming(b->getFalse(), b->GetInsertBlock());
869        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
870            madeProgress->addIncoming(anyProgress, b->GetInsertBlock());
871        }
872        BasicBlock * const hasOutputSpace = b->CreateBasicBlock(kernel->getName() + "_" + name + "_hasOutputSpace");
873        b->CreateLikelyCondBr(check, hasOutputSpace, kernelFinished);
874        b->SetInsertPoint(hasOutputSpace);
875    }
876}
877
878/** ------------------------------------------------------------------------------------------------------------- *
879 * @brief getStrideLength
880 ** ------------------------------------------------------------------------------------------------------------- */
881Value * PipelineGenerator::getStrideLength(const std::unique_ptr<KernelBuilder> & b, const Kernel * const kernel, const Binding & binding) {
882    Value * strideLength = nullptr;
883    const ProcessingRate & rate = binding.getRate();
884    if (rate.isPopCount() || rate.isNegatedPopCount()) {
885        Port refPort; unsigned refIndex;
886        std::tie(refPort, refIndex) = kernel->getStreamPort(rate.getReference());
887        const Binding & ref = kernel->getStreamInput(refIndex);
888        Value * markers = b->loadInputStreamBlock(ref.getName(), b->getSize(0));
889        if (rate.isNegatedPopCount()) {
890            markers = b->CreateNot(markers);
891        }
892        strideLength = b->bitblock_popcount(markers);
893    } else if (binding.hasAttribute(kernel::Attribute::KindId::AlwaysConsume)) {
894        const auto lb = kernel->getLowerBound(rate);
895        strideLength = b->getSize(ceiling(lb * kernel->getStride()));
896    } else {
897        const auto ub = kernel->getUpperBound(rate); assert (ub > 0);
898        strideLength = b->getSize(ceiling(ub * kernel->getStride()));
899    }
900    return strideLength;
901}
902
903/** ------------------------------------------------------------------------------------------------------------- *
904 * @brief callKernel
905 ** ------------------------------------------------------------------------------------------------------------- */
906Value * PipelineGenerator::callKernel(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
907
908    const Kernel * const kernel = kernels[index];
909    b->setKernel(kernel);
910
911    #ifndef DISABLE_COPY_TO_OVERFLOW
912    // Store how many items we produced by this kernel in the prior iteration. We'll use this to determine when
913    // to mirror the first K segments
914    const auto & outputs = kernel->getStreamOutputs();
915    const auto m = outputs.size();
916
917    std::vector<Value *> initiallyProducedItemCount(m, nullptr);
918    for (unsigned i = 0; i < m; ++i) {
919        const Binding & output = outputs[i];
920        const auto & name = output.getName();
921        const StreamSetBuffer * const buffer = kernel->getOutputStreamSetBuffer(name);
922        if (isConsumedAtNonFixedRate.count(buffer)) {
923            initiallyProducedItemCount[i] = b->getProducedItemCount(name);
924        }
925    }
926    #endif
927
928    const auto & inputs = kernel->getStreamInputs();
929    const auto n = inputs.size();
930    std::vector<Value *> arguments(n + 2);
931
932    Value * isFinal = noMore;
933    for (unsigned i = 0; i < n; ++i) {
934        const Binding & input = inputs[i];
935        const StreamSetBuffer * const buffer = kernel->getStreamSetInputBuffer(i);
936
937        const auto p = producedItemCount.find(buffer);
938        assert (p != producedItemCount.end());
939        Value * const produced = p->second;
940
941        const ProcessingRate & rate = input.getRate();
942        if (rate.isPopCount()) {
943            arguments[i + 2] = produced;
944        } else {
945            const unsigned strideSize = ceiling(kernel->getUpperBound(rate) * kernel->getStride());
946            Value * const processed = b->getNonDeferredProcessedItemCount(input);
947            Value * const limit = b->CreateAdd(processed, b->getSize(strideSize * codegen::SegmentSize));
948            Value * const partial = b->CreateICmpULT(produced, limit);
949            arguments[i + 2] = b->CreateSelect(partial, produced, limit);
950            isFinal = b->CreateAnd(isFinal, partial);
951        }
952    }
953
954    // TODO: pass in a strideNo for fixed rate streams to allow the kernel to calculate the current avail,
955    // processed, and produced counts
956
957    arguments[0] = kernel->getInstance();
958    arguments[1] = isFinal;
959
960    b->createDoSegmentCall(arguments);
961
962    #ifndef DISABLE_COPY_TO_OVERFLOW
963    // For each buffer with an overflow region of K blocks, overwrite the overflow with the first K blocks of
964    // data to ensure that even if this stream is produced at a fixed rate but consumed at a bounded rate,
965    // every kernel has a consistent view of the stream data.
966    for (unsigned i = 0; i < m; ++i) {
967        const Binding & output = outputs[i];
968        const auto & name = output.getName();
969        if (initiallyProducedItemCount[i]) {
970            Value * const bufferSize = b->getBufferedSize(name);
971            Value * const prior = initiallyProducedItemCount[i];
972            Value * const offset = b->CreateURem(prior, bufferSize);
973            Value * const produced = b->getNonDeferredProducedItemCount(output);
974            Value * const buffered = b->CreateAdd(offset, b->CreateSub(produced, prior));
975            BasicBlock * const copyBack = b->CreateBasicBlock(name + "MirrorOverflow");
976            BasicBlock * const done = b->CreateBasicBlock(name + "MirrorOverflowDone");
977            b->CreateCondBr(b->CreateICmpUGT(buffered, bufferSize), copyBack, done);
978            b->SetInsertPoint(copyBack);
979            b->CreateCopyToOverflow(name);
980            b->CreateBr(done);
981            b->SetInsertPoint(done);
982        }
983    }
984    #endif
985
986    return b->getTerminationSignal();
987}
988
989/** ------------------------------------------------------------------------------------------------------------- *
990 * @brief applyOutputBufferExpansions
991 ** ------------------------------------------------------------------------------------------------------------- */
992void PipelineGenerator::applyOutputBufferExpansions(const std::unique_ptr<KernelBuilder> & b, const unsigned index) {
993    const Kernel * const kernel = kernels[index];
994    const auto & outputs = kernel->getStreamSetOutputBuffers();
995    for (unsigned i = 0; i < outputs.size(); i++) {
996        if (isa<DynamicBuffer>(outputs[i])) {
997
998
999            const auto baseSize = ceiling(kernel->getUpperBound(kernel->getStreamOutput(i).getRate()) * kernel->getStride() * codegen::SegmentSize);
1000            if (LLVM_LIKELY(baseSize > 0)) {
1001
1002                const auto & name = kernel->getStreamOutput(i).getName();
1003
1004                BasicBlock * const doExpand = b->CreateBasicBlock(name + "Expand");
1005                BasicBlock * const nextBlock = b->GetInsertBlock()->getNextNode();
1006                doExpand->moveAfter(b->GetInsertBlock());
1007                BasicBlock * const bufferReady = b->CreateBasicBlock(name + "Ready");
1008                bufferReady->moveAfter(doExpand);
1009                if (nextBlock) nextBlock->moveAfter(bufferReady);
1010
1011                Value * const produced = b->getProducedItemCount(name);
1012                Value * const consumed = b->getConsumedItemCount(name);
1013                Value * const required = b->CreateAdd(b->CreateSub(produced, consumed), b->getSize(2 * baseSize));
1014
1015                b->CreateCondBr(b->CreateICmpUGT(required, b->getBufferedSize(name)), doExpand, bufferReady);
1016                b->SetInsertPoint(doExpand);
1017
1018                b->doubleCapacity(name);
1019                // Ensure that capacity is sufficient by successive doubling, if necessary.
1020                b->CreateCondBr(b->CreateICmpUGT(required, b->getBufferedSize(name)), doExpand, bufferReady);
1021
1022                b->SetInsertPoint(bufferReady);
1023
1024            }
1025        }
1026    }
1027}
1028
1029
1030/** ------------------------------------------------------------------------------------------------------------- *
1031 * @brief getFullyProcessedItemCount
1032 ** ------------------------------------------------------------------------------------------------------------- */
1033inline Value * PipelineGenerator::getFullyProcessedItemCount(const std::unique_ptr<KernelBuilder> & b, const Binding & input, Value * const isFinal) const {
1034    Value * const processed = b->getProcessedItemCount(input.getName());
1035    if (LLVM_UNLIKELY(input.hasAttribute(kernel::Attribute::KindId::BlockSize))) {
1036        // If the input rate has a block size attribute then --- for the purpose of determining how many
1037        // items have been consumed --- we consider a stream set to be fully processed when an entire
1038        // block (stride?) has been processed.
1039        Constant * const BLOCK_WIDTH = b->getSize(b->getBitBlockWidth());
1040        Value * const partial = b->CreateAnd(processed, ConstantExpr::getNeg(BLOCK_WIDTH));
1041        return b->CreateSelect(isFinal, processed, partial);
1042    }
1043    return processed;
1044}
1045
1046/** ------------------------------------------------------------------------------------------------------------- *
1047 * @brief finalize
1048 ** ------------------------------------------------------------------------------------------------------------- */
1049Value * PipelineGenerator::finalize(const std::unique_ptr<KernelBuilder> & b) {
1050    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1051        ConstantInt * const ZERO = b->getSize(0);
1052        ConstantInt * const ONE = b->getSize(1);
1053        ConstantInt * const TWO = b->getSize(2);
1054        Value * const count = b->CreateSelect(anyProgress, ZERO, b->CreateAdd(deadLockCounter, ONE));
1055        b->CreateAssert(b->CreateICmpNE(count, TWO), "Dead lock detected: pipeline could not progress after two iterations");
1056        deadLockCounter->addIncoming(count, b->GetInsertBlock());
1057    }
1058    // return whether each sink has terminated
1059    Value * final = b->getTrue();
1060    for (const auto u : make_iterator_range(vertices(dependencyGraph))) {
1061        if (out_degree(u, dependencyGraph) == 0) {
1062            final = b->CreateAnd(final, dependencyGraph[u]);
1063        }
1064    }
1065    return final;
1066
1067}
1068
1069/** ------------------------------------------------------------------------------------------------------------- *
1070 * @brief printGraph
1071 ** ------------------------------------------------------------------------------------------------------------- */
1072void PipelineGenerator::printGraph(const ChannelGraph & G) const {
1073
1074    auto & out = errs();
1075
1076    out << "digraph G {\n";
1077    for (auto u : make_iterator_range(vertices(G))) {
1078        assert (G[u] == kernels[u]);
1079        if (in_degree(u, G) > 0 || out_degree(u, G) > 0) {
1080            out << "v" << u << " [label=\"" << u << ": "
1081                << G[u]->getName() << "\"];\n";
1082        }
1083    }
1084
1085    for (auto e : make_iterator_range(edges(G))) {
1086        const Channel & c = G[e];
1087        const auto s = source(e, G);
1088        const auto t = target(e, G);
1089
1090        out << "v" << s << " -> v" << t
1091            << " [label=\""
1092
1093
1094
1095            << c.ratio.numerator() << " / " << c.ratio.denominator()
1096            << "\"];\n";
1097    }
1098
1099    out << "}\n\n";
1100    out.flush();
1101
1102}
1103
1104/** ------------------------------------------------------------------------------------------------------------- *
1105 * @brief printGraph
1106 ** ------------------------------------------------------------------------------------------------------------- */
1107void PipelineGenerator::printGraph(const DependencyGraph & G) const {
1108
1109    auto & out = errs();
1110
1111    out << "digraph G {\n";
1112    for (auto u : make_iterator_range(vertices(G))) {
1113            out << "v" << u << " [label=\"" << u << ": "
1114                << kernels[u]->getName() << "\"];\n";
1115    }
1116
1117    for (auto e : make_iterator_range(edges(G))) {
1118        const auto s = source(e, G);
1119        const auto t = target(e, G);
1120        out << "v" << s << " -> v" << t << ";\n";
1121    }
1122
1123    out << "}\n\n";
1124    out.flush();
1125
1126}
Note: See TracBrowser for help on using the repository browser.