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

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

First stage of MultiBlockKernel? and pipeline restructuring

File size: 30.9 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                    value = iBuilder->CreateLoad(value);
464                } else if (array->isReadNone()) {
465                    value = iBuilder->getOutputStreamBlockPtr(array->getName(), index);
466                } else {
467                    std::string tmp;
468                    raw_string_ostream out(tmp);
469                    out << mKernel->getName();
470                    out << " stream ";
471                    expr->print(out);
472                    out << " cannot be read or written to";
473                    report_fatal_error(out.str());
474                }
475            } else {
476                Value * ptr = compileExpression(iBuilder, extract->getArray(), false);
477                value = iBuilder->CreateGEP(ptr, {ConstantInt::getNullValue(index->getType()), index}, "extract");
478            }
479        } else if (isa<And>(stmt)) {
480            value = compileExpression(iBuilder, stmt->getOperand(0));
481            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
482                value = iBuilder->simd_and(value, compileExpression(iBuilder, stmt->getOperand(1)));
483            }
484        } else if (isa<Or>(stmt)) {
485            value = compileExpression(iBuilder, stmt->getOperand(0));
486            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
487                value = iBuilder->simd_or(value, compileExpression(iBuilder, stmt->getOperand(1)));
488            }
489        } else if (isa<Xor>(stmt)) {
490            value = compileExpression(iBuilder, stmt->getOperand(0));
491            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
492                value = iBuilder->simd_xor(value, compileExpression(iBuilder, stmt->getOperand(1)));
493            }
494        } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
495            Value* ifMask = compileExpression(iBuilder, sel->getCondition());
496            Value* ifTrue = iBuilder->simd_and(ifMask, compileExpression(iBuilder, sel->getTrueExpr()));
497            Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(iBuilder, sel->getFalseExpr()));
498            value = iBuilder->simd_or(ifTrue, ifFalse);
499        } else if (isa<Not>(stmt)) {
500            value = iBuilder->simd_not(compileExpression(iBuilder, stmt->getOperand(0)));
501        } else if (isa<Advance>(stmt)) {
502            const Advance * const adv = cast<Advance>(stmt);
503            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
504            // manager so that it properly selects the correct carry bit.
505            value = mCarryManager->advanceCarryInCarryOut(iBuilder, adv, compileExpression(iBuilder, adv->getExpression()));
506        } else if (isa<IndexedAdvance>(stmt)) {
507            const IndexedAdvance * const adv = cast<IndexedAdvance>(stmt);
508            Value * strm = compileExpression(iBuilder, adv->getExpression());
509            Value * index_strm = compileExpression(iBuilder, adv->getIndex());
510            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
511            // manager so that it properly selects the correct carry bit.
512            value = mCarryManager->indexedAdvanceCarryInCarryOut(iBuilder, adv, strm, index_strm);
513        } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
514            Value * const marker = compileExpression(iBuilder, mstar->getMarker());
515            Value * const cc = compileExpression(iBuilder, mstar->getCharClass());
516            Value * const marker_and_cc = iBuilder->simd_and(marker, cc);
517            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, mstar, marker_and_cc, cc);
518            value = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
519        } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
520            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
521            Value * const thru = compileExpression(iBuilder, sthru->getScanThru());
522            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, thru);
523            value = iBuilder->simd_and(sum, iBuilder->simd_not(thru));
524        } else if (const ScanTo * sthru = dyn_cast<ScanTo>(stmt)) {
525            Value * const marker_expr = compileExpression(iBuilder, sthru->getScanFrom());
526            Value * const to = iBuilder->simd_xor(compileExpression(iBuilder, sthru->getScanTo()), iBuilder->getScalarField("EOFmask"));
527            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, marker_expr, iBuilder->simd_not(to));
528            value = iBuilder->simd_and(sum, to);
529        } else if (const AdvanceThenScanThru * sthru = dyn_cast<AdvanceThenScanThru>(stmt)) {
530            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
531            Value * const thru = compileExpression(iBuilder, sthru->getScanThru());
532            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, iBuilder->simd_or(from, thru));
533            value = iBuilder->simd_and(sum, iBuilder->simd_not(thru));
534        } else if (const AdvanceThenScanTo * sthru = dyn_cast<AdvanceThenScanTo>(stmt)) {
535            Value * const from = compileExpression(iBuilder, sthru->getScanFrom());
536            Value * const to = iBuilder->simd_xor(compileExpression(iBuilder, sthru->getScanTo()), iBuilder->getScalarField("EOFmask"));
537            Value * const sum = mCarryManager->addCarryInCarryOut(iBuilder, sthru, from, iBuilder->simd_or(from, iBuilder->simd_not(to)));
538            value = iBuilder->simd_and(sum, to);
539        } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
540            Value * EOFmask = iBuilder->getScalarField("EOFmask");
541            value = iBuilder->simd_and(compileExpression(iBuilder, e->getExpr()), iBuilder->simd_not(EOFmask));
542        } else if (const AtEOF * e = dyn_cast<AtEOF>(stmt)) {
543            Value * EOFbit = iBuilder->getScalarField("EOFbit");
544            value = iBuilder->simd_and(compileExpression(iBuilder, e->getExpr()), EOFbit);
545        } else if (const Count * c = dyn_cast<Count>(stmt)) {
546            Value * EOFbit = iBuilder->getScalarField("EOFbit");
547            Value * EOFmask = iBuilder->getScalarField("EOFmask");
548            Value * const to_count = iBuilder->simd_and(iBuilder->simd_or(iBuilder->simd_not(EOFmask), EOFbit), compileExpression(iBuilder, c->getExpr()));
549            const unsigned counterSize = iBuilder->getSizeTy()->getBitWidth();
550            const auto f = mAccumulator.find(c);
551            if (LLVM_UNLIKELY(f == mAccumulator.end())) {
552                report_fatal_error("Unknown accumulator: " + c->getName().str());
553            }
554            Value * ptr = iBuilder->getScalarFieldPtr(f->second);
555            const auto alignment = getPointerElementAlignment(ptr);
556            Value * countSoFar = iBuilder->CreateAlignedLoad(ptr, alignment, c->getName() + "_accumulator");
557            auto fields = (iBuilder->getBitBlockWidth() / counterSize);
558            Value * fieldCounts = iBuilder->simd_popcount(counterSize, to_count);
559            while (fields > 1) {
560                fields = fields/2;
561                fieldCounts = iBuilder->CreateAdd(fieldCounts, iBuilder->mvmd_srli(counterSize, fieldCounts, fields));
562            }
563            value = iBuilder->CreateAdd(iBuilder->mvmd_extract(counterSize, fieldCounts, 0), countSoFar, "countSoFar");
564            iBuilder->CreateAlignedStore(value, ptr, alignment);
565        } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
566            PabloAST * stream = l->getExpression();
567            Value * index = nullptr;
568            if (LLVM_UNLIKELY(isa<Extract>(stream))) {
569                stream = cast<Extract>(stream)->getArray();
570                index = compileExpression(iBuilder, cast<Extract>(stream)->getIndex());
571            } else {
572                index = iBuilder->getInt32(0);
573            }
574            const auto bit_shift = (l->getAmount() % iBuilder->getBitBlockWidth());
575            const auto block_shift = (l->getAmount() / iBuilder->getBitBlockWidth());
576            Value * ptr = iBuilder->getAdjustedInputStreamBlockPtr(iBuilder->getSize(block_shift), cast<Var>(stream)->getName(), index);
577            Value * lookAhead = iBuilder->CreateBlockAlignedLoad(ptr);
578            if (bit_shift == 0) {  // Simple case with no intra-block shifting.
579                value = lookAhead;
580            } else { // Need to form shift result from two adjacent blocks.
581                Value * ptr = iBuilder->getAdjustedInputStreamBlockPtr(iBuilder->getSize(block_shift + 1), cast<Var>(stream)->getName(), index);
582                Value * lookAhead1 = iBuilder->CreateBlockAlignedLoad(ptr);
583                if (LLVM_UNLIKELY((bit_shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
584                    value = iBuilder->mvmd_dslli(8, lookAhead1, lookAhead, (bit_shift / 8));
585                } else {
586                    Type  * const streamType = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
587                    Value * b1 = iBuilder->CreateBitCast(lookAhead1, streamType);
588                    Value * b0 = iBuilder->CreateBitCast(lookAhead, streamType);
589                    Value * result = iBuilder->CreateOr(iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - bit_shift), iBuilder->CreateLShr(b0, bit_shift));
590                    value = iBuilder->CreateBitCast(result, iBuilder->getBitBlockType());
591                }
592            }
593
594        } else {
595            std::string tmp;
596            raw_string_ostream out(tmp);
597            out << "PabloCompiler: ";
598            stmt->print(out);
599            out << " was not recognized by the compiler";
600            report_fatal_error(out.str());
601        }
602
603        mMarker[expr] = value;
604        if (DebugOptionIsSet(DumpTrace)) {
605            const String & name = isa<Var>(expr) ? cast<Var>(expr)->getName() : cast<Statement>(expr)->getName();
606            if (value->getType()->isVectorTy()) {
607                iBuilder->CallPrintRegister(name.str(), value);
608            } else if (value->getType()->isIntegerTy()) {
609                iBuilder->CallPrintInt(name.str(), value);
610            }
611        }
612    }
613}
614
615Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloAST * expr, const bool ensureLoaded) const {
616    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
617        return iBuilder->allOnes();
618    } else if (LLVM_UNLIKELY(isa<Zeroes>(expr))) {
619        return iBuilder->allZeroes();
620    } else if (LLVM_UNLIKELY(isa<Integer>(expr))) {
621        return ConstantInt::get(cast<Integer>(expr)->getType(), cast<Integer>(expr)->value());
622    } else if (LLVM_UNLIKELY(isa<Operator>(expr))) {
623        const Operator * op = cast<Operator>(expr);
624        Value * lh = compileExpression(iBuilder, op->getLH());
625        Value * rh = compileExpression(iBuilder, op->getRH());
626        if (LLVM_UNLIKELY(lh->getType() != rh->getType())) {
627            std::string tmp;
628            raw_string_ostream out(tmp);
629            out << "Operator creation error: left hand type of ";
630            expr->print(out);
631            out << " (";
632            lh->getType()->print(out);
633            out << ") differs from right hand type (";
634            rh->getType()->print(out);
635            out << ")";
636            report_fatal_error(out.str());
637        }
638        switch (op->getClassTypeId()) {
639            case TypeId::Add:
640                return iBuilder->CreateAdd(lh, rh);
641            case TypeId::Subtract:
642                return iBuilder->CreateSub(lh, rh);
643            case TypeId::LessThan:
644                return iBuilder->CreateICmpSLT(lh, rh);
645            case TypeId::LessThanEquals:
646                return iBuilder->CreateICmpSLE(lh, rh);
647            case TypeId::Equals:
648                return iBuilder->CreateICmpEQ(lh, rh);
649            case TypeId::GreaterThanEquals:
650                return iBuilder->CreateICmpSGE(lh, rh);
651            case TypeId::GreaterThan:
652                return iBuilder->CreateICmpSGT(lh, rh);
653            case TypeId::NotEquals:
654                return iBuilder->CreateICmpNE(lh, rh);
655            default: break;
656        }
657        std::string tmp;
658        raw_string_ostream out(tmp);
659        out << "PabloCompiler: ";
660        expr->print(out);
661        out << " is not a valid Operator";
662        report_fatal_error(out.str());
663    }
664    const auto f = mMarker.find(expr);
665    if (LLVM_UNLIKELY(f == mMarker.end())) {
666        std::string tmp;
667        raw_string_ostream out(tmp);
668        out << "PabloCompiler: ";
669        expr->print(out);
670        out << " was used before definition!";
671        report_fatal_error(out.str());
672    }
673    Value * value = f->second;
674    if (LLVM_UNLIKELY(isa<GetElementPtrInst>(value) && ensureLoaded)) {
675        value = iBuilder->CreateAlignedLoad(value, getPointerElementAlignment(value));
676    }
677    return value;
678}
679
680PabloCompiler::PabloCompiler(PabloKernel * const kernel)
681: mKernel(kernel)
682, mCarryManager(new CarryManager)
683, mBranchCount(0) {
684    assert ("PabloKernel cannot be null!" && kernel);
685}
686
687PabloCompiler::~PabloCompiler() {
688    delete mCarryManager;
689}
690
691}
Note: See TracBrowser for help on using the repository browser.