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

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

Fix for long advances

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