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

Last change on this file since 6129 was 6129, checked in by cameron, 12 months ago

pablo.Infile(0) optimization

File size: 38.1 KB
RevLine 
[3850]1/*
[5043]2 *  Copyright (c) 2014-16 International Characters.
[3850]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
[5267]7#include "pablo_compiler.h"
[5260]8#include <pablo/pablo_kernel.h>
[5031]9#include <pablo/pablo_toolchain.h>
[4237]10#include <pablo/codegenstate.h>
[5267]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>
[5828]24#include <pablo/pe_repeat.h>
25#include <pablo/pe_pack.h>
[5267]26#include <pablo/pe_var.h>
27#include <pablo/ps_assign.h>
[5510]28#ifdef USE_CARRYPACK_MANAGER
29#include <pablo/carrypack_manager.h>
30#else
[4647]31#include <pablo/carry_manager.h>
[5510]32#endif
[5440]33#include <kernels/kernel_builder.h>
[5310]34#include <kernels/streamset.h>
[4274]35#include <llvm/IR/Module.h>
[5837]36#include <llvm/IR/Type.h>
[5270]37#include <llvm/Support/raw_os_ostream.h>
[6055]38#include <llvm/ADT/STLExtras.h> // for make_unique
[4919]39
[5267]40using namespace llvm;
41
[4237]42namespace pablo {
43
[5227]44using TypeId = PabloAST::ClassTypeId;
[4237]45
[5831]46inline static unsigned getAlignment(const Type * const type) {
47    return type->getPrimitiveSizeInBits() / 8;
[5283]48}
49
[5831]50inline static unsigned getAlignment(const Value * const expr) {
51    return getAlignment(expr->getType());
52}
53
[5283]54inline static unsigned getPointerElementAlignment(const Value * const ptr) {
[5831]55    return getAlignment(ptr->getType()->getPointerElementType());
[5283]56}
57
[5828]58void PabloCompiler::initializeKernelData(const std::unique_ptr<kernel::KernelBuilder> & b) {
[5620]59    mBranchCount = 0;
[5836]60    examineBlock(b, mKernel->getEntryScope());
[5828]61    mCarryManager->initializeCarryData(b, mKernel);
[5620]62    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {
63        const auto count = (mBranchCount * 2) + 1;
64        mKernel->addScalar(ArrayType::get(mKernel->getSizeTy(), count), "profile");
65        mBasicBlock.reserve(count);
66    }
[4237]67}
[4659]68
[5828]69void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> & b) {
70    mCarryManager->releaseCarryData(b);
[5486]71}
72
[5828]73void PabloCompiler::clearCarryData(const std::unique_ptr<kernel::KernelBuilder> & b) {
74    mCarryManager->clearCarryData(b);
75}
76
77void PabloCompiler::compile(const std::unique_ptr<kernel::KernelBuilder> & b) {
78    mCarryManager->initializeCodeGen(b);
[5836]79    PabloBlock * const entryBlock = mKernel->getEntryScope(); assert (entryBlock);
[5828]80    mMarker.emplace(entryBlock->createZeroes(), b->allZeroes());
81    mMarker.emplace(entryBlock->createOnes(), b->allOnes());
[5620]82    mBranchCount = 0;
[5828]83    addBranchCounter(b);
84    compileBlock(b, entryBlock);
85    mCarryManager->finalizeCodeGen(b);
[4659]86}
[4665]87
[5828]88void PabloCompiler::examineBlock(const std::unique_ptr<kernel::KernelBuilder> & b, const PabloBlock * const block) {
[5000]89    for (const Statement * stmt : *block) {
90        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
91            const Lookahead * const la = cast<Lookahead>(stmt);
[5646]92            PabloAST * input = la->getExpression();
[5782]93            if (isa<Extract>(input)) {
[5646]94                input = cast<Extract>(input)->getArray();
[5202]95            }
[5646]96            bool notFound = true;
97            if (LLVM_LIKELY(isa<Var>(input))) {
98                for (unsigned i = 0; i < mKernel->getNumOfInputs(); ++i) {
99                    if (input == mKernel->getInput(i)) {
[5782]100                        const auto & binding = mKernel->getStreamInput(i);
101                        if (LLVM_UNLIKELY(!binding.hasLookahead() || binding.getLookahead() < la->getAmount())) {
102                            std::string tmp;
103                            raw_string_ostream out(tmp);
104                            input->print(out);
105                            out << " must have a lookahead attribute of at least " << la->getAmount();
106                            report_fatal_error(out.str());
[5646]107                        }
108                        notFound = false;
109                        break;
110                    }
111                }
112            }
113            if (LLVM_UNLIKELY(notFound)) {
114                report_fatal_error("Lookahead " + stmt->getName() + " can only be performed on an input streamset");
115            }
[5227]116        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
[5620]117            ++mBranchCount;
[5828]118            examineBlock(b, cast<Branch>(stmt)->getBody());
[5283]119        } else if (LLVM_UNLIKELY(isa<Count>(stmt))) {
[5828]120            mAccumulator.insert(std::make_pair(stmt, b->getInt32(mKernel->addUnnamedScalar(stmt->getType()))));
[4237]121        }
[5202]122    }   
[4237]123}
124
[5828]125void PabloCompiler::addBranchCounter(const std::unique_ptr<kernel::KernelBuilder> & b) {
[5620]126    if (CompileOptionIsSet(PabloCompilationFlags::EnableProfiling)) {       
[5828]127        Value * ptr = b->getScalarFieldPtr("profile");
[5620]128        assert (mBasicBlock.size() < ptr->getType()->getPointerElementType()->getArrayNumElements());
[5828]129        ptr = b->CreateGEP(ptr, {b->getInt32(0), b->getInt32(mBasicBlock.size())});
[5620]130        const auto alignment = getPointerElementAlignment(ptr);
[5828]131        Value * value = b->CreateAlignedLoad(ptr, alignment, false, "branchCounter");
132        value = b->CreateAdd(value, ConstantInt::get(cast<IntegerType>(value->getType()), 1));
133        b->CreateAlignedStore(value, ptr, alignment);
134        mBasicBlock.push_back(b->GetInsertBlock());
[5620]135    }
136}
137
[5828]138inline void PabloCompiler::compileBlock(const std::unique_ptr<kernel::KernelBuilder> & b, const PabloBlock * const block) {
[4870]139    for (const Statement * statement : *block) {
[5828]140        compileStatement(b, statement);
[4237]141    }
142}
143
[5828]144void PabloCompiler::compileIf(const std::unique_ptr<kernel::KernelBuilder> & b, const If * const ifStatement) {
[4647]145    //
146    //  The If-ElseZero stmt:
147    //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
148    //  If the value of the predicate is nonzero, then determine the values of variables
149    //  <var>* by executing the given statements.  Otherwise, the value of the
150    //  variables are all zero.  Requirements: (a) no variable that is defined within
151    //  the body of the if may be accessed outside unless it is explicitly
152    //  listed in the variable list, (b) every variable in the defined list receives
153    //  a value within the body, and (c) the logical consequence of executing
154    //  the statements in the event that the predicate is zero is that the
155    //  values of all defined variables indeed work out to be 0.
156    //
157    //  Simple Implementation with Phi nodes:  a phi node in the if exit block
158    //  is inserted for each variable in the defined variable list.  It receives
159    //  a zero value from the ifentry block and the defined value from the if
160    //  body.
161    //
[4665]162
[5828]163    BasicBlock * const ifEntryBlock = b->GetInsertBlock();
[5620]164    ++mBranchCount;
[5828]165    BasicBlock * const ifBodyBlock = b->CreateBasicBlock("if.body_" + std::to_string(mBranchCount));
166    BasicBlock * const ifEndBlock = b->CreateBasicBlock("if.end_" + std::to_string(mBranchCount));
[4541]167   
[5202]168    std::vector<std::pair<const Var *, Value *>> incoming;
169
170    for (const Var * var : ifStatement->getEscaped()) {
[5320]171        if (LLVM_UNLIKELY(var->isKernelParameter())) {
172            Value * marker = nullptr;
173            if (var->isScalar()) {
[5828]174                marker = b->getScalarFieldPtr(var->getName());
[5320]175            } else if (var->isReadOnly()) {
[5828]176                marker = b->getInputStreamBlockPtr(var->getName(), b->getInt32(0));
[5320]177            } else if (var->isReadNone()) {
[5828]178                marker = b->getOutputStreamBlockPtr(var->getName(), b->getInt32(0));
[5320]179            }
180            mMarker[var] = marker;
181        } else {
182            auto f = mMarker.find(var);
183            if (LLVM_UNLIKELY(f == mMarker.end())) {
184                std::string tmp;
185                raw_string_ostream out(tmp);
186                var->print(out);
187                out << " is uninitialized prior to entering ";
188                ifStatement->print(out);
189                report_fatal_error(out.str());
190            }
191            incoming.emplace_back(var, f->second);
[5202]192        }
193    }
194
[5292]195    const PabloBlock * ifBody = ifStatement->getBody();
[4628]196   
[5828]197    mCarryManager->enterIfScope(b, ifBody);
[5227]198
[5828]199    Value * condition = compileExpression(b, ifStatement->getCondition());
200    if (condition->getType() == b->getBitBlockType()) {
201        condition = b->bitblock_any(mCarryManager->generateSummaryTest(b, condition));
[5227]202    }
[4670]203   
[5828]204    b->CreateCondBr(condition, ifBodyBlock, ifEndBlock);
[4838]205   
[4647]206    // Entry processing is complete, now handle the body of the if.
[5828]207    b->SetInsertPoint(ifBodyBlock);
[5227]208
[5828]209    mCarryManager->enterIfBody(b, ifEntryBlock);
[5227]210
[5828]211    addBranchCounter(b);
[5620]212
[5828]213    compileBlock(b, ifBody);
[5202]214
[5828]215    mCarryManager->leaveIfBody(b, b->GetInsertBlock());
[4922]216
[5828]217    BasicBlock * ifExitBlock = b->GetInsertBlock();
[4922]218
[5828]219    b->CreateBr(ifEndBlock);
[5351]220
221    ifEndBlock->moveAfter(ifExitBlock);
222
[4647]223    //End Block
[5828]224    b->SetInsertPoint(ifEndBlock);
[5227]225
[5828]226    mCarryManager->leaveIfScope(b, ifEntryBlock, ifExitBlock);
[5227]227
[5202]228    for (const auto i : incoming) {
[5283]229        const Var * var; Value * incoming;
230        std::tie(var, incoming) = i;
[5202]231
[5283]232        auto f = mMarker.find(var);
233        if (LLVM_UNLIKELY(f == mMarker.end())) {
[5202]234            std::string tmp;
235            raw_string_ostream out(tmp);
[5283]236            out << "PHINode creation error: ";
[5267]237            var->print(out);
[5283]238            out << " was not assigned an outgoing value.";
[5310]239            report_fatal_error(out.str());
[5202]240        }
241
[5283]242        Value * const outgoing = f->second;
243        if (LLVM_UNLIKELY(incoming == outgoing)) {
244            continue;
245        }
[5227]246
[5283]247        if (LLVM_UNLIKELY(incoming->getType() != outgoing->getType())) {
248            std::string tmp;
249            raw_string_ostream out(tmp);
250            out << "PHINode creation error: incoming type of ";
251            var->print(out);
252            out << " (";
253            incoming->getType()->print(out);
254            out << ") differs from the outgoing type (";
255            outgoing->getType()->print(out);
256            out << ") within ";
257            ifStatement->print(out);
[5310]258            report_fatal_error(out.str());
[5283]259        }
[5227]260
[5828]261        PHINode * phi = b->CreatePHI(incoming->getType(), 2, var->getName());
[5283]262        phi->addIncoming(incoming, ifEntryBlock);
263        phi->addIncoming(outgoing, ifExitBlock);
[5160]264        f->second = phi;
[5620]265    }
266
[5828]267    addBranchCounter(b);
[4535]268}
269
[5828]270void PabloCompiler::compileWhile(const std::unique_ptr<kernel::KernelBuilder> & b, const While * const whileStatement) {
[4595]271
[5292]272    const PabloBlock * const whileBody = whileStatement->getBody();
273
[5828]274    BasicBlock * whileEntryBlock = b->GetInsertBlock();
[4640]275
[5227]276    const auto escaped = whileStatement->getEscaped();
277
[5169]278#ifdef ENABLE_BOUNDED_WHILE
279    PHINode * bound_phi = nullptr;  // Needed for bounded while loops.
280#endif
[4647]281    // On entry to the while structure, proceed to execute the first iteration
[5320]282    // of the loop body unconditionally. The while condition is tested at the end of
[4647]283    // the loop.
[4640]284
[5320]285    for (const Var * var : escaped) {
286        if (LLVM_UNLIKELY(var->isKernelParameter())) {
287            Value * marker = nullptr;
288            if (var->isScalar()) {
[5828]289                marker = b->getScalarFieldPtr(var->getName());
[5320]290            } else if (var->isReadOnly()) {
[5828]291                marker = b->getInputStreamBlockPtr(var->getName(), b->getInt32(0));
[5320]292            } else if (var->isReadNone()) {
[5828]293                marker = b->getOutputStreamBlockPtr(var->getName(), b->getInt32(0));
[5320]294            }
295            mMarker[var] = marker;
296        }
297    }
298
[5828]299    mCarryManager->enterLoopScope(b, whileBody);
[5227]300
[5828]301    BasicBlock * whileBodyBlock = b->CreateBasicBlock("while.body_" + std::to_string(mBranchCount));
302    BasicBlock * whileEndBlock = b->CreateBasicBlock("while.end_" + std::to_string(mBranchCount));
[5620]303    ++mBranchCount;
[5353]304
[5828]305    b->CreateBr(whileBodyBlock);
[5227]306
[5828]307    b->SetInsertPoint(whileBodyBlock);
[4640]308
[4647]309    //
310    // There are 3 sets of Phi nodes for the while loop.
311    // (1) Carry-ins: (a) incoming carry data first iterations, (b) zero thereafter
312    // (2) Carry-out accumulators: (a) zero first iteration, (b) |= carry-out of each iteration
313    // (3) Next nodes: (a) values set up before loop, (b) modified values calculated in loop.
[5169]314#ifdef ENABLE_BOUNDED_WHILE
315    // (4) The loop bound, if any.
316#endif
[4640]317
[5202]318    std::vector<std::pair<const Var *, PHINode *>> variants;
319
[4647]320    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
[5227]321    for (const auto var : escaped) {
[5283]322        auto f = mMarker.find(var);
323        if (LLVM_UNLIKELY(f == mMarker.end())) {
[5202]324            std::string tmp;
325            raw_string_ostream out(tmp);
[5283]326            out << "PHINode creation error: ";
[5267]327            var->print(out);
[5217]328            out << " is uninitialized prior to entering ";
[5267]329            whileStatement->print(out);
[5310]330            report_fatal_error(out.str());
[5202]331        }
[5227]332        Value * entryValue = f->second;
[5828]333        PHINode * phi = b->CreatePHI(entryValue->getType(), 2, var->getName());
[5227]334        phi->addIncoming(entryValue, whileEntryBlock);
[5160]335        f->second = phi;
[5283]336        assert(mMarker[var] == phi);
[5202]337        variants.emplace_back(var, phi);
[4647]338    }
[5169]339#ifdef ENABLE_BOUNDED_WHILE
340    if (whileStatement->getBound()) {
[5828]341        bound_phi = b->CreatePHI(b->getSizeTy(), 2, "while_bound");
342        bound_phi->addIncoming(b->getSize(whileStatement->getBound()), whileEntryBlock);
[5169]343    }
344#endif
[5227]345
[5828]346    mCarryManager->enterLoopBody(b, whileEntryBlock);
[5227]347
[5828]348    addBranchCounter(b);
[5620]349
[5828]350    compileBlock(b, whileBody);
[4640]351
[5169]352    // After the whileBody has been compiled, we may be in a different basic block.
[4640]353
[5828]354    mCarryManager->leaveLoopBody(b, b->GetInsertBlock());
[5353]355
356
[5169]357#ifdef ENABLE_BOUNDED_WHILE
358    if (whileStatement->getBound()) {
[5828]359        Value * new_bound = b->CreateSub(bound_phi, b->getSize(1));
[5170]360        bound_phi->addIncoming(new_bound, whileExitBlock);
[5828]361        condition = b->CreateAnd(condition, b->CreateICmpUGT(new_bound, ConstantInt::getNullValue(b->getSizeTy())));
[5169]362    }
[5227]363#endif
[4576]364
[5828]365    BasicBlock * const whileExitBlock = b->GetInsertBlock();
[5361]366
[5202]367    // and for any variant nodes in the loop body
368    for (const auto variant : variants) {
[5283]369        const Var * var; PHINode * incomingPhi;
370        std::tie(var, incomingPhi) = variant;
371        const auto f = mMarker.find(var);
372        if (LLVM_UNLIKELY(f == mMarker.end())) {
[5202]373            std::string tmp;
374            raw_string_ostream out(tmp);
[5283]375            out << "PHINode creation error: ";
[5267]376            var->print(out);
[5283]377            out << " is no longer assigned a value.";
[5310]378            report_fatal_error(out.str());
[4264]379        }
[5283]380
381        Value * const outgoingValue = f->second;
382
383        if (LLVM_UNLIKELY(incomingPhi->getType() != outgoingValue->getType())) {
384            std::string tmp;
385            raw_string_ostream out(tmp);
386            out << "PHINode creation error: incoming type of ";
387            var->print(out);
388            out << " (";
389            incomingPhi->getType()->print(out);
390            out << ") differs from the outgoing type (";
391            outgoingValue->getType()->print(out);
392            out << ") within ";
393            whileStatement->print(out);
[5310]394            report_fatal_error(out.str());
[5283]395        }
396
397        incomingPhi->addIncoming(outgoingValue, whileExitBlock);
[4647]398    }
[4237]399
[5361]400    // Terminate the while loop body with a conditional branch back.
[5828]401    Value * condition = compileExpression(b, whileStatement->getCondition());
402    if (condition->getType() == b->getBitBlockType()) {
403        condition = b->bitblock_any(mCarryManager->generateSummaryTest(b, condition));
[5361]404    }
405
[5828]406    b->CreateCondBr(condition, whileBodyBlock, whileEndBlock);
[5227]407
[5620]408    whileEndBlock->moveAfter(whileExitBlock);
409
[5828]410    b->SetInsertPoint(whileEndBlock);
[4640]411
[5828]412    mCarryManager->leaveLoopScope(b, whileEntryBlock, whileExitBlock);
[5227]413
[5828]414    addBranchCounter(b);
[4535]415}
416
[5828]417void PabloCompiler::compileStatement(const std::unique_ptr<kernel::KernelBuilder> & b, const Statement * const stmt) {
[4674]418
[5202]419    if (LLVM_UNLIKELY(isa<If>(stmt))) {
[5828]420        compileIf(b, cast<If>(stmt));
[5202]421    } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
[5828]422        compileWhile(b, cast<While>(stmt));
[5202]423    } else {
424        const PabloAST * expr = stmt;
425        Value * value = nullptr;
[5828]426        if (isa<And>(stmt)) {
[5834]427            Value * const op0 = compileExpression(b, stmt->getOperand(0));
428            Value * const op1 = compileExpression(b, stmt->getOperand(1));
429            value = b->simd_and(op0, op1);
[5227]430        } else if (isa<Or>(stmt)) {
[5834]431            Value * const op0 = compileExpression(b, stmt->getOperand(0));
432            Value * const op1 = compileExpression(b, stmt->getOperand(1));
433            value = b->simd_or(op0, op1);
[5227]434        } else if (isa<Xor>(stmt)) {
[5834]435            Value * const op0 = compileExpression(b, stmt->getOperand(0));
436            Value * const op1 = compileExpression(b, stmt->getOperand(1));
437            value = b->simd_xor(op0, op1);
[5202]438        } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
[5828]439            Value* ifMask = compileExpression(b, sel->getCondition());
440            Value* ifTrue = b->simd_and(ifMask, compileExpression(b, sel->getTrueExpr()));
441            Value* ifFalse = b->simd_and(b->simd_not(ifMask), compileExpression(b, sel->getFalseExpr()));
442            value = b->simd_or(ifTrue, ifFalse);
[5227]443        } else if (isa<Not>(stmt)) {
[5828]444            value = b->simd_not(compileExpression(b, stmt->getOperand(0)));
[5227]445        } else if (isa<Advance>(stmt)) {
446            const Advance * const adv = cast<Advance>(stmt);
447            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
448            // manager so that it properly selects the correct carry bit.
[5828]449            value = mCarryManager->advanceCarryInCarryOut(b, adv, compileExpression(b, adv->getExpression()));
[5705]450        } else if (isa<IndexedAdvance>(stmt)) {
451            const IndexedAdvance * const adv = cast<IndexedAdvance>(stmt);
[5828]452            Value * strm = compileExpression(b, adv->getExpression());
453            Value * index_strm = compileExpression(b, adv->getIndex());
[5705]454            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
455            // manager so that it properly selects the correct carry bit.
[5828]456            value = mCarryManager->indexedAdvanceCarryInCarryOut(b, adv, strm, index_strm);
[5202]457        } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
[5828]458            Value * const marker = compileExpression(b, mstar->getMarker());
459            Value * const cc = compileExpression(b, mstar->getCharClass());
460            Value * const marker_and_cc = b->simd_and(marker, cc);
461            Value * const sum = mCarryManager->addCarryInCarryOut(b, mstar, marker_and_cc, cc);
462            value = b->simd_or(b->simd_xor(sum, cc), marker);
[5202]463        } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
[5828]464            Value * const from = compileExpression(b, sthru->getScanFrom());
465            Value * const thru = compileExpression(b, sthru->getScanThru());
466            Value * const sum = mCarryManager->addCarryInCarryOut(b, sthru, from, thru);
467            value = b->simd_and(sum, b->simd_not(thru));
[5329]468        } else if (const ScanTo * sthru = dyn_cast<ScanTo>(stmt)) {
[5828]469            Value * const marker_expr = compileExpression(b, sthru->getScanFrom());
470            Value * const to = b->simd_xor(compileExpression(b, sthru->getScanTo()), b->getScalarField("EOFmask"));
471            Value * const sum = mCarryManager->addCarryInCarryOut(b, sthru, marker_expr, b->simd_not(to));
472            value = b->simd_and(sum, to);
[5329]473        } else if (const AdvanceThenScanThru * sthru = dyn_cast<AdvanceThenScanThru>(stmt)) {
[5828]474            Value * const from = compileExpression(b, sthru->getScanFrom());
475            Value * const thru = compileExpression(b, sthru->getScanThru());
476            Value * const sum = mCarryManager->addCarryInCarryOut(b, sthru, from, b->simd_or(from, thru));
477            value = b->simd_and(sum, b->simd_not(thru));
[5329]478        } else if (const AdvanceThenScanTo * sthru = dyn_cast<AdvanceThenScanTo>(stmt)) {
[5828]479            Value * const from = compileExpression(b, sthru->getScanFrom());
480            Value * const to = b->simd_xor(compileExpression(b, sthru->getScanTo()), b->getScalarField("EOFmask"));
481            Value * const sum = mCarryManager->addCarryInCarryOut(b, sthru, from, b->simd_or(from, b->simd_not(to)));
482            value = b->simd_and(sum, to);
483        } else if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
484            expr = cast<Assign>(stmt)->getVariable();
485            value = compileExpression(b, cast<Assign>(stmt)->getValue());
486            if (isa<Extract>(expr) || (isa<Var>(expr) && cast<Var>(expr)->isKernelParameter())) {
487                Value * const ptr = compileExpression(b, expr, false);
488                b->CreateAlignedStore(value, ptr, getAlignment(value));
489                value = ptr;
490            }
[5202]491        } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
[5828]492            Value * EOFmask = b->getScalarField("EOFmask");
493            value = b->simd_and(compileExpression(b, e->getExpr()), b->simd_not(EOFmask));
[5202]494        } else if (const AtEOF * e = dyn_cast<AtEOF>(stmt)) {
[5828]495            Value * EOFbit = b->getScalarField("EOFbit");
496            value = b->simd_and(compileExpression(b, e->getExpr()), EOFbit);
[5202]497        } else if (const Count * c = dyn_cast<Count>(stmt)) {
[5828]498            Value * EOFbit = b->getScalarField("EOFbit");
499            Value * EOFmask = b->getScalarField("EOFmask");
[5832]500            Value * const to_count = b->simd_and(b->simd_or(b->simd_not(EOFmask), EOFbit), compileExpression(b, c->getExpr()));           
[5283]501            const auto f = mAccumulator.find(c);
502            if (LLVM_UNLIKELY(f == mAccumulator.end())) {
[5310]503                report_fatal_error("Unknown accumulator: " + c->getName().str());
[5283]504            }
[5832]505            Value * const ptr = b->getScalarFieldPtr(f->second);
[5320]506            const auto alignment = getPointerElementAlignment(ptr);
[5832]507            Value * const countSoFar = b->CreateAlignedLoad(ptr, alignment, c->getName() + "_accumulator");
508            const auto fieldWidth = b->getSizeTy()->getBitWidth();
[5977]509            Value * bitBlockCount = b->simd_popcount(b->getBitBlockWidth(), to_count);
510            value = b->CreateAdd(b->mvmd_extract(fieldWidth, bitBlockCount, 0), countSoFar, "countSoFar");
[5828]511            b->CreateAlignedStore(value, ptr, alignment);
[5202]512        } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
[5646]513            PabloAST * stream = l->getExpression();
[5647]514            Value * index = nullptr;
[5782]515            if (LLVM_UNLIKELY(isa<Extract>(stream))) {               
[5828]516                index = compileExpression(b, cast<Extract>(stream)->getIndex(), true);
[5647]517                stream = cast<Extract>(stream)->getArray();
518            } else {
[5828]519                index = b->getInt32(0);
[5141]520            }
[5828]521            const auto bit_shift = (l->getAmount() % b->getBitBlockWidth());
522            const auto block_shift = (l->getAmount() / b->getBitBlockWidth());
523            Value * ptr = b->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, b->getSize(block_shift));
524            Value * lookAhead = b->CreateBlockAlignedLoad(ptr);
[5202]525            if (bit_shift == 0) {  // Simple case with no intra-block shifting.
526                value = lookAhead;
527            } else { // Need to form shift result from two adjacent blocks.
[5828]528                Value * ptr = b->getInputStreamBlockPtr(cast<Var>(stream)->getName(), index, b->getSize(block_shift + 1));
529                Value * lookAhead1 = b->CreateBlockAlignedLoad(ptr);
[5202]530                if (LLVM_UNLIKELY((bit_shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
[5828]531                    value = b->mvmd_dslli(8, lookAhead1, lookAhead, (bit_shift / 8));
[5202]532                } else {
[5828]533                    Type  * const streamType = b->getIntNTy(b->getBitBlockWidth());
534                    Value * b1 = b->CreateBitCast(lookAhead1, streamType);
535                    Value * b0 = b->CreateBitCast(lookAhead, streamType);
536                    Value * result = b->CreateOr(b->CreateShl(b1, b->getBitBlockWidth() - bit_shift), b->CreateLShr(b0, bit_shift));
537                    value = b->CreateBitCast(result, b->getBitBlockType());
[5202]538                }
539            }
[5828]540        } else if (const Repeat * const s = dyn_cast<Repeat>(stmt)) {
541            value = compileExpression(b, s->getValue());
542            Type * const ty = s->getType();
543            if (LLVM_LIKELY(ty->isVectorTy())) {
544                const auto fw = s->getFieldWidth()->value();
545                value = b->CreateZExtOrTrunc(value, b->getIntNTy(fw));
546                value = b->simd_fill(fw, value);
547            } else {
548                value = b->CreateZExtOrTrunc(value, ty);
549            }
550        } else if (const PackH * const p = dyn_cast<PackH>(stmt)) {
551            const auto sourceWidth = p->getValue()->getType()->getVectorElementType()->getIntegerBitWidth();
[5837]552            const auto packWidth = p->getFieldWidth()->value();
553            assert (sourceWidth == packWidth);
[5828]554            Value * const base = compileExpression(b, p->getValue(), false);
[5837]555            const auto result_packs = sourceWidth/2;
556            if (LLVM_LIKELY(result_packs > 1)) {
557                value = b->CreateAlloca(ArrayType::get(b->getBitBlockType(), result_packs));
[5828]558            }
559            Constant * const ZERO = b->getInt32(0);
[5837]560            for (unsigned i = 0; i < result_packs; ++i) {
[5828]561                Value * A = b->CreateLoad(b->CreateGEP(base, {ZERO, b->getInt32(i * 2)}));
562                Value * B = b->CreateLoad(b->CreateGEP(base, {ZERO, b->getInt32(i * 2 + 1)}));
[5837]563                Value * P = b->bitCast(b->hsimd_packh(packWidth, A, B));
564                if (LLVM_UNLIKELY(result_packs == 1)) {
[5828]565                    value = P;
566                    break;
567                }
[5837]568                b->CreateStore(P, b->CreateGEP(value, {ZERO, b->getInt32(i)}));
[5828]569            }
570        } else if (const PackL * const p = dyn_cast<PackL>(stmt)) {
571            const auto sourceWidth = p->getValue()->getType()->getVectorElementType()->getIntegerBitWidth();
[5837]572            const auto packWidth = p->getFieldWidth()->value();
573            assert (sourceWidth == packWidth);
[5828]574            Value * const base = compileExpression(b, p->getValue(), false);
[5837]575            const auto result_packs = sourceWidth/2;
576            if (LLVM_LIKELY(result_packs > 1)) {
577                value = b->CreateAlloca(ArrayType::get(b->getBitBlockType(), result_packs));
[5828]578            }
579            Constant * const ZERO = b->getInt32(0);
[5837]580            for (unsigned i = 0; i < result_packs; ++i) {
[5828]581                Value * A = b->CreateLoad(b->CreateGEP(base, {ZERO, b->getInt32(i * 2)}));
582                Value * B = b->CreateLoad(b->CreateGEP(base, {ZERO, b->getInt32(i * 2 + 1)}));
[5837]583                Value * P = b->bitCast(b->hsimd_packl(packWidth, A, B));
584                if (LLVM_UNLIKELY(result_packs == 1)) {
[5828]585                    value = P;
586                    break;
587                }
[5837]588                b->CreateStore(P, b->CreateGEP(value, {ZERO, b->getInt32(i)}));
[5828]589            }
[5202]590        } else {
591            std::string tmp;
[5310]592            raw_string_ostream out(tmp);
[5371]593            out << "PabloCompiler: ";
[5267]594            stmt->print(out);
[5320]595            out << " was not recognized by the compiler";
596            report_fatal_error(out.str());
[5141]597        }
[5828]598        assert (expr);
599        assert (value);
[5283]600        mMarker[expr] = value;
[5202]601        if (DebugOptionIsSet(DumpTrace)) {
[5828]602            std::string tmp;
603            raw_string_ostream name(tmp);
604            expr->print(name);
[5317]605            if (value->getType()->isVectorTy()) {
[5828]606                b->CallPrintRegister(name.str(), value);
[5317]607            } else if (value->getType()->isIntegerTy()) {
[5828]608                b->CallPrintInt(name.str(), value);
[5245]609            }
[5202]610        }
[4720]611    }
[4410]612}
613
[5828]614unsigned getIntegerBitWidth(const Type * ty) {
615    if (ty->isArrayTy()) {
616        assert (ty->getArrayNumElements() == 1);
617        ty = ty->getArrayElementType();
618    }
619    if (ty->isVectorTy()) {
620        assert (ty->getVectorNumElements() == 0);
621        ty = ty->getVectorElementType();
622    }
623    return ty->getIntegerBitWidth();
624}
625
626Value * PabloCompiler::compileExpression(const std::unique_ptr<kernel::KernelBuilder> & b, const PabloAST * const expr, const bool ensureLoaded) {
627    const auto f = mMarker.find(expr);   
628    Value * value = nullptr;
629    if (LLVM_LIKELY(f != mMarker.end())) {
630        value = f->second;
631    } else {
632        if (isa<Integer>(expr)) {
633            value = ConstantInt::get(cast<Integer>(expr)->getType(), cast<Integer>(expr)->value());
634        } else if (isa<Zeroes>(expr)) {
635            value = b->allZeroes();
636        } else if (LLVM_UNLIKELY(isa<Ones>(expr))) {
637            value = b->allOnes();
638        } else if (isa<Extract>(expr)) {
639            const Extract * const extract = cast<Extract>(expr);
640            const Var * const var = cast<Var>(extract->getArray());
641            Value * const index = compileExpression(b, extract->getIndex());
642            value = getPointerToVar(b, var, index);
643        } else if (LLVM_UNLIKELY(isa<Var>(expr))) {
644            const Var * const var = cast<Var>(expr);
645            if (LLVM_LIKELY(var->isKernelParameter() && var->isScalar())) {
646                value = b->getScalarFieldPtr(var->getName());
647            } else { // use before def error
648                std::string tmp;
649                raw_string_ostream out(tmp);
650                out << "PabloCompiler: ";
651                expr->print(out);
652                out << " is not a scalar value or was used before definition";
653                report_fatal_error(out.str());
654            }
655        } else if (LLVM_UNLIKELY(isa<Operator>(expr))) {
656            const Operator * const op = cast<Operator>(expr);
657            const PabloAST * lh = op->getLH();
658            const PabloAST * rh = op->getRH();
659            if ((isa<Var>(lh) || isa<Extract>(lh)) || (isa<Var>(rh) || isa<Extract>(rh))) {
[6129]660                if (getIntegerBitWidth(lh->getType()) != getIntegerBitWidth(rh->getType())) {
661                    llvm::report_fatal_error("Integer types must be identical!");
662                }
663                const unsigned intWidth = std::min(getIntegerBitWidth(lh->getType()), getIntegerBitWidth(rh->getType()));
664                const unsigned maskWidth = b->getBitBlockWidth() / intWidth;
665                IntegerType * const maskTy = b->getIntNTy(maskWidth);
666                VectorType * const vTy = VectorType::get(b->getIntNTy(intWidth), maskWidth);
[5828]667
668                Value * baseLhv = nullptr;
669                Value * lhvStreamIndex = nullptr;
670                if (isa<Var>(lh)) {
671                    lhvStreamIndex = b->getInt32(0);
672                } else if (isa<Extract>(lh)) {
673                    lhvStreamIndex = compileExpression(b, cast<Extract>(lh)->getIndex());
[5855]674                    lh = cast<Extract>(lh)->getArray();
[5828]675                } else {
[5831]676                    baseLhv = compileExpression(b, lh);
[5828]677                }
678
679                Value * baseRhv = nullptr;
680                Value * rhvStreamIndex = nullptr;
681                if (isa<Var>(rh)) {
682                    rhvStreamIndex = b->getInt32(0);
[5847]683                } else if (isa<Extract>(rh)) {
[5828]684                    rhvStreamIndex = compileExpression(b, cast<Extract>(rh)->getIndex());
[5855]685                    rh = cast<Extract>(rh)->getArray();
[5828]686                } else {
[5831]687                    baseRhv = compileExpression(b, rh);
[5828]688                }
689
690                const TypeId typeId = op->getClassTypeId();
691
692                if (LLVM_UNLIKELY(typeId == TypeId::Add || typeId == TypeId::Subtract)) {
693
[6129]694                    value = b->CreateAlloca(vTy, b->getInt32(intWidth));
[5828]695
[6129]696                    for (unsigned i = 0; i < intWidth; ++i) {
[5828]697                        llvm::Constant * const index = b->getInt32(i);
698                        Value * lhv = nullptr;
699                        if (baseLhv) {
700                            lhv = baseLhv;
701                        } else {
702                            lhv = getPointerToVar(b, cast<Var>(lh), lhvStreamIndex, index);
[5831]703                            lhv = b->CreateBlockAlignedLoad(lhv);
[5828]704                        }
705                        lhv = b->CreateBitCast(lhv, vTy);
706
707                        Value * rhv = nullptr;
708                        if (baseRhv) {
709                            rhv = baseRhv;
710                        } else {
711                            rhv = getPointerToVar(b, cast<Var>(rh), rhvStreamIndex, index);
[5831]712                            rhv = b->CreateBlockAlignedLoad(rhv);
[5828]713                        }
714                        rhv = b->CreateBitCast(rhv, vTy);
715
716                        Value * result = nullptr;
717                        if (typeId == TypeId::Add) {
718                            result = b->CreateAdd(lhv, rhv);
[5831]719                        } else { // if (typeId == TypeId::Subtract) {
[5828]720                            result = b->CreateSub(lhv, rhv);
721                        }
722                        b->CreateAlignedStore(result, b->CreateGEP(value, {b->getInt32(0), b->getInt32(i)}), getAlignment(result));
723                    }
724
725                } else {
726
[6129]727                    value = UndefValue::get(VectorType::get(maskTy, intWidth));
[5828]728
[6129]729                    for (unsigned i = 0; i < intWidth; ++i) {
[5828]730                        llvm::Constant * const index = b->getInt32(i);
731                        Value * lhv = nullptr;
732                        if (baseLhv) {
733                            lhv = baseLhv;
734                        } else {
735                            lhv = getPointerToVar(b, cast<Var>(lh), lhvStreamIndex, index);
[5831]736                            lhv = b->CreateBlockAlignedLoad(lhv);
[5828]737                        }
738                        lhv = b->CreateBitCast(lhv, vTy);
739
740                        Value * rhv = nullptr;
741                        if (baseRhv) {
742                            rhv = baseRhv;
743                        } else {
744                            rhv = getPointerToVar(b, cast<Var>(rh), rhvStreamIndex, index);
[5831]745                            rhv = b->CreateBlockAlignedLoad(rhv);
[5828]746                        }
747                        rhv = b->CreateBitCast(rhv, vTy);
748                        Value * comp = nullptr;
749                        switch (typeId) {
750                            case TypeId::GreaterThanEquals:
751                            case TypeId::LessThan:
[6129]752                                comp = b->simd_ult(intWidth, lhv, rhv);
[5828]753                                break;
754                            case TypeId::Equals:
755                            case TypeId::NotEquals:
[6129]756                                comp = b->simd_eq(intWidth, lhv, rhv);
[5828]757                                break;
758                            case TypeId::LessThanEquals:
759                            case TypeId::GreaterThan:
[6129]760                                comp = b->simd_ugt(intWidth, lhv, rhv);
[5828]761                                break;
762                            default: llvm_unreachable("invalid vector operator id");
763                        }
[6129]764                        Value * const mask = b->CreateZExtOrTrunc(b->hsimd_signmask(intWidth, comp), maskTy);
765                        value = b->mvmd_insert(maskWidth, value, mask, i);
[5828]766                    }
767                    value = b->CreateBitCast(value, b->getBitBlockType());
768                    switch (typeId) {
769                        case TypeId::GreaterThanEquals:
770                        case TypeId::LessThanEquals:
771                        case TypeId::NotEquals:
[6129]772                            value = b->CreateNot(value);
[5828]773                        default: break;
774                    }
775                }
776
777            } else {
778                Value * const lhv = compileExpression(b, lh);
779                Value * const rhv = compileExpression(b, rh);
780                switch (op->getClassTypeId()) {
781                    case TypeId::Add:
782                        value = b->CreateAdd(lhv, rhv); break;
783                    case TypeId::Subtract:
784                        value = b->CreateSub(lhv, rhv); break;
785                    case TypeId::LessThan:
[6129]786                        value = b->CreateICmpULT(lhv, rhv); break;
[5828]787                    case TypeId::LessThanEquals:
[6129]788                        value = b->CreateICmpULE(lhv, rhv); break;
[5828]789                    case TypeId::Equals:
790                        value = b->CreateICmpEQ(lhv, rhv); break;
791                    case TypeId::GreaterThanEquals:
[6129]792                        value = b->CreateICmpUGE(lhv, rhv); break;
[5828]793                    case TypeId::GreaterThan:
[6129]794                        value = b->CreateICmpUGT(lhv, rhv); break;
[5828]795                    case TypeId::NotEquals:
796                        value = b->CreateICmpNE(lhv, rhv); break;
797                    default: llvm_unreachable("invalid scalar operator id");
798                }
799            }
800        } else { // use before def error
[5283]801            std::string tmp;
802            raw_string_ostream out(tmp);
[5828]803            out << "PabloCompiler: ";
[5283]804            expr->print(out);
[5828]805            out << " was used before definition";
[5310]806            report_fatal_error(out.str());
[5283]807        }
[5828]808        assert (value);
809        // mMarker.insert({expr, value});
[4410]810    }
[5828]811    if (LLVM_UNLIKELY(value->getType()->isPointerTy() && ensureLoaded)) {
812        value = b->CreateAlignedLoad(value, getPointerElementAlignment(value));
[4359]813    }
[5202]814    return value;
[4237]815}
[4268]816
[5828]817Value * PabloCompiler::getPointerToVar(const std::unique_ptr<kernel::KernelBuilder> & b, const Var * var, Value * index1, Value * index2)  {
[5855]818    assert (var && index1);
[5828]819    if (LLVM_LIKELY(var->isKernelParameter())) {
820        if (LLVM_UNLIKELY(var->isScalar())) {
821            std::string tmp;
822            raw_string_ostream out(tmp);
823            out << mKernel->getName();
824            out << ": cannot index scalar value ";
825            var->print(out);
826            report_fatal_error(out.str());
827        } else if (var->isReadOnly()) {
828            if (index2) {
829                return b->getInputStreamPackPtr(var->getName(), index1, index2);
830            } else {
831                return b->getInputStreamBlockPtr(var->getName(), index1);
832            }
833        } else if (var->isReadNone()) {
834            if (index2) {
835                return b->getOutputStreamPackPtr(var->getName(), index1, index2);
836            } else {
837                return b->getOutputStreamBlockPtr(var->getName(), index1);
838            }
839        } else {
840            std::string tmp;
841            raw_string_ostream out(tmp);
842            out << mKernel->getName();
843            out << ": stream ";
844            var->print(out);
845            out << " cannot be read from or written to";
846            report_fatal_error(out.str());
847        }
848    } else {
849        Value * const ptr = compileExpression(b, var, false);
850        std::vector<Value *> offsets;
851        offsets.push_back(ConstantInt::getNullValue(index1->getType()));
852        offsets.push_back(index1);
853        if (index2) offsets.push_back(index2);
854        return b->CreateGEP(ptr, offsets);
855    }
856}
857
[5431]858PabloCompiler::PabloCompiler(PabloKernel * const kernel)
[5435]859: mKernel(kernel)
[5992]860, mCarryManager(make_unique<CarryManager>())
[5620]861, mBranchCount(0) {
[5431]862    assert ("PabloKernel cannot be null!" && kernel);
[4268]863}
[5227]864
865PabloCompiler::~PabloCompiler() {
866}
867
868}
Note: See TracBrowser for help on using the repository browser.