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

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

Minor changes to function compilation preceeding any modification of the pablo Call class.

File size: 32.7 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 <cc/cc_namemap.hpp>
14#include <re/re_name.h>
15#include <stdexcept>
16#include <include/simd-lib/bitblock.hpp>
17#include <sstream>
18#include <llvm/IR/Verifier.h>
19#include <llvm/Pass.h>
20#include <llvm/PassManager.h>
21#include <llvm/ADT/SmallVector.h>
22#include <llvm/Analysis/Passes.h>
23#include <llvm/IR/BasicBlock.h>
24#include <llvm/IR/CallingConv.h>
25#include <llvm/IR/Constants.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/ExecutionEngine/ExecutionEngine.h>
43#include <llvm/ExecutionEngine/MCJIT.h>
44#include <llvm/IRReader/IRReader.h>
45#include <llvm/Bitcode/ReaderWriter.h>
46#include <llvm/Support/MemoryBuffer.h>
47#include <llvm/IR/IRBuilder.h>
48#include <llvm/Support/CommandLine.h>
49#include <llvm/ADT/Twine.h>
50#include <iostream>
51
52static cl::OptionCategory eIRDumpOptions("LLVM IR Dump Options", "These options control dumping of LLVM IR.");
53static cl::opt<bool> DumpGeneratedIR("dump-generated-IR", cl::init(false), cl::desc("print LLVM IR generated by RE compilation"), cl::cat(eIRDumpOptions));
54
55static cl::OptionCategory fTracingOptions("Run-time Tracing Options", "These options control execution traces.");
56static cl::opt<bool> TraceNext("trace-next-nodes", cl::init(false), cl::desc("Generate dynamic traces of executed Next nodes (while control variables)."), cl::cat(fTracingOptions));
57static cl::opt<bool> DumpTrace("dump-trace", cl::init(false), cl::desc("Generate dynamic traces of executed assignments."), cl::cat(fTracingOptions));
58
59extern "C" {
60  void wrapped_print_register(char * regName, BitBlock bit_block) {
61      print_register<BitBlock>(regName, bit_block);
62  }
63}
64
65namespace pablo {
66
67PabloCompiler::PabloCompiler()
68#ifdef USE_LLVM_3_5
69: mMod(new Module("icgrep", getGlobalContext()))
70#else
71: mModOwner(make_unique<Module>("icgrep", getGlobalContext()))
72, mMod(mModOwner.get())
73#endif
74, mBuilder(&LLVM_Builder)
75, mCarryManager(nullptr)
76, mExecutionEngine(nullptr)
77, mBitBlockType(VectorType::get(IntegerType::get(mMod->getContext(), 64), BLOCK_SIZE / 64))
78, mInputPtr(nullptr)
79, mCarryDataPtr(nullptr)
80, mWhileDepth(0)
81, mIfDepth(0)
82, mZeroInitializer(ConstantAggregateZero::get(mBitBlockType))
83, mOneInitializer(ConstantVector::getAllOnesValue(mBitBlockType))
84, mFunction(nullptr)
85, mInputAddressPtr(nullptr)
86, mOutputAddressPtr(nullptr)
87, mMaxWhileDepth(0)
88, mPrintRegisterFunction(nullptr)
89{
90    //Create the jit execution engine.up
91    InitializeNativeTarget();
92    InitializeNativeTargetAsmPrinter();
93    InitializeNativeTargetAsmParser();
94}
95
96PabloCompiler::~PabloCompiler()
97{
98
99}
100   
101void PabloCompiler::InstallExternalFunction(std::string C_fn_name, void * fn_ptr) {
102    mExternalMap.insert(std::make_pair(C_fn_name, fn_ptr));
103}
104
105void PabloCompiler::genPrintRegister(std::string regName, Value * bitblockValue) {
106    Constant * regNameData = ConstantDataArray::getString(mMod->getContext(), regName);
107    GlobalVariable *regStrVar = new GlobalVariable(*mMod, 
108                                                   ArrayType::get(IntegerType::get(mMod->getContext(), 8), regName.length()+1),
109                                                   /*isConstant=*/ true,
110                                                   /*Linkage=*/ GlobalValue::PrivateLinkage,
111                                                   /*Initializer=*/ regNameData);
112    Value * regStrPtr = mBuilder->CreateGEP(regStrVar, {mBuilder->getInt64(0), mBuilder->getInt32(0)});
113    mBuilder->CreateCall(mPrintRegisterFunction, {regStrPtr, bitblockValue});
114}
115
116CompiledPabloFunction PabloCompiler::compile(PabloFunction & function)
117{
118    mWhileDepth = 0;
119    mIfDepth = 0;
120    mMaxWhileDepth = 0;
121    mCarryManager = new CarryManager(mMod, mBuilder, mBitBlockType, mZeroInitializer, mOneInitializer);
122   
123    std::string errMessage;
124#ifdef USE_LLVM_3_5
125    EngineBuilder builder(mMod);
126#else
127    EngineBuilder builder(std::move(mModOwner));
128#endif
129    builder.setErrorStr(&errMessage);
130    builder.setMCPU(sys::getHostCPUName());
131#ifdef USE_LLVM_3_5
132    builder.setUseMCJIT(true);
133#endif
134    builder.setOptLevel(mMaxWhileDepth ? CodeGenOpt::Level::Less : CodeGenOpt::Level::None);
135    mExecutionEngine = builder.create();
136    if (mExecutionEngine == nullptr) {
137        throw std::runtime_error("Could not create ExecutionEngine: " + errMessage);
138    }
139
140    GenerateFunction(function);
141    DeclareFunctions();
142
143    Examine(function.getEntryBlock());
144    DeclareCallFunctions();
145
146    mWhileDepth = 0;
147    mIfDepth = 0;
148    mMaxWhileDepth = 0;
149    BasicBlock * b = BasicBlock::Create(mMod->getContext(), "entry", mFunction,0);
150    mBuilder->SetInsertPoint(b);
151
152    //The basis bits structure
153    for (unsigned i = 0; i != function.getParameters().size(); ++i) {
154        Value* indices[] = {mBuilder->getInt64(0), mBuilder->getInt32(i)};
155        Value * gep = mBuilder->CreateGEP(mInputAddressPtr, indices);
156        LoadInst * basisBit = mBuilder->CreateAlignedLoad(gep, BLOCK_SIZE/8, false, function.getParameter(i)->getName()->to_string());
157        mMarkerMap.insert(std::make_pair(function.getParameter(i), basisBit));
158        if (DumpTrace) {
159            genPrintRegister(function.getParameter(i)->getName()->to_string(), basisBit);
160        }
161    }
162       
163    unsigned totalCarryDataSize = mCarryManager->initialize(&(function.getEntryBlock()), mCarryDataPtr);
164   
165    //Generate the IR instructions for the function.
166    compileBlock(function.getEntryBlock());
167   
168    mCarryManager->generateBlockNoIncrement();
169
170    if (DumpTrace || TraceNext) {
171        genPrintRegister("mBlockNo", mBuilder->CreateAlignedLoad(mBuilder->CreateBitCast(mCarryManager->getBlockNoPtr(), PointerType::get(mBitBlockType, 0)), BLOCK_SIZE/8, false));
172    }
173   
174    if (LLVM_UNLIKELY(mWhileDepth != 0)) {
175        throw std::runtime_error("Non-zero nesting depth error (" + std::to_string(mWhileDepth) + ")");
176    }
177
178    // Write the output values out
179    for (unsigned i = 0; i != function.getResults().size(); ++i) {
180        SetOutputValue(mMarkerMap[function.getResult(i)], i);
181    }
182
183    //Terminate the block
184    ReturnInst::Create(mMod->getContext(), mBuilder->GetInsertBlock());
185
186    //Display the IR that has been generated by this module.
187    if (LLVM_UNLIKELY(DumpGeneratedIR)) {
188        mMod->dump();
189    }
190    //Create a verifier.  The verifier will print an error message if our module is malformed in any way.
191    verifyModule(*mMod, &dbgs());
192
193    mExecutionEngine->finalizeObject();
194
195    delete mCarryManager;
196    mCarryManager = nullptr;
197
198    //Return the required size of the carry data area to the process_block function.
199    return CompiledPabloFunction(totalCarryDataSize * sizeof(BitBlock), mFunction, mExecutionEngine);
200}
201
202inline void PabloCompiler::GenerateFunction(PabloFunction & function) {
203    std::vector<Type *> inputType(function.getParameters().size(), mBitBlockType);
204    std::vector<Type *> outputType(function.getResults().size(), mBitBlockType);
205    mInputPtr = PointerType::get(StructType::get(mMod->getContext(), inputType), 0);
206    Type * carryPtr = PointerType::get(mBitBlockType, 0);
207    Type * outputPtr = PointerType::get(StructType::get(mMod->getContext(), outputType), 0);
208    FunctionType * functionType = FunctionType::get(Type::getVoidTy(mMod->getContext()), {{mInputPtr, carryPtr, outputPtr}}, false);
209
210
211#ifdef USE_UADD_OVERFLOW
212#ifdef USE_TWO_UADD_OVERFLOW
213    // Type Definitions for llvm.uadd.with.overflow.carryin.i128 or .i256
214    std::vector<Type*>StructTy_0_fields;
215    StructTy_0_fields.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
216    StructTy_0_fields.push_back(IntegerType::get(mMod->getContext(), 1));
217    StructType *StructTy_0 = StructType::get(mMod->getContext(), StructTy_0_fields, /*isPacked=*/false);
218
219    std::vector<Type*>FuncTy_1_args;
220    FuncTy_1_args.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
221    FuncTy_1_args.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
222    FunctionType* FuncTy_1 = FunctionType::get(
223                                              /*Result=*/StructTy_0,
224                                              /*Params=*/FuncTy_1_args,
225                                              /*isVarArg=*/false);
226
227    mFunctionUaddOverflow = mMod->getFunction("llvm.uadd.with.overflow.i" +
228                                              std::to_string(BLOCK_SIZE));
229    if (!mFunctionUaddOverflow) {
230        mFunctionUaddOverflow= Function::Create(
231          /*Type=*/ FuncTy_1,
232          /*Linkage=*/ GlobalValue::ExternalLinkage,
233          /*Name=*/ "llvm.uadd.with.overflow.i" + std::to_string(BLOCK_SIZE), mMod); // (external, no body)
234        mFunctionUaddOverflow->setCallingConv(CallingConv::C);
235    }
236    AttributeSet mFunctionUaddOverflowPAL;
237    {
238        SmallVector<AttributeSet, 4> Attrs;
239        AttributeSet PAS;
240        {
241          AttrBuilder B;
242          B.addAttribute(Attribute::NoUnwind);
243          B.addAttribute(Attribute::ReadNone);
244          PAS = AttributeSet::get(mMod->getContext(), ~0U, B);
245        }
246
247        Attrs.push_back(PAS);
248        mFunctionUaddOverflowPAL = AttributeSet::get(mMod->getContext(), Attrs);
249    }
250    mFunctionUaddOverflow->setAttributes(mFunctionUaddOverflowPAL);
251#else
252    // Type Definitions for llvm.uadd.with.overflow.carryin.i128 or .i256
253    std::vector<Type*>StructTy_0_fields;
254    StructTy_0_fields.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
255    StructTy_0_fields.push_back(IntegerType::get(mMod->getContext(), 1));
256    StructType *StructTy_0 = StructType::get(mMod->getContext(), StructTy_0_fields, /*isPacked=*/false);
257
258    std::vector<Type*>FuncTy_1_args;
259    FuncTy_1_args.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
260    FuncTy_1_args.push_back(IntegerType::get(mMod->getContext(), BLOCK_SIZE));
261    FuncTy_1_args.push_back(IntegerType::get(mMod->getContext(), 1));
262    FunctionType* FuncTy_1 = FunctionType::get(
263                                              /*Result=*/StructTy_0,
264                                              /*Params=*/FuncTy_1_args,
265                                              /*isVarArg=*/false);
266
267    mFunctionUaddOverflowCarryin = mMod->getFunction("llvm.uadd.with.overflow.carryin.i" +
268                                              std::to_string(BLOCK_SIZE));
269    if (!mFunctionUaddOverflowCarryin) {
270        mFunctionUaddOverflowCarryin = Function::Create(
271          /*Type=*/ FuncTy_1,
272          /*Linkage=*/ GlobalValue::ExternalLinkage,
273          /*Name=*/ "llvm.uadd.with.overflow.carryin.i" + std::to_string(BLOCK_SIZE), mMod); // (external, no body)
274        mFunctionUaddOverflowCarryin->setCallingConv(CallingConv::C);
275    }
276    AttributeSet mFunctionUaddOverflowCarryinPAL;
277    {
278        SmallVector<AttributeSet, 4> Attrs;
279        AttributeSet PAS;
280        {
281          AttrBuilder B;
282          B.addAttribute(Attribute::NoUnwind);
283          B.addAttribute(Attribute::ReadNone);
284          PAS = AttributeSet::get(mMod->getContext(), ~0U, B);
285        }
286
287        Attrs.push_back(PAS);
288        mFunctionUaddOverflowCarryinPAL = AttributeSet::get(mMod->getContext(), Attrs);
289    }
290    mFunctionUaddOverflowCarryin->setAttributes(mFunctionUaddOverflowCarryinPAL);
291#endif
292#endif
293
294    //Starts on process_block
295    SmallVector<AttributeSet, 4> Attrs;
296    Attrs.push_back(AttributeSet::get(mMod->getContext(), ~0U, { Attribute::NoUnwind, Attribute::UWTable }));
297    Attrs.push_back(AttributeSet::get(mMod->getContext(), 1U, { Attribute::ReadOnly, Attribute::NoCapture }));
298    Attrs.push_back(AttributeSet::get(mMod->getContext(), 2U, { Attribute::NoCapture }));
299    Attrs.push_back(AttributeSet::get(mMod->getContext(), 3U, { Attribute::ReadNone, Attribute::NoCapture }));
300    AttributeSet AttrSet = AttributeSet::get(mMod->getContext(), Attrs);
301
302    // Create the function that will be generated.
303    mFunction = Function::Create(functionType, GlobalValue::ExternalLinkage, function.getName()->value(), mMod);
304    mFunction->setCallingConv(CallingConv::C);
305    mFunction->setAttributes(AttrSet);
306
307    Function::arg_iterator args = mFunction->arg_begin();
308    mInputAddressPtr = args++;
309    mInputAddressPtr->setName("input");
310    mCarryDataPtr = args++;
311    mCarryDataPtr->setName("carry");
312    mOutputAddressPtr = args++;
313    mOutputAddressPtr->setName("output");
314}
315
316inline void PabloCompiler::DeclareFunctions() {
317    if (DumpTrace || TraceNext) {
318        //This function can be used for testing to print the contents of a register from JIT'd code to the terminal window.
319        mPrintRegisterFunction = mMod->getOrInsertFunction("wrapped_print_register", Type::getVoidTy(getGlobalContext()), Type::getInt8PtrTy(getGlobalContext()), mBitBlockType, NULL);
320        mExecutionEngine->addGlobalMapping(cast<GlobalValue>(mPrintRegisterFunction), (void *)&wrapped_print_register);
321    }
322}
323   
324void PabloCompiler::Examine(PabloBlock & blk) {
325    for (Statement * stmt : blk) {
326        if (Call * call = dyn_cast<Call>(stmt)) {
327            mCalleeMap.insert(std::make_pair(call->getCallee(), nullptr));
328        }
329        else if (If * ifStatement = dyn_cast<If>(stmt)) {
330            ++mIfDepth;
331            Examine(ifStatement->getBody());
332            --mIfDepth;
333        }
334        else if (While * whileStatement = dyn_cast<While>(stmt)) {
335            mMaxWhileDepth = std::max(mMaxWhileDepth, ++mWhileDepth);
336            Examine(whileStatement->getBody());
337            --mWhileDepth;
338        }
339    }
340}
341
342void PabloCompiler::DeclareCallFunctions() {
343    for (auto mapping : mCalleeMap) {
344        const String * callee = mapping.first;
345        //std::cerr << callee->str() << " to be declared\n";
346        auto ei = mExternalMap.find(callee->value());
347        if (ei != mExternalMap.end()) {
348            void * fn_ptr = ei->second;
349            Value * externalValue = mMod->getOrInsertFunction(callee->value(), mBitBlockType, mInputPtr, NULL);
350            if (LLVM_UNLIKELY(externalValue == nullptr)) {
351                throw std::runtime_error("Could not create static method call for external function \"" + callee->to_string() + "\"");
352            }
353            mExecutionEngine->addGlobalMapping(cast<GlobalValue>(externalValue), fn_ptr);
354            mCalleeMap[callee] = externalValue;
355        }
356        else {
357            throw std::runtime_error("External function \"" + callee->to_string() + "\" not installed");
358        }
359    }
360}
361
362void PabloCompiler::compileBlock(PabloBlock & block) {
363    mCarryManager->ensureCarriesLoadedLocal(block);
364    mPabloBlock = & block;
365    for (const Statement * statement : block) {
366        compileStatement(statement);
367    }
368    mPabloBlock = block.getParent();
369    mCarryManager->ensureCarriesStoredLocal(block);
370}
371
372
373void PabloCompiler::compileIf(const If * ifStatement) {       
374    //
375    //  The If-ElseZero stmt:
376    //  if <predicate:expr> then <body:stmt>* elsezero <defined:var>* endif
377    //  If the value of the predicate is nonzero, then determine the values of variables
378    //  <var>* by executing the given statements.  Otherwise, the value of the
379    //  variables are all zero.  Requirements: (a) no variable that is defined within
380    //  the body of the if may be accessed outside unless it is explicitly
381    //  listed in the variable list, (b) every variable in the defined list receives
382    //  a value within the body, and (c) the logical consequence of executing
383    //  the statements in the event that the predicate is zero is that the
384    //  values of all defined variables indeed work out to be 0.
385    //
386    //  Simple Implementation with Phi nodes:  a phi node in the if exit block
387    //  is inserted for each variable in the defined variable list.  It receives
388    //  a zero value from the ifentry block and the defined value from the if
389    //  body.
390    //
391    BasicBlock * ifEntryBlock = mBuilder->GetInsertBlock();
392    BasicBlock * ifBodyBlock = BasicBlock::Create(mMod->getContext(), "if.body", mFunction, 0);
393    BasicBlock * ifEndBlock = BasicBlock::Create(mMod->getContext(), "if.end", mFunction, 0);
394   
395    PabloBlock & ifBody = ifStatement -> getBody();
396   
397    Value* if_test_value = compileExpression(ifStatement->getCondition());
398    if (mCarryManager->blockHasCarries(ifBody)) {
399        // load the summary variable
400        Value* last_if_pending_data = mCarryManager->getCarrySummaryExpr(ifBody);
401        if_test_value = mBuilder->CreateOr(if_test_value, last_if_pending_data);
402    }
403    mBuilder->CreateCondBr(genBitBlockAny(if_test_value), ifEndBlock, ifBodyBlock);
404    // Entry processing is complete, now handle the body of the if.
405    mBuilder->SetInsertPoint(ifBodyBlock);
406   
407    ++mIfDepth;
408    compileBlock(ifBody);
409    --mIfDepth;
410    if (mCarryManager->blockHasCarries(ifBody)) {
411        mCarryManager->generateCarryOutSummaryCode(ifBody);
412    }
413    BasicBlock * ifBodyFinalBlock = mBuilder->GetInsertBlock();
414    mBuilder->CreateBr(ifEndBlock);
415    //End Block
416    mBuilder->SetInsertPoint(ifEndBlock);
417    for (const PabloAST * node : ifStatement->getDefined()) {
418        const Assign * assign = cast<Assign>(node);
419        PHINode * phi = mBuilder->CreatePHI(mBitBlockType, 2, assign->getName()->value());
420        auto f = mMarkerMap.find(assign);
421        assert (f != mMarkerMap.end());
422        phi->addIncoming(mZeroInitializer, ifEntryBlock);
423        phi->addIncoming(f->second, ifBodyFinalBlock);
424        mMarkerMap[assign] = phi;
425    }
426    // Create the phi Node for the summary variable, if needed.
427    if (mCarryManager->summaryNeededInParentBlock(ifBody)) {
428        mCarryManager->addSummaryPhi(ifBody, ifEntryBlock, ifBodyFinalBlock);
429    }
430}
431
432void PabloCompiler::compileWhile(const While * whileStatement) {
433
434    PabloBlock & whileBody = whileStatement -> getBody();
435   
436    BasicBlock * whileEntryBlock = mBuilder->GetInsertBlock();
437    BasicBlock * whileBodyBlock = BasicBlock::Create(mMod->getContext(), "while.body", mFunction, 0);
438    BasicBlock * whileEndBlock = BasicBlock::Create(mMod->getContext(), "while.end", mFunction, 0);
439
440    mCarryManager->ensureCarriesLoadedRecursive(whileBody);
441
442    const auto & nextNodes = whileStatement->getVariants();
443    std::vector<PHINode *> nextPhis;
444    nextPhis.reserve(nextNodes.size());
445
446    // On entry to the while structure, proceed to execute the first iteration
447    // of the loop body unconditionally.   The while condition is tested at the end of
448    // the loop.
449
450    mBuilder->CreateBr(whileBodyBlock);
451    mBuilder->SetInsertPoint(whileBodyBlock);
452
453    //
454    // There are 3 sets of Phi nodes for the while loop.
455    // (1) Carry-ins: (a) incoming carry data first iterations, (b) zero thereafter
456    // (2) Carry-out accumulators: (a) zero first iteration, (b) |= carry-out of each iteration
457    // (3) Next nodes: (a) values set up before loop, (b) modified values calculated in loop.
458
459    mCarryManager->initializeCarryDataPhisAtWhileEntry(whileBody, whileEntryBlock);
460
461    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
462    for (const Next * n : nextNodes) {
463        PHINode * phi = mBuilder->CreatePHI(mBitBlockType, 2, n->getName()->value());
464        auto f = mMarkerMap.find(n->getInitial());
465        assert (f != mMarkerMap.end());
466        phi->addIncoming(f->second, whileEntryBlock);
467        mMarkerMap[n->getInitial()] = phi;
468        nextPhis.push_back(phi);
469    }
470
471    //
472    // Now compile the loop body proper.  Carry-out accumulated values
473    // and iterated values of Next nodes will be computed.
474    ++mWhileDepth;
475    compileBlock(whileBody);
476
477    BasicBlock * whileBodyFinalBlock = mBuilder->GetInsertBlock();
478
479    mCarryManager->extendCarryDataPhisAtWhileBodyFinalBlock(whileBody, whileBodyFinalBlock);
480
481    // Terminate the while loop body with a conditional branch back.
482    mBuilder->CreateCondBr(genBitBlockAny(compileExpression(whileStatement->getCondition())), whileEndBlock, whileBodyBlock);
483
484    // and for any Next nodes in the loop body
485    for (unsigned i = 0; i < nextNodes.size(); i++) {
486        const Next * n = nextNodes[i];
487        auto f = mMarkerMap.find(n->getExpr());
488        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
489            throw std::runtime_error("Next node expression was not compiled!");
490        }
491        nextPhis[i]->addIncoming(f->second, whileBodyFinalBlock);
492    }
493
494    mBuilder->SetInsertPoint(whileEndBlock);
495    --mWhileDepth;
496
497    mCarryManager->ensureCarriesStoredRecursive(whileBody);
498}
499
500
501void PabloCompiler::compileStatement(const Statement * stmt) {
502    Value * expr = nullptr;
503    if (const Assign * assign = dyn_cast<const Assign>(stmt)) {
504        expr = compileExpression(assign->getExpression());
505    }
506    else if (const Next * next = dyn_cast<const Next>(stmt)) {
507        expr = compileExpression(next->getExpr());
508        if (TraceNext) {
509            genPrintRegister(next->getName()->to_string(), expr);
510        }
511    }
512    else if (const If * ifStatement = dyn_cast<const If>(stmt)) {
513        compileIf(ifStatement);
514        return;
515    }
516    else if (const While * whileStatement = dyn_cast<const While>(stmt)) {
517        compileWhile(whileStatement);
518        return;
519    }
520    else if (const Call* call = dyn_cast<Call>(stmt)) {
521        //Call the callee once and store the result in the marker map.
522        if (mMarkerMap.count(call) != 0) {
523            return;
524        }
525        auto ci = mCalleeMap.find(call->getCallee());
526        if (LLVM_UNLIKELY(ci == mCalleeMap.end())) {
527            throw std::runtime_error("Unexpected error locating static function for \"" + call->getCallee()->to_string() + "\"");
528        }
529        expr = mBuilder->CreateCall(ci->second, mInputAddressPtr);
530    }
531    else if (const And * pablo_and = dyn_cast<And>(stmt)) {
532        expr = mBuilder->CreateAnd(compileExpression(pablo_and->getExpr1()), compileExpression(pablo_and->getExpr2()), "and");
533    }
534    else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
535        expr = mBuilder->CreateOr(compileExpression(pablo_or->getExpr1()), compileExpression(pablo_or->getExpr2()), "or");
536    }
537    else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
538        expr = mBuilder->CreateXor(compileExpression(pablo_xor->getExpr1()), compileExpression(pablo_xor->getExpr2()), "xor");
539    }
540    else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
541        Value* ifMask = compileExpression(sel->getCondition());
542        Value* ifTrue = mBuilder->CreateAnd(ifMask, compileExpression(sel->getTrueExpr()));
543        Value* ifFalse = mBuilder->CreateAnd(genNot(ifMask), compileExpression(sel->getFalseExpr()));
544        expr = mBuilder->CreateOr(ifTrue, ifFalse);
545    }
546    else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
547        expr = genNot(compileExpression(pablo_not->getExpr()));
548    }
549    else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
550        Value* strm_value = compileExpression(adv->getExpr());
551        int shift = adv->getAdvanceAmount();
552        unsigned advance_index = adv->getLocalAdvanceIndex();
553        expr = mCarryManager->advanceCarryInCarryOut(mPabloBlock, advance_index, shift, strm_value);
554    }
555    else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
556        Value * marker = compileExpression(mstar->getMarker());
557        Value * cc = compileExpression(mstar->getCharClass());
558        Value * marker_and_cc = mBuilder->CreateAnd(marker, cc);
559        unsigned carry_index = mstar->getLocalCarryIndex();
560        expr = mBuilder->CreateOr(mBuilder->CreateXor(genAddWithCarry(marker_and_cc, cc, carry_index), cc), marker, "matchstar");
561    }
562    else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
563        Value * marker_expr = compileExpression(sthru->getScanFrom());
564        Value * cc_expr = compileExpression(sthru->getScanThru());
565        unsigned carry_index = sthru->getLocalCarryIndex();
566        expr = mBuilder->CreateAnd(genAddWithCarry(marker_expr, cc_expr, carry_index), genNot(cc_expr), "scanthru");
567    }
568    else {
569        llvm::raw_os_ostream cerr(std::cerr);
570        PabloPrinter::print(stmt, cerr);
571        throw std::runtime_error("Unrecognized Pablo Statement! can't compile.");
572    }
573    mMarkerMap[stmt] = expr;
574    if (DumpTrace) {
575        genPrintRegister(stmt->getName()->to_string(), expr);
576    }
577   
578}
579
580Value * PabloCompiler::compileExpression(const PabloAST * expr) {
581    if (isa<Ones>(expr)) {
582        return mOneInitializer;
583    }
584    else if (isa<Zeroes>(expr)) {
585        return mZeroInitializer;
586    }
587    auto f = mMarkerMap.find(expr);
588    if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
589        std::string o;
590        llvm::raw_string_ostream str(o);
591        str << "\"";
592        PabloPrinter::print(expr, str);
593        str << "\" was used before definition!";
594        throw std::runtime_error(str.str());
595    }
596    return f->second;
597}
598
599
600#ifdef USE_UADD_OVERFLOW
601#ifdef USE_TWO_UADD_OVERFLOW
602PabloCompiler::SumWithOverflowPack PabloCompiler::callUaddOverflow(Value* int128_e1, Value* int128_e2) {
603    std::vector<Value*> struct_res_params;
604    struct_res_params.push_back(int128_e1);
605    struct_res_params.push_back(int128_e2);
606    CallInst* struct_res = CallInst::Create(mFunctionUaddOverflow, struct_res_params, "uadd_overflow_res", mBasicBlock);
607    struct_res->setCallingConv(CallingConv::C);
608    struct_res->setTailCall(false);
609    AttributeSet struct_res_PAL;
610    struct_res->setAttributes(struct_res_PAL);
611
612    SumWithOverflowPack ret;
613
614    std::vector<unsigned> int128_sum_indices;
615    int128_sum_indices.push_back(0);
616    ret.sum = ExtractValueInst::Create(struct_res, int128_sum_indices, "sum", mBasicBlock);
617
618    std::vector<unsigned> int1_obit_indices;
619    int1_obit_indices.push_back(1);
620    ret.obit = ExtractValueInst::Create(struct_res, int1_obit_indices, "obit", mBasicBlock);
621
622    return ret;
623}
624#else
625PabloCompiler::SumWithOverflowPack PabloCompiler::callUaddOverflow(Value* int128_e1, Value* int128_e2, Value* int1_cin) {
626    std::vector<Value*> struct_res_params;
627    struct_res_params.push_back(int128_e1);
628    struct_res_params.push_back(int128_e2);
629    struct_res_params.push_back(int1_cin);
630    CallInst* struct_res = CallInst::Create(mFunctionUaddOverflowCarryin, struct_res_params, "uadd_overflow_res", mBasicBlock);
631    struct_res->setCallingConv(CallingConv::C);
632    struct_res->setTailCall(false);
633    AttributeSet struct_res_PAL;
634    struct_res->setAttributes(struct_res_PAL);
635
636    SumWithOverflowPack ret;
637
638    std::vector<unsigned> int128_sum_indices;
639    int128_sum_indices.push_back(0);
640    ret.sum = ExtractValueInst::Create(struct_res, int128_sum_indices, "sum", mBasicBlock);
641
642    std::vector<unsigned> int1_obit_indices;
643    int1_obit_indices.push_back(1);
644    ret.obit = ExtractValueInst::Create(struct_res, int1_obit_indices, "obit", mBasicBlock);
645
646    return ret;
647}
648#endif
649#endif
650
651
652Value* PabloCompiler::genAddWithCarry(Value* e1, Value* e2, unsigned localIndex) {
653    Value * carryq_value = mCarryManager->getCarryOpCarryIn(mPabloBlock, localIndex);
654#ifdef USE_TWO_UADD_OVERFLOW
655    //This is the ideal implementation, which uses two uadd.with.overflow
656    //The back end should be able to recognize this pattern and combine it into uadd.with.overflow.carryin
657    CastInst* int128_e1 = new BitCastInst(e1, mBuilder->getIntNTy(BLOCK_SIZE), "e1_128", mBasicBlock);
658    CastInst* int128_e2 = new BitCastInst(e2, mBuilder->getIntNTy(BLOCK_SIZE), "e2_128", mBasicBlock);
659    CastInst* int128_carryq_value = new BitCastInst(carryq_value, mBuilder->getIntNTy(BLOCK_SIZE), "carryq_128", mBasicBlock);
660
661    SumWithOverflowPack sumpack0, sumpack1;
662
663    sumpack0 = callUaddOverflow(int128_e1, int128_e2);
664    sumpack1 = callUaddOverflow(sumpack0.sum, int128_carryq_value);
665
666    Value* obit = mBuilder->CreateOr(sumpack0.obit, sumpack1.obit, "carry_bit");
667    Value* sum = mBuilder->CreateBitCast(sumpack1.sum, mBitBlockType, "ret_sum");
668
669    /*obit is the i1 carryout, zero extend and insert it into a v2i64 or v4i64 vector.*/
670    ConstantAggregateZero* const_packed_5 = ConstantAggregateZero::get(mBitBlockType);
671    ConstantInt* const_int32_6 = ConstantInt::get(mMod->getContext(), APInt(32, StringRef("0"), 10));
672    CastInst* int64_o0 = new ZExtInst(obit, IntegerType::get(mMod->getContext(), 64), "o0", mBasicBlock);
673    InsertElementInst* carry_out = InsertElementInst::Create(const_packed_5, int64_o0, const_int32_6, "carry_out", mBasicBlock);
674
675#elif defined USE_UADD_OVERFLOW
676    //use llvm.uadd.with.overflow.i128 or i256
677    CastInst* int128_e1 = new BitCastInst(e1, mBuilder->getIntNTy(BLOCK_SIZE), "e1_128", mBasicBlock);
678    CastInst* int128_e2 = new BitCastInst(e2, mBuilder->getIntNTy(BLOCK_SIZE), "e2_128", mBasicBlock);
679
680    //get i1 carryin from iBLOCK_SIZE
681    ConstantInt* const_int32_6 = ConstantInt::get(mMod->getContext(), APInt(32, StringRef("0"), 10));
682    ExtractElementInst * int64_carryq_value = ExtractElementInst::Create(carryq_value, const_int32_6, "carryq_64", mBasicBlock);
683    CastInst* int1_carryq_value = new TruncInst(int64_carryq_value, IntegerType::get(mMod->getContext(), 1), "carryq_1", mBasicBlock);
684
685    SumWithOverflowPack sumpack0;
686    sumpack0 = callUaddOverflow(int128_e1, int128_e2, int1_carryq_value);
687    Value* obit = sumpack0.obit;
688    Value* sum = mBuilder->CreateBitCast(sumpack0.sum, mBitBlockType, "sum");
689
690    /*obit is the i1 carryout, zero extend and insert it into a v2i64 or v4i64 vector.*/
691    ConstantAggregateZero* const_packed_5 = ConstantAggregateZero::get(mBitBlockType);
692    CastInst* int64_o0 = new ZExtInst(obit, IntegerType::get(mMod->getContext(), 64), "o0", mBasicBlock);
693    InsertElementInst* carry_out = InsertElementInst::Create(const_packed_5, int64_o0, const_int32_6, "carry_out", mBasicBlock);
694#elif (BLOCK_SIZE == 128)
695    //calculate carry through logical ops
696    Value* carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
697    Value* carryprop = mBuilder->CreateOr(e1, e2, "carryprop");
698    Value* digitsum = mBuilder->CreateAdd(e1, e2, "digitsum");
699    Value* partial = mBuilder->CreateAdd(digitsum, carryq_value, "partial");
700    Value* digitcarry = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, genNot(partial)));
701    Value* mid_carry_in = genShiftLeft64(mBuilder->CreateLShr(digitcarry, 63), "mid_carry_in");
702
703    Value* sum = mBuilder->CreateAdd(partial, mid_carry_in, "sum");
704    Value* carry_out = genShiftHighbitToLow(BLOCK_SIZE, mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, genNot(sum))));
705#else
706    //BLOCK_SIZE == 256, there is no other implementation
707    static_assert(false, "Add with carry for 256-bit bitblock requires USE_UADD_OVERFLOW");
708#endif //USE_TWO_UADD_OVERFLOW
709
710    mCarryManager->setCarryOpCarryOut(mPabloBlock, localIndex, carry_out);
711    return sum;
712}
713
714inline Value* PabloCompiler::genBitBlockAny(Value* test) {
715    Value* cast_marker_value_1 = mBuilder->CreateBitCast(test, mBuilder->getIntNTy(BLOCK_SIZE));
716    return mBuilder->CreateICmpEQ(cast_marker_value_1, ConstantInt::get(mBuilder->getIntNTy(BLOCK_SIZE), 0));
717}
718
719Value * PabloCompiler::genShiftHighbitToLow(unsigned FieldWidth, Value * op) {
720    unsigned FieldCount = BLOCK_SIZE/FieldWidth;
721    VectorType * vType = VectorType::get(IntegerType::get(mMod->getContext(), FieldWidth), FieldCount);
722    Value * v = mBuilder->CreateBitCast(op, vType);
723    return mBuilder->CreateBitCast(mBuilder->CreateLShr(v, FieldWidth - 1), mBitBlockType);
724}
725
726Value* PabloCompiler::genShiftLeft64(Value* e, const Twine &namehint) {
727    Value* i128_val = mBuilder->CreateBitCast(e, mBuilder->getIntNTy(BLOCK_SIZE));
728    return mBuilder->CreateBitCast(mBuilder->CreateShl(i128_val, 64, namehint), mBitBlockType);
729}
730
731inline Value* PabloCompiler::genNot(Value* expr) {
732    return mBuilder->CreateXor(expr, mOneInitializer, "not");
733}
734   
735void PabloCompiler::SetOutputValue(Value * marker, const unsigned index) {
736    if (marker->getType()->isPointerTy()) {
737        marker = mBuilder->CreateAlignedLoad(marker, BLOCK_SIZE/8, false);
738    }
739    Value* indices[] = {mBuilder->getInt64(0), mBuilder->getInt32(index)};
740    Value* gep = mBuilder->CreateGEP(mOutputAddressPtr, indices);
741    mBuilder->CreateAlignedStore(marker, gep, BLOCK_SIZE/8, false);
742}
743
744CompiledPabloFunction::CompiledPabloFunction(size_t carryDataSize, Function * function, ExecutionEngine * executionEngine)
745: CarryDataSize(carryDataSize)
746, FunctionPointer(executionEngine->getPointerToFunction(function))
747, mFunction(function)
748, mExecutionEngine(executionEngine)
749{
750
751}
752
753// Clean up the memory for the compiled function once we're finished using it.
754CompiledPabloFunction::~CompiledPabloFunction() {
755    if (mExecutionEngine) {
756        assert (mFunction);
757        // mExecutionEngine->freeMachineCodeForFunction(mFunction); // This function only prints a "not supported" message. Reevaluate with LLVM 3.6.
758        delete mExecutionEngine;
759    }
760}
761
762}
Note: See TracBrowser for help on using the repository browser.