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

Last change on this file since 5646 was 5646, checked in by nmedfort, 2 years ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

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