source: icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp @ 5792

Last change on this file since 5792 was 5782, checked in by nmedfort, 22 months ago

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

File size: 31.2 KB
Line 
1/*
2 *  Copyright (c) 2014-16 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "pablo_compiler.h"
8#include <pablo/pablo_kernel.h>
9#include <pablo/pablo_toolchain.h>
10#include <pablo/codegenstate.h>
11#include <pablo/boolean.h>
12#include <pablo/arithmetic.h>
13#include <pablo/branch.h>
14#include <pablo/pe_advance.h>
15#include <pablo/pe_lookahead.h>
16#include <pablo/pe_matchstar.h>
17#include <pablo/pe_scanthru.h>
18#include <pablo/pe_infile.h>
19#include <pablo/pe_count.h>
20#include <pablo/pe_integer.h>
21#include <pablo/pe_string.h>
22#include <pablo/pe_zeroes.h>
23#include <pablo/pe_ones.h>
24#include <pablo/pe_var.h>
25#include <pablo/ps_assign.h>
26#ifdef USE_CARRYPACK_MANAGER
27#include <pablo/carrypack_manager.h>
28#else
29#include <pablo/carry_manager.h>
30#endif
31#include <kernels/kernel_builder.h>
32#include <kernels/streamset.h>
33#include <llvm/IR/Module.h>
34#include <llvm/Support/raw_os_ostream.h>
35
36using namespace llvm;
37
38namespace pablo {
39
40using TypeId = PabloAST::ClassTypeId;
41
42inline static unsigned getAlignment(const Value * const type) {
43    return type->getType()->getPrimitiveSizeInBits() / 8;
44}
45
46inline static unsigned getPointerElementAlignment(const Value * const ptr) {
47    return ptr->getType()->getPointerElementType()->getPrimitiveSizeInBits() / 8;
48}
49
50void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
51    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
52    mBranchCount = 0;
53    examineBlock(iBuilder, mKernel->getEntryBlock());
54    mCarryManager->initializeCarryData(iBuilder, mKernel);
55    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
56        const auto count = (mBranchCount * 2) + 1;
57        mKernel->addScalar(ArrayType::get(mKernel->getSizeTy(), count), "profile");
58        mBasicBlock.reserve(count);
59    }
60}
61
62void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
63    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
64    mCarryManager->releaseCarryData(iBuilder);
65}
66
67void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
68    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
69    mCarryManager->initializeCodeGen(iBuilder);
70    PabloBlock * const entryBlock = mKernel->getEntryBlock(); assert (entryBlock);
71    mMarker.emplace(entryBlock->createZeroes(), iBuilder->allZeroes());
72    mMarker.emplace(entryBlock->createOnes(), iBuilder->allOnes());
73    mBranchCount = 0;
74    addBranchCounter(iBuilder);
75    compileBlock(iBuilder, entryBlock);
76    mCarryManager->finalizeCodeGen(iBuilder);
77}
78
79void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
80    for (const Statement * stmt : *block) {
81        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
82            const Lookahead * const la = cast<Lookahead>(stmt);
83            PabloAST * input = la->getExpression();
84            if (isa<Extract>(input)) {
85                input = cast<Extract>(input)->getArray();
86            }
87            bool notFound = true;
88            if (LLVM_LIKELY(isa<Var>(input))) {
89                for (unsigned i = 0; i < mKernel->getNumOfInputs(); ++i) {
90                    if (input == mKernel->getInput(i)) {
91                        const auto & binding = mKernel->getStreamInput(i);
92                        if (LLVM_UNLIKELY(!binding.hasLookahead() || binding.getLookahead() < la->getAmount())) {
93                            std::string tmp;
94                            raw_string_ostream out(tmp);
95                            input->print(out);
96                            out << " must have a lookahead attribute of at least " << la->getAmount();
97                            report_fatal_error(out.str());
98                        }
99                        notFound = false;
100                        break;
101                    }
102                }
103            }
104            if (LLVM_UNLIKELY(notFound)) {
105                report_fatal_error("Lookahead " + stmt->getName() + " can only be performed on an input streamset");
106            }
107        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
108            ++mBranchCount;
109            examineBlock(iBuilder, cast<Branch>(stmt)->getBody());
110        } else if (LLVM_UNLIKELY(isa<Count>(stmt))) {
111            mAccumulator.insert(std::make_pair(stmt, iBuilder->getInt32(mKernel->addUnnamedScalar(stmt->getType()))));
112        }
113    }   
114}
115
116void PabloCompiler::addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) {
117    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {       
118        Value * ptr = iBuilder->getScalarFieldPtr("profile");
119        assert (mBasicBlock.size() < ptr->getType()->getPointerElementType()->getArrayNumElements());
120        ptr = iBuilder->CreateGEP(ptr, {iBuilder->getInt32(0), iBuilder->getInt32(mBasicBlock.size())});
121        const auto alignment = getPointerElementAlignment(ptr);
122        Value * value = iBuilder->CreateAlignedLoad(ptr, alignment, false, "branchCounter");
123        value = iBuilder->CreateAdd(value, ConstantInt::get(cast<IntegerType>(value->getType()), 1));
124        iBuilder->CreateAlignedStore(value, ptr, alignment);
125        mBasicBlock.push_back(iBuilder->GetInsertBlock());
126    }
127}
128
129inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const block) {
130    for (const Statement * statement : *block) {
131        compileStatement(iBuilder, statement);
132    }
133}
134
135void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const If * const ifStatement) {
136    //
137    //  The If-ElseZero stmt:
138    //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
139    //  If the value of the predicate is nonzero, then determine the values of variables
140    //  <var>* by executing the given statements.  Otherwise, the value of the
141    //  variables are all zero.  Requirements: (a) no variable that is defined within
142    //  the body of the if may be accessed outside unless it is explicitly
143    //  listed in the variable list, (b) every variable in the defined list receives
144    //  a value within the body, and (c) the logical consequence of executing
145    //  the statements in the event that the predicate is zero is that the
146    //  values of all defined variables indeed work out to be 0.
147    //
148    //  Simple Implementation with Phi nodes:  a phi node in the if exit block
149    //  is inserted for each variable in the defined variable list.  It receives
150    //  a zero value from the ifentry block and the defined value from the if
151    //  body.
152    //
153
154    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
155    ++mBranchCount;
156    BasicBlock * const ifBodyBlock = iBuilder->CreateBasicBlock("if.body_" + std::to_string(mBranchCount));
157    BasicBlock * const ifEndBlock = iBuilder->CreateBasicBlock("if.end_" + std::to_string(mBranchCount));
158   
159    std::vector<std::pair<const Var *, Value *>> incoming;
160
161    for (const Var * var : ifStatement->getEscaped()) {
162        if (LLVM_UNLIKELY(var->isKernelParameter())) {
163            Value * marker = nullptr;
164            if (var->isScalar()) {
165                marker = iBuilder->getScalarFieldPtr(var->getName());
166            } else if (var->isReadOnly()) {
167                marker = iBuilder->getInputStreamBlockPtr(var->getName(), iBuilder->getInt32(0));
168            } else if (var->isReadNone()) {
169                marker = iBuilder->getOutputStreamBlockPtr(var->getName(), iBuilder->getInt32(0));
170            }
171            mMarker[var] = marker;
172        } else {
173            auto f = mMarker.find(var);
174            if (LLVM_UNLIKELY(f == mMarker.end())) {
175                std::string tmp;
176                raw_string_ostream out(tmp);
177                var->print(out);
178                out << " is uninitialized prior to entering ";
179                ifStatement->print(out);
180                report_fatal_error(out.str());
181            }
182            incoming.emplace_back(var, f->second);
183        }
184    }
185
186    const PabloBlock * ifBody = ifStatement->getBody();
187   
188    mCarryManager->enterIfScope(iBuilder, ifBody);
189
190    Value * condition = compileExpression(iBuilder, ifStatement->getCondition());
191    if (condition->getType() == iBuilder->getBitBlockType()) {
192        condition = iBuilder->bitblock_any(mCarryManager->generateSummaryTest(iBuilder, condition));
193    }
194   
195    iBuilder->CreateCondBr(condition, ifBodyBlock, ifEndBlock);
196   
197    // Entry processing is complete, now handle the body of the if.
198    iBuilder->SetInsertPoint(ifBodyBlock);
199
200    mCarryManager->enterIfBody(iBuilder, ifEntryBlock);
201
202    addBranchCounter(iBuilder);
203
204    compileBlock(iBuilder, ifBody);
205
206    mCarryManager->leaveIfBody(iBuilder, iBuilder->GetInsertBlock());
207
208    BasicBlock * ifExitBlock = iBuilder->GetInsertBlock();
209
210    iBuilder->CreateBr(ifEndBlock);
211
212    ifEndBlock->moveAfter(ifExitBlock);
213
214    //End Block
215    iBuilder->SetInsertPoint(ifEndBlock);
216
217    mCarryManager->leaveIfScope(iBuilder, ifEntryBlock, ifExitBlock);
218
219    for (const auto i : incoming) {
220        const Var * var; Value * incoming;
221        std::tie(var, incoming) = i;
222
223        auto f = mMarker.find(var);
224        if (LLVM_UNLIKELY(f == mMarker.end())) {
225            std::string tmp;
226            raw_string_ostream out(tmp);
227            out << "PHINode creation error: ";
228            var->print(out);
229            out << " was not assigned an outgoing value.";
230            report_fatal_error(out.str());
231        }
232
233        Value * const outgoing = f->second;
234        if (LLVM_UNLIKELY(incoming == outgoing)) {
235            continue;
236        }
237
238        if (LLVM_UNLIKELY(incoming->getType() != outgoing->getType())) {
239            std::string tmp;
240            raw_string_ostream out(tmp);
241            out << "PHINode creation error: incoming type of ";
242            var->print(out);
243            out << " (";
244            incoming->getType()->print(out);
245            out << ") differs from the outgoing type (";
246            outgoing->getType()->print(out);
247            out << ") within ";
248            ifStatement->print(out);
249            report_fatal_error(out.str());
250        }
251
252        PHINode * phi = iBuilder->CreatePHI(incoming->getType(), 2, var->getName());
253        phi->addIncoming(incoming, ifEntryBlock);
254        phi->addIncoming(outgoing, ifExitBlock);
255        f->second = phi;
256    }
257
258    addBranchCounter(iBuilder);
259}
260
261void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const While * const whileStatement) {
262
263    const PabloBlock * const whileBody = whileStatement->getBody();
264
265    BasicBlock * whileEntryBlock = iBuilder->GetInsertBlock();
266
267    const auto escaped = whileStatement->getEscaped();
268
269#ifdef ENABLE_BOUNDED_WHILE
270    PHINode * bound_phi = nullptr;  // Needed for bounded while loops.
271#endif
272    // On entry to the while structure, proceed to execute the first iteration
273    // of the loop body unconditionally. The while condition is tested at the end of
274    // the loop.
275
276    for (const Var * var : escaped) {
277        if (LLVM_UNLIKELY(var->isKernelParameter())) {
278            Value * marker = nullptr;
279            if (var->isScalar()) {
280                marker = iBuilder->getScalarFieldPtr(var->getName());
281            } else if (var->isReadOnly()) {
282                marker = iBuilder->getInputStreamBlockPtr(var->getName(), iBuilder->getInt32(0));
283            } else if (var->isReadNone()) {
284                marker = iBuilder->getOutputStreamBlockPtr(var->getName(), iBuilder->getInt32(0));
285            }
286            mMarker[var] = marker;
287        }
288    }
289
290    mCarryManager->enterLoopScope(iBuilder, whileBody);
291
292    BasicBlock * whileBodyBlock = iBuilder->CreateBasicBlock("while.body_" + std::to_string(mBranchCount));
293    BasicBlock * whileEndBlock = iBuilder->CreateBasicBlock("while.end_" + std::to_string(mBranchCount));
294    ++mBranchCount;
295
296    iBuilder->CreateBr(whileBodyBlock);
297
298    iBuilder->SetInsertPoint(whileBodyBlock);
299
300    //
301    // There are 3 sets of Phi nodes for the while loop.
302    // (1) Carry-ins: (a) incoming carry data first iterations, (b) zero thereafter
303    // (2) Carry-out accumulators: (a) zero first iteration, (b) |= carry-out of each iteration
304    // (3) Next nodes: (a) values set up before loop, (b) modified values calculated in loop.
305#ifdef ENABLE_BOUNDED_WHILE
306    // (4) The loop bound, if any.
307#endif
308
309    std::vector<std::pair<const Var *, PHINode *>> variants;
310
311    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
312    for (const auto var : escaped) {
313        auto f = mMarker.find(var);
314        if (LLVM_UNLIKELY(f == mMarker.end())) {
315            std::string tmp;
316            raw_string_ostream out(tmp);
317            out << "PHINode creation error: ";
318            var->print(out);
319            out << " is uninitialized prior to entering ";
320            whileStatement->print(out);
321            report_fatal_error(out.str());
322        }
323        Value * entryValue = f->second;
324        PHINode * phi = iBuilder->CreatePHI(entryValue->getType(), 2, var->getName());
325        phi->addIncoming(entryValue, whileEntryBlock);
326        f->second = phi;
327        assert(mMarker[var] == phi);
328        variants.emplace_back(var, phi);
329    }
330#ifdef ENABLE_BOUNDED_WHILE
331    if (whileStatement->getBound()) {
332        bound_phi = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2, "while_bound");
333        bound_phi->addIncoming(iBuilder->getSize(whileStatement->getBound()), whileEntryBlock);
334    }
335#endif
336
337    mCarryManager->enterLoopBody(iBuilder, whileEntryBlock);
338
339    addBranchCounter(iBuilder);
340
341    compileBlock(iBuilder, whileBody);
342
343    // After the whileBody has been compiled, we may be in a different basic block.
344
345    mCarryManager->leaveLoopBody(iBuilder, iBuilder->GetInsertBlock());
346
347
348#ifdef ENABLE_BOUNDED_WHILE
349    if (whileStatement->getBound()) {
350        Value * new_bound = iBuilder->CreateSub(bound_phi, iBuilder->getSize(1));
351        bound_phi->addIncoming(new_bound, whileExitBlock);
352        condition = iBuilder->CreateAnd(condition, iBuilder->CreateICmpUGT(new_bound, ConstantInt::getNullValue(iBuilder->getSizeTy())));
353    }
354#endif
355
356    BasicBlock * const whileExitBlock = iBuilder->GetInsertBlock();
357
358    // and for any variant nodes in the loop body
359    for (const auto variant : variants) {
360        const Var * var; PHINode * incomingPhi;
361        std::tie(var, incomingPhi) = variant;
362        const auto f = mMarker.find(var);
363        if (LLVM_UNLIKELY(f == mMarker.end())) {
364            std::string tmp;
365            raw_string_ostream out(tmp);
366            out << "PHINode creation error: ";
367            var->print(out);
368            out << " is no longer assigned a value.";
369            report_fatal_error(out.str());
370        }
371
372        Value * const outgoingValue = f->second;
373
374        if (LLVM_UNLIKELY(incomingPhi->getType() != outgoingValue->getType())) {
375            std::string tmp;
376            raw_string_ostream out(tmp);
377            out << "PHINode creation error: incoming type of ";
378            var->print(out);
379            out << " (";
380            incomingPhi->getType()->print(out);
381            out << ") differs from the outgoing type (";
382            outgoingValue->getType()->print(out);
383            out << ") within ";
384            whileStatement->print(out);
385            report_fatal_error(out.str());
386        }
387
388        incomingPhi->addIncoming(outgoingValue, whileExitBlock);
389    }
390
391    // Terminate the while loop body with a conditional branch back.
392    Value * condition = compileExpression(iBuilder, whileStatement->getCondition());
393    if (condition->getType() == iBuilder->getBitBlockType()) {
394        condition = iBuilder->bitblock_any(mCarryManager->generateSummaryTest(iBuilder, condition));
395    }
396
397    iBuilder->CreateCondBr(condition, whileBodyBlock, whileEndBlock);
398
399    whileEndBlock->moveAfter(whileExitBlock);
400
401    iBuilder->SetInsertPoint(whileEndBlock);
402
403    mCarryManager->leaveLoopScope(iBuilder, whileEntryBlock, whileExitBlock);
404
405    addBranchCounter(iBuilder);
406}
407
408void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const Statement * const stmt) {
409
410    if (LLVM_UNLIKELY(isa<If>(stmt))) {
411        compileIf(iBuilder, cast<If>(stmt));
412    } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
413        compileWhile(iBuilder, cast<While>(stmt));
414    } else {
415        const PabloAST * expr = stmt;
416        Value * value = nullptr;
417        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
418            value = compileExpression(iBuilder, cast<Assign>(stmt)->getValue());
419            expr = cast<Assign>(stmt)->getVariable();
420            Value * ptr = nullptr;
421            if (LLVM_LIKELY(isa<Var>(expr))) {
422                const Var * var = cast<Var>(expr);
423                if (LLVM_UNLIKELY(var->isReadOnly())) {
424                    std::string tmp;
425                    raw_string_ostream out(tmp);
426                    out << mKernel->getName();
427                    out << " cannot assign value to ";
428                    var->print(out);
429                    out << ": ";
430                    var->print(out);
431                    out << " is read only";
432                    report_fatal_error(out.str());
433                }
434                if (var->isKernelParameter()) {
435                    if (var->isScalar()) {
436                        ptr = iBuilder->getScalarFieldPtr(var->getName());
437                    } else {
438                        ptr = iBuilder->getOutputStreamBlockPtr(var->getName(), iBuilder->getInt32(0));
439                    }
440                }
441            } else if (isa<Extract>(expr)) {
442                const auto f = mMarker.find(expr);
443                if (LLVM_UNLIKELY(f == mMarker.end())) {
444                    std::string tmp;
445                    raw_string_ostream out(tmp);
446                    out << mKernel->getName();
447                    out << " cannot assign value to ";
448                    expr->print(out);
449                    out << ": ";
450                    expr->print(out);
451                    out << " does not dominate ";
452                    stmt->print(out);
453                    report_fatal_error(out.str());
454                }
455                ptr = f->second;
456                assert (ptr);
457            }
458            if (ptr) {
459                iBuilder->CreateAlignedStore(value, ptr, getAlignment(value));
460                value = ptr;
461            }
462        } else if (const Extract * extract = dyn_cast<Extract>(stmt)) {
463            Value * index = compileExpression(iBuilder, extract->getIndex());
464            Var * const array = dyn_cast<Var>(extract->getArray());
465            if (LLVM_LIKELY(array && array->isKernelParameter())) {
466                if (array->isReadOnly()) {
467                    value = iBuilder->getInputStreamBlockPtr(array->getName(), index);
468                    value = iBuilder->CreateLoad(value);
469                } else if (array->isReadNone()) {
470                    value = iBuilder->getOutputStreamBlockPtr(array->getName(), index);
471                } else {
472                    std::string tmp;
473                    raw_string_ostream out(tmp);
474                    out << mKernel->getName();
475                    out << " stream ";
476                    expr->print(out);
477                    out << " cannot be read or written to";
478                    report_fatal_error(out.str());
479                }
480            } else {
481                Value * ptr = compileExpression(iBuilder, extract->getArray(), false);
482                value = iBuilder->CreateGEP(ptr, {ConstantInt::getNullValue(index->getType()), index}, "extract");
483            }
484        } else if (isa<And>(stmt)) {
485            value = compileExpression(iBuilder, stmt->getOperand(0));
486            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
487                value = iBuilder->simd_and(value, compileExpression(iBuilder, stmt->getOperand(1)));
488            }
489        } else if (isa<Or>(stmt)) {
490            value = compileExpression(iBuilder, stmt->getOperand(0));
491            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
492                value = iBuilder->simd_or(value, compileExpression(iBuilder, stmt->getOperand(1)));
493            }
494        } else if (isa<Xor>(stmt)) {
495            value = compileExpression(iBuilder, stmt->getOperand(0));
496            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
497                value = iBuilder->simd_xor(value, compileExpression(iBuilder, stmt->getOperand(1)));
498            }
499        } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
500            Value* ifMask = compileExpression(iBuilder, sel->getCondition());
501            Value* ifTrue = iBuilder->simd_and(ifMask, compileExpression(iBuilder, sel->getTrueExpr()));
502            Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(iBuilder, sel->getFalseExpr()));
503            value = iBuilder->simd_or(ifTrue, ifFalse);
504        } else if (isa<Not>(stmt)) {
505            value = iBuilder->simd_not(compileExpression(iBuilder, stmt->getOperand(0)));
506        } else if (isa<Advance>(stmt)) {
507            const Advance * const adv = cast<Advance>(stmt);
508            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
509            // manager so that it properly selects the correct carry bit.
510            value = mCarryManager->advanceCarryInCarryOut(iBuilder, adv, compileExpression(iBuilder, adv->getExpression()));
511        } else if (isa<IndexedAdvance>(stmt)) {
512            const IndexedAdvance * const adv = cast<IndexedAdvance>(stmt);
513            Value * strm = compileExpression(iBuilder, adv->getExpression());
514            Value * index_strm = compileExpression(iBuilder, adv->getIndex());
515            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
516            // manager so that it properly selects the correct carry bit.
517            value = mCarryManager->indexedAdvanceCarryInCarryOut(iBuilder, adv, strm, index_strm);
518        } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
519            Value * const marker = compileExpression(iBuilder, mstar->getMarker());
520            Value * const cc = compileExpression(iBuilder, mstar->getCharClass());
521            Value * const marker_and_cc = iBuilder->simd_and(marker, cc);
522            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, mstar, marker_and_cc, cc);
523            value = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
524        } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
525            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
526            Value * const thru = compileExpression(iBuilder, sthru->getScanThru());
527            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, thru);
528            value = iBuilder->simd_and(sum, iBuilder->simd_not(thru));
529        } else if (const ScanTo * sthru = dyn_cast<ScanTo>(stmt)) {
530            Value * const marker_expr = compileExpression(iBuilder, sthru->getScanFrom());
531            Value * const to = iBuilder->simd_xor(compileExpression(iBuilder, sthru->getScanTo()), iBuilder->getScalarField("EOFmask"));
532            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, marker_expr, iBuilder->simd_not(to));
533            value = iBuilder->simd_and(sum, to);
534        } else if (const AdvanceThenScanThru * sthru = dyn_cast<AdvanceThenScanThru>(stmt)) {
535            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
536            Value * const thru = compileExpression(iBuilder, sthru->getScanThru());
537            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, iBuilder->simd_or(from, thru));
538            value = iBuilder->simd_and(sum, iBuilder->simd_not(thru));
539        } else if (const AdvanceThenScanTo * sthru = dyn_cast<AdvanceThenScanTo>(stmt)) {
540            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
541            Value * const to = iBuilder->simd_xor(compileExpression(iBuilder, sthru->getScanTo()), iBuilder->getScalarField("EOFmask"));
542            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, iBuilder->simd_or(from, iBuilder->simd_not(to)));
543            value = iBuilder->simd_and(sum, to);
544        } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
545            Value * EOFmask = iBuilder->getScalarField("EOFmask");
546            value = iBuilder->simd_and(compileExpression(iBuilder, e->getExpr()), iBuilder->simd_not(EOFmask));
547        } else if (const AtEOF * e = dyn_cast<AtEOF>(stmt)) {
548            Value * EOFbit = iBuilder->getScalarField("EOFbit");
549            value = iBuilder->simd_and(compileExpression(iBuilder, e->getExpr()), EOFbit);
550        } else if (const Count * c = dyn_cast<Count>(stmt)) {
551            Value * EOFbit = iBuilder->getScalarField("EOFbit");
552            Value * EOFmask = iBuilder->getScalarField("EOFmask");
553            Value * const to_count = iBuilder->simd_and(iBuilder->simd_or(iBuilder->simd_not(EOFmask), EOFbit), compileExpression(iBuilder, c->getExpr()));
554            const unsigned counterSize = iBuilder->getSizeTy()->getBitWidth();
555            const auto f = mAccumulator.find(c);
556            if (LLVM_UNLIKELY(f == mAccumulator.end())) {
557                report_fatal_error("Unknown accumulator: " + c->getName().str());
558            }
559            Value * ptr = iBuilder->getScalarFieldPtr(f->second);
560            const auto alignment = getPointerElementAlignment(ptr);
561            Value * countSoFar = iBuilder->CreateAlignedLoad(ptr, alignment, c->getName() + "_accumulator");
562            auto fields = (iBuilder->getBitBlockWidth() / counterSize);
563            Value * fieldCounts = iBuilder->simd_popcount(counterSize, to_count);
564            while (fields > 1) {
565                fields = fields/2;
566                fieldCounts = iBuilder->CreateAdd(fieldCounts, iBuilder->mvmd_srli(counterSize, fieldCounts, fields));
567            }
568            value = iBuilder->CreateAdd(iBuilder->mvmd_extract(counterSize, fieldCounts, 0), countSoFar, "countSoFar");
569            iBuilder->CreateAlignedStore(value, ptr, alignment);
570        } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
571            PabloAST * stream = l->getExpression();
572            Value * index = nullptr;
573            if (LLVM_UNLIKELY(isa<Extract>(stream))) {               
574                index = compileExpression(iBuilder, cast<Extract>(stream)->getIndex(), true);
575                stream = cast<Extract>(stream)->getArray();
576            } else {
577                index = iBuilder->getInt32(0);
578            }
579            const auto bit_shift = (l->getAmount() % iBuilder->getBitBlockWidth());
580            const auto block_shift = (l->getAmount() / iBuilder->getBitBlockWidth());
581            Value * ptr = iBuilder->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, iBuilder->getSize(block_shift));
582            Value * lookAhead = iBuilder->CreateBlockAlignedLoad(ptr);
583            if (bit_shift == 0) {  // Simple case with no intra-block shifting.
584                value = lookAhead;
585            } else { // Need to form shift result from two adjacent blocks.
586                Value * ptr = iBuilder->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, iBuilder->getSize(block_shift + 1));
587                Value * lookAhead1 = iBuilder->CreateBlockAlignedLoad(ptr);
588                if (LLVM_UNLIKELY((bit_shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
589                    value = iBuilder->mvmd_dslli(8, lookAhead1, lookAhead, (bit_shift / 8));
590                } else {
591                    Type  * const streamType = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
592                    Value * b1 = iBuilder->CreateBitCast(lookAhead1, streamType);
593                    Value * b0 = iBuilder->CreateBitCast(lookAhead, streamType);
594                    Value * result = iBuilder->CreateOr(iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - bit_shift), iBuilder->CreateLShr(b0, bit_shift));
595                    value = iBuilder->CreateBitCast(result, iBuilder->getBitBlockType());
596                }
597            }
598
599        } else {
600            std::string tmp;
601            raw_string_ostream out(tmp);
602            out << "PabloCompiler: ";
603            stmt->print(out);
604            out << " was not recognized by the compiler";
605            report_fatal_error(out.str());
606        }
607
608        mMarker[expr] = value;
609        if (DebugOptionIsSet(DumpTrace)) {
610            const String & name = isa<Var>(expr) ? cast<Var>(expr)->getName() : cast<Statement>(expr)->getName();
611            if (value->getType()->isVectorTy()) {
612                iBuilder->CallPrintRegister(name.str(), value);
613            } else if (value->getType()->isIntegerTy()) {
614                iBuilder->CallPrintInt(name.str(), value);
615            }
616        }
617    }
618}
619
620Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
621    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
622        return iBuilder->allOnes();
623    } else if (LLVM_UNLIKELY(isa<Zeroes>(expr))) {
624        return iBuilder->allZeroes();
625    } else if (LLVM_UNLIKELY(isa<Integer>(expr))) {
626        return ConstantInt::get(cast<Integer>(expr)->getType(), cast<Integer>(expr)->value());
627    } else if (LLVM_UNLIKELY(isa<Operator>(expr))) {
628        const Operator * op = cast<Operator>(expr);
629        Value * lh = compileExpression(iBuilder, op->getLH());
630        Value * rh = compileExpression(iBuilder, op->getRH());
631        if (LLVM_UNLIKELY(lh->getType() != rh->getType())) {
632            std::string tmp;
633            raw_string_ostream out(tmp);
634            out << "Operator creation error: left hand type of ";
635            expr->print(out);
636            out << " (";
637            lh->getType()->print(out);
638            out << ") differs from right hand type (";
639            rh->getType()->print(out);
640            out << ")";
641            report_fatal_error(out.str());
642        }
643        switch (op->getClassTypeId()) {
644            case TypeId::Add:
645                return iBuilder->CreateAdd(lh, rh);
646            case TypeId::Subtract:
647                return iBuilder->CreateSub(lh, rh);
648            case TypeId::LessThan:
649                return iBuilder->CreateICmpSLT(lh, rh);
650            case TypeId::LessThanEquals:
651                return iBuilder->CreateICmpSLE(lh, rh);
652            case TypeId::Equals:
653                return iBuilder->CreateICmpEQ(lh, rh);
654            case TypeId::GreaterThanEquals:
655                return iBuilder->CreateICmpSGE(lh, rh);
656            case TypeId::GreaterThan:
657                return iBuilder->CreateICmpSGT(lh, rh);
658            case TypeId::NotEquals:
659                return iBuilder->CreateICmpNE(lh, rh);
660            default: break;
661        }
662        std::string tmp;
663        raw_string_ostream out(tmp);
664        out << "PabloCompiler: ";
665        expr->print(out);
666        out << " is not a valid Operator";
667        report_fatal_error(out.str());
668    }
669    const auto f = mMarker.find(expr);
670    if (LLVM_UNLIKELY(f == mMarker.end())) {
671        std::string tmp;
672        raw_string_ostream out(tmp);
673        out << "PabloCompiler: ";
674        expr->print(out);
675        out << " was used before definition!";
676        report_fatal_error(out.str());
677    }
678    Value * value = f->second;
679    if (LLVM_UNLIKELY(isa<GetElementPtrInst>(value) && ensureLoaded)) {
680        value = iBuilder->CreateAlignedLoad(value, getPointerElementAlignment(value));
681    }
682    return value;
683}
684
685PabloCompiler::PabloCompiler(PabloKernel * const kernel)
686: mKernel(kernel)
687, mCarryManager(new CarryManager)
688, mBranchCount(0) {
689    assert ("PabloKernel cannot be null!" && kernel);
690}
691
692PabloCompiler::~PabloCompiler() {
693    delete mCarryManager;
694}
695
696}
Note: See TracBrowser for help on using the repository browser.