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

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

getStreamSetBlockPtr

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