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

Last change on this file since 4959 was 4959, checked in by nmedfort, 4 years ago

Initial modifications to Pablo Compiler and Kernel Builder to support circular buffers for Lookahead.

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