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

Last change on this file since 5035 was 5035, checked in by cameron, 3 years ago

Add EOFmask internal state value to generated Pablo functions; implement pablo.inFile

File size: 20.1 KB
Line 
1/*
2 *  Copyright (c) 2014-15 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/pablo_compiler.h>
8#include <pablo/pablo_toolchain.h>
9#include <pablo/codegenstate.h>
10#include <pablo/carry_data.h>
11#include <pablo/carry_manager.h>
12#include <pablo/printer_pablos.h>
13#include <pablo/function.h>
14#include <re/re_name.h>
15#include <stdexcept>
16#include <sstream>
17#include <IDISA/idisa_builder.h>
18#include <IDISA/idisa_avx_builder.h>
19#include <llvm/Pass.h>
20#include <llvm/PassManager.h>
21#include <llvm/ADT/SmallVector.h>
22#include <llvm/Analysis/Passes.h>
23#include <llvm/IR/BasicBlock.h>
24#include <llvm/IR/CallingConv.h>
25#include <llvm/IR/DataLayout.h>
26#include <llvm/IR/DerivedTypes.h>
27#include <llvm/IR/Function.h>
28#include <llvm/IR/GlobalVariable.h>
29#include <llvm/IR/InlineAsm.h>
30#include <llvm/IR/Instructions.h>
31#include <llvm/IR/LLVMContext.h>
32#include <llvm/IR/Module.h>
33#include <llvm/Support/FormattedStream.h>
34#include <llvm/Support/MathExtras.h>
35#include <llvm/Support/Casting.h>
36#include <llvm/Support/Compiler.h>
37#include <llvm/Support/Debug.h>
38#include <llvm/Support/TargetSelect.h>
39#include <llvm/Support/Host.h>
40#include <llvm/Transforms/Scalar.h>
41#include <llvm/IRReader/IRReader.h>
42#include <llvm/Bitcode/ReaderWriter.h>
43#include <llvm/Support/MemoryBuffer.h>
44#include <llvm/IR/IRBuilder.h>
45#include <llvm/Support/CommandLine.h>
46#include <llvm/ADT/Twine.h>
47#include <iostream>
48#include <llvm/Support/raw_ostream.h>
49#include <llvm/Support/FileSystem.h>
50#ifndef NDEBUG
51#include <llvm/IR/Verifier.h>
52#endif
53#include <hrtime.h>
54
55
56namespace pablo {
57
58#define DSSLI_FIELDWIDTH 64
59
60PabloCompiler::PabloCompiler(Module * m, IDISA::IDISA_Builder * b)
61: mMod(m)
62, iBuilder(b)
63, mBitBlockType(b->getBitBlockType())
64, mCarryManager(nullptr)
65, mPabloFunction(nullptr)
66, mPabloBlock(nullptr)
67, mKernelBuilder(nullptr)
68, mWhileDepth(0)
69, mIfDepth(0)
70, mFunction(nullptr)
71, mMaxWhileDepth(0) {
72   
73}
74
75void PabloCompiler::setKernel(kernel::KernelBuilder * kBuilder){
76    mKernelBuilder = kBuilder;
77} 
78
79llvm::Function * PabloCompiler::compile(PabloFunction * function) {
80
81    #ifdef PRINT_TIMING_INFORMATION
82    const timestamp_t pablo_compilation_start = read_cycle_counter();
83    #endif
84 
85    Examine(function);
86
87    mCarryManager = new CarryManager(iBuilder);
88
89    GenerateKernel(function);
90       
91    delete mCarryManager;
92    mCarryManager = nullptr;
93   
94    #ifdef PRINT_TIMING_INFORMATION
95    const timestamp_t pablo_compilation_end = read_cycle_counter();
96    std::cerr << "PABLO COMPILATION TIME: " << (pablo_compilation_end - pablo_compilation_start) << std::endl;
97    #endif
98
99    return mFunction;
100}
101
102inline void PabloCompiler::GenerateKernel(PabloFunction * const function) {
103 
104    mPabloFunction = function;
105
106    for (unsigned i = 0; i < function->getNumOfParameters(); ++i) {
107        mKernelBuilder->addInputStream(1, function->getParameter(i)->getName()->to_string());
108    }
109    for (unsigned i = 0; i < function->getNumOfResults(); ++i) {
110        mKernelBuilder->addOutputStream(1);
111    }
112
113    mCarryManager->initialize(function, mKernelBuilder);
114   
115    mKernelBuilder->addInternalState(mBitBlockType, "EOFmask");
116   
117    mFunction = mKernelBuilder->prepareFunction({mInputStreamOffset.begin(), mInputStreamOffset.end()});
118
119    mCarryManager->reset();
120
121    for (unsigned j = 0; j < function->getNumOfParameters(); ++j) {
122        Value * inputVal = mKernelBuilder->getInputStream(j);
123        const Var * const var = function->getParameter(j);
124        if (DebugOptionIsSet(DumpTrace)) {
125            iBuilder->CallPrintRegister(var->getName()->to_string(), iBuilder->CreateBlockAlignedLoad(inputVal));
126        }
127        mMarkerMap.insert(std::make_pair(var, inputVal));
128    }
129
130    compileBlock(function->getEntryBlock());
131
132    for (unsigned j = 0; j < function->getNumOfResults(); ++j) {
133        const auto f = mMarkerMap.find(function->getResult(j));
134        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
135            throw std::runtime_error("PabloCompiler: result " + std::to_string(j) + " was not assigned a value!");
136        }
137        iBuilder->CreateBlockAlignedStore(f->second, mKernelBuilder->getOutputStream(j));
138    }
139
140    mKernelBuilder->finalize();
141}
142
143inline void PabloCompiler::Examine(const PabloFunction * const function) {
144    mWhileDepth = 0;
145    mIfDepth = 0;
146    mMaxWhileDepth = 0;
147    LookaheadOffsetMap offsetMap;
148    Examine(function->getEntryBlock(), offsetMap);
149    mInputStreamOffset.clear();
150    for (const auto & oi : offsetMap) {
151        for (const auto offset : oi.second) {
152            mInputStreamOffset.insert(offset / iBuilder->getBitBlockWidth());
153        }
154    }
155}
156
157void PabloCompiler::Examine(const PabloBlock * const block, LookaheadOffsetMap & offsetMap) {
158    for (const Statement * stmt : *block) {
159         boost::container::flat_set<unsigned> offsets;
160        if (LLVM_UNLIKELY(isa<Lookahead>(stmt))) {
161            const Lookahead * const la = cast<Lookahead>(stmt);
162            assert (isa<Var>(la->getExpr()));
163            offsets.insert(la->getAmount());
164            offsets.insert(la->getAmount() + iBuilder->getBitBlockWidth() - 1);
165        } else {
166            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
167                const PabloAST * expr = stmt->getOperand(i);
168                if (isa<Var>(expr)) {
169                    offsets.insert(0);
170                } else if (LLVM_LIKELY(isa<Statement>(expr) && !isa<Assign>(expr) && !isa<Next>(expr))) {
171                    const auto f = offsetMap.find(expr);
172                    assert (f != offsetMap.end());
173                    const auto & o = f->second;
174                    offsets.insert(o.begin(), o.end());
175                }
176            }
177            if (LLVM_UNLIKELY(isa<If>(stmt))) {
178                Examine(cast<If>(stmt)->getBody(), offsetMap);
179            } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
180                mMaxWhileDepth = std::max(mMaxWhileDepth, ++mWhileDepth);
181                Examine(cast<While>(stmt)->getBody(), offsetMap);
182                --mWhileDepth;
183            }
184        }
185        offsetMap.emplace(stmt, offsets);
186    }
187}
188
189void PabloCompiler::compileBlock(const PabloBlock * const block) {
190    mPabloBlock = block;
191    for (const Statement * statement : *block) {
192        compileStatement(statement);
193    }
194    mPabloBlock = block->getParent();
195}
196
197void PabloCompiler::compileIf(const If * ifStatement) {       
198    //
199    //  The If-ElseZero stmt:
200    //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
201    //  If the value of the predicate is nonzero, then determine the values of variables
202    //  <var>* by executing the given statements.  Otherwise, the value of the
203    //  variables are all zero.  Requirements: (a) no variable that is defined within
204    //  the body of the if may be accessed outside unless it is explicitly
205    //  listed in the variable list, (b) every variable in the defined list receives
206    //  a value within the body, and (c) the logical consequence of executing
207    //  the statements in the event that the predicate is zero is that the
208    //  values of all defined variables indeed work out to be 0.
209    //
210    //  Simple Implementation with Phi nodes:  a phi node in the if exit block
211    //  is inserted for each variable in the defined variable list.  It receives
212    //  a zero value from the ifentry block and the defined value from the if
213    //  body.
214    //
215
216    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
217    BasicBlock * const ifBodyBlock = BasicBlock::Create(mMod->getContext(), "if.body", mFunction, 0);
218    BasicBlock * const ifEndBlock = BasicBlock::Create(mMod->getContext(), "if.end", mFunction, 0);
219   
220    PabloBlock * ifBody = ifStatement->getBody();
221   
222    Value * const condition = compileExpression(ifStatement->getCondition());
223   
224    mCarryManager->enterScope(ifBody);
225    iBuilder->CreateCondBr(mCarryManager->generateSummaryTest(condition), ifBodyBlock, ifEndBlock);
226   
227    // Entry processing is complete, now handle the body of the if.
228    iBuilder->SetInsertPoint(ifBodyBlock);
229   
230    compileBlock(ifBody);
231    BasicBlock * ifExitBlock = iBuilder->GetInsertBlock();
232
233    if (mCarryManager->hasCarries()) {
234        mCarryManager->storeCarryOutSummary();
235    }
236    mCarryManager->addOuterSummaryToNestedSummary();
237
238    iBuilder->CreateBr(ifEndBlock);
239    //End Block
240    iBuilder->SetInsertPoint(ifEndBlock);
241    for (const PabloAST * node : ifStatement->getDefined()) {
242        const Assign * assign = cast<Assign>(node);
243        PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, assign->getName()->value());
244        auto f = mMarkerMap.find(assign);
245        assert (f != mMarkerMap.end());
246        phi->addIncoming(iBuilder->allZeroes(), ifEntryBlock);
247        phi->addIncoming(f->second, ifExitBlock);
248        mMarkerMap[assign] = phi;
249    }
250    // Create the phi Node for the summary variable, if needed.
251    mCarryManager->buildCarryDataPhisAfterIfBody(ifEntryBlock, ifExitBlock);
252    mCarryManager->leaveScope();
253}
254
255void PabloCompiler::compileWhile(const While * whileStatement) {
256
257    PabloBlock * const whileBody = whileStatement->getBody();
258   
259    BasicBlock * whileEntryBlock = iBuilder->GetInsertBlock();
260    BasicBlock * whileBodyBlock = BasicBlock::Create(mMod->getContext(), "while.body", mFunction, 0);
261    BasicBlock * whileEndBlock = BasicBlock::Create(mMod->getContext(), "while.end", mFunction, 0);
262
263    mCarryManager->enterScope(whileBody);
264    mCarryManager->ensureCarriesLoadedRecursive();
265
266    const auto & nextNodes = whileStatement->getVariants();
267    std::vector<PHINode *> nextPhis;
268    nextPhis.reserve(nextNodes.size());
269
270    // On entry to the while structure, proceed to execute the first iteration
271    // of the loop body unconditionally.   The while condition is tested at the end of
272    // the loop.
273
274    iBuilder->CreateBr(whileBodyBlock);
275    iBuilder->SetInsertPoint(whileBodyBlock);
276
277    //
278    // There are 3 sets of Phi nodes for the while loop.
279    // (1) Carry-ins: (a) incoming carry data first iterations, (b) zero thereafter
280    // (2) Carry-out accumulators: (a) zero first iteration, (b) |= carry-out of each iteration
281    // (3) Next nodes: (a) values set up before loop, (b) modified values calculated in loop.
282
283    mCarryManager->initializeWhileEntryCarryDataPhis(whileEntryBlock);
284
285    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
286    for (const Next * n : nextNodes) {
287        PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, n->getName()->value());
288        auto f = mMarkerMap.find(n->getInitial());
289        assert (f != mMarkerMap.end());
290        phi->addIncoming(f->second, whileEntryBlock);
291        mMarkerMap[n->getInitial()] = phi;
292        nextPhis.push_back(phi);
293    }
294
295    //
296    // Now compile the loop body proper.  Carry-out accumulated values
297    // and iterated values of Next nodes will be computed.
298    ++mWhileDepth;
299    compileBlock(whileBody);
300
301    BasicBlock * whileExitBlock = iBuilder->GetInsertBlock();
302
303    if (mCarryManager->hasCarries()) {
304        mCarryManager->storeCarryOutSummary();
305    }
306    mCarryManager->finalizeWhileBlockCarryDataPhis(whileExitBlock);
307
308    // Terminate the while loop body with a conditional branch back.
309    iBuilder->CreateCondBr(iBuilder->bitblock_any(compileExpression(whileStatement->getCondition())), whileBodyBlock, whileEndBlock);
310
311    // and for any Next nodes in the loop body
312    for (unsigned i = 0; i < nextNodes.size(); i++) {
313        const Next * n = nextNodes[i];
314        auto f = mMarkerMap.find(n->getExpr());
315        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
316            throw std::runtime_error("Next node expression was not compiled!");
317        }
318        nextPhis[i]->addIncoming(f->second, whileExitBlock);
319    }
320
321    iBuilder->SetInsertPoint(whileEndBlock);
322    --mWhileDepth;
323
324    mCarryManager->ensureCarriesStoredRecursive();
325    mCarryManager->leaveScope();
326}
327
328
329void PabloCompiler::compileStatement(const Statement * stmt) {
330    Value * expr = nullptr;
331    if (const Assign * assign = dyn_cast<const Assign>(stmt)) {
332        expr = compileExpression(assign->getExpression());
333    } else if (const Next * next = dyn_cast<const Next>(stmt)) {
334        expr = compileExpression(next->getExpr());
335    } else if (const If * ifStatement = dyn_cast<const If>(stmt)) {
336        compileIf(ifStatement);
337        return;
338    } else if (const While * whileStatement = dyn_cast<const While>(stmt)) {
339        compileWhile(whileStatement);
340        return;
341//    } else if (const Call* call = dyn_cast<Call>(stmt)) {
342//        // Call the callee once and store the result in the marker map.
343//        if (LLVM_UNLIKELY(mMarkerMap.count(call) == 0)) {
344//            return;
345//        }
346
347//        const Prototype * proto = call->getPrototype();
348//        const String * callee = proto->getName();
349
350//        Type * inputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfParameters(), mBitBlockType});
351//        Type * outputType = StructType::get(mMod->getContext(), std::vector<Type *>{proto->getNumOfResults(), mBitBlockType});
352//        FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), std::vector<Type *>{PointerType::get(inputType, 0), PointerType::get(outputType, 0)}, false);
353
354//        //Starts on process_block
355//        SmallVector<AttributeSet, 3> Attrs;
356//        Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, std::vector<Attribute::AttrKind>({ Attribute::ReadOnly, Attribute::NoCapture })));
357//        Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, std::vector<Attribute::AttrKind>({ Attribute::ReadNone, Attribute::NoCapture })));
358//        AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
359
360//        Function * externalFunction = cast<Function>(mMod->getOrInsertFunction(callee->value(), functionType, AttrSet));
361//        if (LLVM_UNLIKELY(externalFunction == nullptr)) {
362//            throw std::runtime_error("Could not create static method call for external function \"" + callee->to_string() + "\"");
363//        }
364//        externalFunction->setCallingConv(llvm::CallingConv::C);
365
366//        AllocaInst * outputStruct = iBuilder->CreateAlloca(outputType);
367//        iBuilder->CreateCall2(externalFunction, mInputAddressPtr, outputStruct);
368//        Value * outputPtr = iBuilder->CreateGEP(outputStruct, std::vector<Value *>({ iBuilder->getInt32(0), iBuilder->getInt32(0) }));
369
370//        expr = iBuilder->CreateBlockAlignedLoad(outputPtr);
371    } else if (const And * pablo_and = dyn_cast<And>(stmt)) {
372        expr = iBuilder->simd_and(compileExpression(pablo_and->getOperand(0)), compileExpression(pablo_and->getOperand(1)));
373    } else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
374        expr = iBuilder->simd_or(compileExpression(pablo_or->getOperand(0)), compileExpression(pablo_or->getOperand(1)));
375    } else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
376        expr = iBuilder->simd_xor(compileExpression(pablo_xor->getOperand(0)), compileExpression(pablo_xor->getOperand(1)));
377    } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
378        Value* ifMask = compileExpression(sel->getCondition());
379        Value* ifTrue = iBuilder->simd_and(ifMask, compileExpression(sel->getTrueExpr()));
380        Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(sel->getFalseExpr()));
381        expr = iBuilder->simd_or(ifTrue, ifFalse);
382    } else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
383        expr = iBuilder->simd_not(compileExpression(pablo_not->getExpr()));
384    } else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
385        Value * const strm_value = compileExpression(adv->getExpr());
386        expr = mCarryManager->advanceCarryInCarryOut(adv->getLocalIndex(), adv->getAmount(), strm_value);
387    } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
388        Value * const marker = compileExpression(mstar->getMarker());
389        Value * const cc = compileExpression(mstar->getCharClass());
390        Value * const marker_and_cc = iBuilder->simd_and(marker, cc);
391        Value * const sum = mCarryManager->addCarryInCarryOut(mstar->getLocalCarryIndex(), marker_and_cc, cc);
392        expr = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
393    } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
394        Value * const  marker_expr = compileExpression(sthru->getScanFrom());
395        Value * const  cc_expr = compileExpression(sthru->getScanThru());
396        Value * const  sum = mCarryManager->addCarryInCarryOut(sthru->getLocalCarryIndex(), marker_expr, cc_expr);
397        expr = iBuilder->simd_and(sum, iBuilder->simd_not(cc_expr));
398    } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
399        // Currently InFile(x) => x;  a no-op
400        Value * EOFmask = iBuilder->CreateLoad(mKernelBuilder->getInternalState("EOFmask"));
401        expr = iBuilder->simd_and(compileExpression(e->getExpr()), iBuilder->simd_not(EOFmask));
402    } else if (const Count * c = dyn_cast<Count>(stmt)) {
403        Value * const to_count = compileExpression(c->getExpr());
404        expr = mCarryManager->popCount(to_count, c->getGlobalCountIndex());
405    } else if (const Lookahead * l = dyn_cast<Lookahead>(stmt)) {
406        PabloAST * const var = l->getExpr();
407        if (LLVM_UNLIKELY(!isa<Var>(var))) {
408            throw std::runtime_error("Lookahead input type must be a Var object");
409        }
410        unsigned index = 0;
411        for (; index < mPabloFunction->getNumOfParameters(); ++index) {
412            if (mPabloFunction->getParameter(index) == var) {
413                break;
414            }
415        }
416        if (LLVM_UNLIKELY(index >= mPabloFunction->getNumOfParameters())) {
417            throw std::runtime_error("Lookahead has an illegal Var operand");
418        }
419        const unsigned offset0 = (l->getAmount() / iBuilder->getBitBlockWidth());
420        const unsigned offset1 = ((l->getAmount() + iBuilder->getBitBlockWidth() - 1) / iBuilder->getBitBlockWidth());
421        const unsigned shift = (l->getAmount() % iBuilder->getBitBlockWidth());
422        Value * const v0 = iBuilder->CreateBlockAlignedLoad(mKernelBuilder->getInputStream(index, offset0));
423        Value * const v1 = iBuilder->CreateBlockAlignedLoad(mKernelBuilder->getInputStream(index, offset1));
424        if (LLVM_UNLIKELY((shift % 8) == 0)) { // Use a single whole-byte shift, if possible.
425            expr = iBuilder->mvmd_dslli(8, v1, v0, (shift / 8));
426        } else if (LLVM_LIKELY(shift < DSSLI_FIELDWIDTH)) {
427            Value * ahead = iBuilder->mvmd_dslli(DSSLI_FIELDWIDTH, v1, v0, 1);
428            ahead = iBuilder->simd_slli(DSSLI_FIELDWIDTH, ahead, DSSLI_FIELDWIDTH - shift);
429            Value * value = iBuilder->simd_srli(DSSLI_FIELDWIDTH, v0, shift);
430            expr = iBuilder->simd_or(value, ahead);
431        } else {
432            Type  * const streamType = iBuilder->getIntNTy(iBuilder->getBitBlockWidth());
433            Value * b0 = iBuilder->CreateBitCast(v0, streamType);
434            Value * b1 = iBuilder->CreateBitCast(v1, streamType);
435            Value * result = iBuilder->CreateOr(iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - shift), iBuilder->CreateLShr(b0, shift));
436            expr = iBuilder->CreateBitCast(result, mBitBlockType);
437        }
438    } else {
439        std::string tmp;
440        llvm::raw_string_ostream msg(tmp);
441        msg << "Internal error: ";
442        PabloPrinter::print(stmt, msg);
443        msg << " is not a recognized statement in the Pablo compiler.";
444        throw std::runtime_error(msg.str());
445    }
446    mMarkerMap[stmt] = expr;
447    if (DebugOptionIsSet(DumpTrace)) {
448        iBuilder->CallPrintRegister(stmt->getName()->to_string(), expr);
449    }
450   
451}
452
453Value * PabloCompiler::compileExpression(const PabloAST * expr) {
454    if (LLVM_UNLIKELY(isa<Ones>(expr))) {
455        return iBuilder->allOnes();
456    } else if (LLVM_UNLIKELY(isa<Zeroes>(expr))) {
457        return iBuilder->allZeroes();
458    }
459    auto f = mMarkerMap.find(expr);
460    if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
461        std::string o;
462        llvm::raw_string_ostream str(o);
463        str << "\"";
464        PabloPrinter::print(expr, str);
465        str << "\" was used before definition!";
466        throw std::runtime_error(str.str());
467    }
468    Value * result = f->second;
469    if (LLVM_UNLIKELY(isa<Var>(expr))) {
470        assert (isa<GetElementPtrInst>(result));
471        result = iBuilder->CreateBlockAlignedLoad(result);
472    }
473    return result;
474}
475
476}
Note: See TracBrowser for help on using the repository browser.