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

Last change on this file since 5837 was 5837, checked in by cameron, 18 months ago

Pablo packh/packl and transposition with -enable-pablo-s2p

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