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

Last change on this file since 5045 was 5045, checked in by xuedongx, 3 years ago

Support over UTF-16 representation of Unicode

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