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

Last change on this file since 4968 was 4968, checked in by nmedfort, 3 years ago

Some fixes for threading and kernel builder.

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