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

Last change on this file since 5620 was 5620, checked in by nmedfort, 19 months ago

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

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