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

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

Dynamic generation of s2p code

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