source: icGREP/icgrep-devel/icgrep/IR_Gen/CBuilder.cpp @ 6237

Last change on this file since 6237 was 6237, checked in by nmedfort, 4 months ago

Re-enabled segment pipeline parallelism; moved logical segment number into pipeline kernel.

File size: 64.6 KB
Line 
1/*
2 *  Copyright (c) 2016 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 "CBuilder.h"
8#include <llvm/IR/Mangler.h>
9#include <llvm/IR/Module.h>
10#include <llvm/IR/Constants.h>
11#include <llvm/IR/Intrinsics.h>
12#include <llvm/IR/TypeBuilder.h>
13#include <llvm/IR/MDBuilder.h>
14#include <llvm/ADT/DenseSet.h>
15#include <llvm/Support/raw_ostream.h>
16#include <llvm/Support/Format.h>
17#include <toolchain/toolchain.h>
18#include <toolchain/driver.h>
19//#include <thread>
20#include <stdlib.h>
21#include <sys/mman.h>
22#include <unistd.h>
23#include <stdio.h>
24#include <boost/format.hpp>
25#include <boost/interprocess/mapped_region.hpp>
26
27#if defined(__i386__)
28typedef uint32_t unw_word_t;
29#else
30typedef uint64_t unw_word_t;
31#endif
32#if defined(HAS_MACH_VM_TYPES)
33#include <mach/vm_types.h>
34extern void _thread_stack_pcs(vm_address_t *buffer, unsigned max, unsigned *nb, unsigned skip);
35static_assert(sizeof(vm_address_t) == sizeof(uintptr_t), "");
36#elif defined(HAS_LIBUNWIND)
37#define UNW_LOCAL_ONLY
38#include <libunwind.h>
39static_assert(sizeof(unw_word_t) <= sizeof(uintptr_t), "");
40#elif defined(HAS_EXECINFO)
41#include <execinfo.h>
42static_assert(sizeof(void *) == sizeof(uintptr_t), "");
43#endif
44
45
46#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
47#define setReturnDoesNotAlias() setDoesNotAlias(0)
48#endif
49
50using namespace llvm;
51
52inline static bool is_power_2(const uint64_t n) {
53    return ((n & (n - 1)) == 0) && n;
54}
55
56#ifdef HAS_ADDRESS_SANITIZER
57Value * checkHeapAddress(CBuilder * const b, Value * const Ptr, Value * const Size) {
58    Module * const m = b->getModule();
59    PointerType * const voidPtrTy = b->getVoidPtrTy();
60    IntegerType * const sizeTy = b->getSizeTy();
61    Function * isPoisoned = m->getFunction("__asan_region_is_poisoned");
62    if (LLVM_UNLIKELY(isPoisoned == nullptr)) {
63        isPoisoned = Function::Create(FunctionType::get(voidPtrTy, {voidPtrTy, sizeTy}, false), Function::ExternalLinkage, "__asan_region_is_poisoned", m);
64        isPoisoned->setCallingConv(CallingConv::C);
65        isPoisoned->setReturnDoesNotAlias();
66        #if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
67        isPoisoned->setDoesNotAlias(1);
68        #endif
69    }
70    Value * const addr = b->CreatePointerCast(Ptr, voidPtrTy);
71    Value * check = b->CreateCall(isPoisoned, { addr, b->CreateTrunc(Size, sizeTy) });
72    return b->CreateICmpEQ(check, ConstantPointerNull::get(cast<PointerType>(isPoisoned->getReturnType())));
73}
74#define CHECK_HEAP_ADDRESS(Ptr, Size, Name) \
75if (LLVM_UNLIKELY(hasAddressSanitizer())) { \
76    CreateAssert(checkHeapAddress(this, Ptr, Size), Name " was given unallocated memory address"); \
77}
78#else
79#define CHECK_HEAP_ADDRESS(Ptr, Size, Name)
80#endif
81
82static AllocaInst * resolveStackAddress(Value * Ptr) {
83    for (;;) {
84        if (GetElementPtrInst * gep = dyn_cast<GetElementPtrInst>(Ptr)) {
85            Ptr = gep->getPointerOperand();
86        } else if (CastInst * ci = dyn_cast<CastInst>(Ptr)) {
87            Ptr = ci->getOperand(0);
88        } else {
89            return dyn_cast<AllocaInst>(Ptr);
90        }
91    }
92}
93
94static inline bool notConstantZeroArraySize(const AllocaInst * const Base) {
95    if (const Constant * const as = dyn_cast_or_null<Constant>(Base->getArraySize())) {
96        return !as->isNullValue();
97    }
98    return false;
99}
100
101static Value * checkStackAddress(CBuilder * const b, Value * const Ptr, Value * const Size, AllocaInst * const Base) {
102    DataLayout DL(b->getModule());
103    IntegerType * const intPtrTy = cast<IntegerType>(DL.getIntPtrType(Ptr->getType()));
104    Value * sz = ConstantExpr::getBitCast(ConstantExpr::getSizeOf(Base->getAllocatedType()), intPtrTy);
105    if (notConstantZeroArraySize(Base)) {
106        sz = b->CreateMul(sz, b->CreateZExtOrTrunc(Base->getArraySize(), intPtrTy));
107    }
108    Value * const p = b->CreatePtrToInt(Ptr, intPtrTy);
109    Value * const s = b->CreatePtrToInt(Base, intPtrTy);
110    Value * const w = b->CreateAdd(p, b->CreateZExtOrTrunc(Size, intPtrTy));
111    Value * const e = b->CreateAdd(s, sz);
112    return b->CreateAnd(b->CreateICmpUGE(p, s), b->CreateICmpULE(w, e));
113}
114
115#define CHECK_ADDRESS(Ptr, Size, Name) \
116    CreateAssert(Ptr, Name " was given a null address"); \
117    if (AllocaInst * Base = resolveStackAddress(Ptr)) { \
118        CreateAssert(checkStackAddress(this, Ptr, Size, Base), Name " was given an invalid stack address"); \
119    } else { \
120        CHECK_HEAP_ADDRESS(Ptr, Size, Name) \
121    }
122
123Value * CBuilder::CreateURem(Value * const number, Value * const divisor, const Twine & Name) {
124    if (ConstantInt * const c = dyn_cast<ConstantInt>(divisor)) {
125        const auto d = c->getZExtValue();
126        assert ("CreateURem divisor cannot be 0!" && d);
127        if (is_power_2(d)) {
128            if (LLVM_UNLIKELY(d == 1)) {
129                return ConstantInt::getNullValue(number->getType());
130            } else {
131                return CreateAnd(number, ConstantInt::get(number->getType(), d - 1), Name);
132            }
133        }
134    }
135    CreateAssert(divisor, "CreateURem divisor cannot be 0!");
136    return Insert(BinaryOperator::CreateURem(number, divisor), Name);
137}
138
139Value * CBuilder::CreateUDiv(Value * const number, Value * const divisor, const Twine & Name) {
140    if (ConstantInt * c = dyn_cast<ConstantInt>(divisor)) {
141        const auto d = c->getZExtValue();
142        assert ("CreateUDiv divisor cannot be 0!" && d);
143        if (is_power_2(d)) {
144            if (d > 1) {
145                return CreateLShr(number, ConstantInt::get(divisor->getType(), std::log2(d)), Name);
146            } else {
147                return number;
148            }
149        }
150    }
151    CreateAssert(divisor, "CreateUDiv divisor cannot be 0!");
152    return Insert(BinaryOperator::CreateUDiv(number, divisor), Name);
153}
154
155Value * CBuilder::CreateCeilUDiv(Value * const number, Value * const divisor, const Twine & Name) {
156    assert (number->getType() == divisor->getType());
157    Type * const t = number->getType();
158    Constant * const ONE = ConstantInt::get(t, 1);
159    // avoid overflow with x+y-1
160    return CreateAdd(CreateUDiv(CreateSub(number, ONE), divisor), ONE, Name);
161}
162
163Value * CBuilder::CreateRoundUp(Value * const number, Value * const divisor, const Twine & Name) {
164    if (isa<ConstantInt>(divisor)) {
165        const auto d = cast<ConstantInt>(divisor)->getZExtValue();
166        if (is_power_2(d)) {
167            Constant * const ONE = ConstantInt::get(divisor->getType(), 1);
168            Constant * const toAdd = ConstantExpr::getSub(cast<ConstantInt>(divisor), ONE);
169            return CreateAnd(CreateAdd(number, toAdd), ConstantExpr::getNeg(cast<ConstantInt>(divisor)));
170        }
171    }
172    return CreateMul(CreateCeilUDiv(number, divisor), divisor, Name);
173}
174
175Value * CBuilder::CreateOpenCall(Value * filename, Value * oflag, Value * mode) {
176    Module * const m = getModule();
177    Function * openFn = m->getFunction("open");
178    if (openFn == nullptr) {
179        IntegerType * const int32Ty = getInt32Ty();
180        PointerType * const int8PtrTy = getInt8PtrTy();
181        openFn = cast<Function>(m->getOrInsertFunction("open",
182                                                         int32Ty, int8PtrTy, int32Ty, int32Ty, nullptr));
183    }
184    return CreateCall(openFn, {filename, oflag, mode});
185}
186
187// ssize_t write(int fildes, const void *buf, size_t nbyte);
188Value * CBuilder::CreateWriteCall(Value * fileDescriptor, Value * buf, Value * nbyte) {
189    PointerType * const voidPtrTy = getVoidPtrTy();
190    Module * const m = getModule();
191    Function * write = m->getFunction("write");
192    if (write == nullptr) {
193        IntegerType * const sizeTy = getSizeTy();
194        IntegerType * const int32Ty = getInt32Ty();
195        write = cast<Function>(m->getOrInsertFunction("write",
196#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
197        AttributeSet().addAttribute(getContext(), 2U, Attribute::NoAlias),
198#else
199        AttributeList().addAttribute(getContext(), 2U, Attribute::NoAlias),
200#endif
201        sizeTy, int32Ty, voidPtrTy, sizeTy, nullptr));
202    }
203    buf = CreatePointerCast(buf, voidPtrTy);
204    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
205        CHECK_ADDRESS(buf, nbyte, "CreateWriteCall");
206    }
207    return CreateCall(write, {fileDescriptor, buf, nbyte});
208}
209
210Value * CBuilder::CreateReadCall(Value * fileDescriptor, Value * buf, Value * nbyte) {
211    PointerType * const voidPtrTy = getVoidPtrTy();
212    Module * const m = getModule();
213    Function * readFn = m->getFunction("read");
214    if (readFn == nullptr) {
215        IntegerType * const sizeTy = getSizeTy();
216        IntegerType * const int32Ty = getInt32Ty();
217        readFn = cast<Function>(m->getOrInsertFunction("read",
218#if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
219        AttributeSet().addAttribute(getContext(), 2U, Attribute::NoAlias),
220#else
221        AttributeList().addAttribute(getContext(), 2U, Attribute::NoAlias),
222#endif
223        sizeTy, int32Ty, voidPtrTy, sizeTy, nullptr));
224    }
225    buf = CreatePointerCast(buf, voidPtrTy);
226    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
227        CHECK_ADDRESS(buf, nbyte, "CreateReadCall");
228    }
229    return CreateCall(readFn, {fileDescriptor, buf, nbyte});
230}
231
232Value * CBuilder::CreateCloseCall(Value * fileDescriptor) {
233    Module * const m = getModule();
234    Function * closeFn = m->getFunction("close");
235    if (closeFn == nullptr) {
236        IntegerType * int32Ty = getInt32Ty();
237        FunctionType * fty = FunctionType::get(int32Ty, {int32Ty}, true);
238        closeFn = Function::Create(fty, Function::ExternalLinkage, "close", m);
239    }
240    return CreateCall(closeFn, fileDescriptor);
241}
242
243Value * CBuilder::CreateUnlinkCall(Value * path) {
244    Module * const m = getModule();
245    Function * unlinkFunc = m->getFunction("unlink");
246    if (unlinkFunc == nullptr) {
247        FunctionType * fty = FunctionType::get(getInt32Ty(), {getInt8PtrTy()}, false);
248        unlinkFunc = Function::Create(fty, Function::ExternalLinkage, "unlink", m);
249        unlinkFunc->setCallingConv(CallingConv::C);
250    }
251    return CreateCall(unlinkFunc, path);
252}
253
254Value * CBuilder::CreateMkstempCall(Value * ftemplate) {
255    Module * const m = getModule();
256    Function * mkstempFn = m->getFunction("mkstemp");
257    if (mkstempFn == nullptr) {
258        FunctionType * const fty = FunctionType::get(getInt32Ty(), {getInt8PtrTy()}, false);
259        mkstempFn = Function::Create(fty, Function::ExternalLinkage, "mkstemp", m);
260    }
261    return CreateCall(mkstempFn, ftemplate);
262}
263
264Value * CBuilder::CreateStrlenCall(Value * str) {
265    Module * const m = getModule();
266    Function * strlenFn = m->getFunction("strlen");
267    if (strlenFn == nullptr) {
268        FunctionType * const fty = FunctionType::get(getSizeTy(), {getInt8PtrTy()}, false);
269        strlenFn = Function::Create(fty, Function::ExternalLinkage, "strlen", m);
270    }
271    return CreateCall(strlenFn, str);
272}
273
274Function * CBuilder::GetPrintf() {
275    Module * const m = getModule();
276    Function * printf = m->getFunction("printf");
277    if (printf == nullptr) {
278        FunctionType * const fty = FunctionType::get(getInt32Ty(), {getInt8PtrTy()}, true);
279        printf = Function::Create(fty, Function::ExternalLinkage, "printf", m);
280        printf->addAttribute(1, Attribute::NoAlias);
281    }
282    return printf;
283}
284
285Function * CBuilder::GetDprintf() {
286    Module * const m = getModule();
287    Function * dprintf = m->getFunction("dprintf");
288    if (dprintf == nullptr) {
289        FunctionType * fty = FunctionType::get(getInt32Ty(), {getInt32Ty(), getInt8PtrTy()}, true);
290        dprintf = Function::Create(fty, Function::ExternalLinkage, "dprintf", m);
291    }
292    return dprintf;
293}
294
295void CBuilder::CallPrintIntCond(StringRef name, Value * const value, Value * const cond, const STD_FD fd) {
296    BasicBlock * const insertBefore = GetInsertBlock()->getNextNode();
297    BasicBlock* const callBlock = CreateBasicBlock("callBlock", insertBefore);
298    BasicBlock* const exitBlock = CreateBasicBlock("exitBlock", insertBefore);
299    CreateCondBr(cond, callBlock, exitBlock);
300    SetInsertPoint(callBlock);
301    CallPrintInt(name, value, fd);
302    CreateBr(exitBlock);
303    SetInsertPoint(exitBlock);
304}
305
306void CBuilder::CallPrintInt(StringRef name, Value * const value, const STD_FD fd) {
307    Module * const m = getModule();
308    Constant * printRegister = m->getFunction("print_int");
309    IntegerType * const int64Ty = getInt64Ty();
310    if (LLVM_UNLIKELY(printRegister == nullptr)) {
311        FunctionType *FT = FunctionType::get(getVoidTy(), { getInt32Ty(), getInt8PtrTy(), int64Ty }, false);
312        Function * function = Function::Create(FT, Function::InternalLinkage, "print_int", m);
313        auto arg = function->arg_begin();
314        BasicBlock * entry = BasicBlock::Create(getContext(), "entry", function);
315        IRBuilder<> builder(entry);
316        Value * const fdInt = &*(arg++);
317        fdInt->setName("fd");
318        Value * const name = &*(arg++);
319        name->setName("name");
320        Value * value = &*arg;
321        value->setName("value");
322        std::vector<Value *> args(4);
323        args[0] = fdInt;
324        args[1] = GetString("%-40s = %" PRIx64 "\n");
325        args[2] = name;
326        args[3] = value;
327        builder.CreateCall(GetDprintf(), args);
328        builder.CreateRetVoid();
329        printRegister = function;
330    }
331    Value * num = nullptr;
332    if (value->getType()->isPointerTy()) {
333        num = CreatePtrToInt(value, int64Ty);
334    } else {
335        num = CreateZExt(value, int64Ty);
336    }
337    assert (num->getType()->isIntegerTy());
338    CreateCall(printRegister, {getInt32(static_cast<uint32_t>(fd)), GetString(name), num});
339}
340
341Value * CBuilder::CreateMalloc(Value * size) {
342    Module * const m = getModule();
343    IntegerType * const sizeTy = getSizeTy();
344    Function * f = m->getFunction("malloc");
345    if (f == nullptr) {
346        PointerType * const voidPtrTy = getVoidPtrTy();
347        FunctionType * fty = FunctionType::get(voidPtrTy, {sizeTy}, false);
348        f = Function::Create(fty, Function::ExternalLinkage, "malloc", m);
349        f->setCallingConv(CallingConv::C);
350        f->setReturnDoesNotAlias();
351    }
352    size = CreateZExtOrTrunc(size, sizeTy);
353    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
354        CreateAssert(size, "CreateMalloc: 0-byte malloc is implementation defined");
355    }
356    CallInst * const ptr = CreateCall(f, size);
357    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
358        CreateAssert(ptr, "CreateMalloc: returned null pointer");
359    }
360    CreateMemZero(ptr, size, 1);
361    return ptr;
362}
363
364Value * CBuilder::CreateCacheAlignedMalloc(Type * const type, Value * const ArraySize, const unsigned addressSpace) {
365    Value * size = ConstantExpr::getSizeOf(type);
366    if (ArraySize) {
367        size = CreateMul(size, CreateZExtOrTrunc(ArraySize, size->getType()));
368    }
369    return CreatePointerCast(CreateCacheAlignedMalloc(size), type->getPointerTo(addressSpace));
370}
371
372Value * CBuilder::CreateAlignedMalloc(Value * size, const unsigned alignment) {
373    if (LLVM_UNLIKELY(!is_power_2(alignment))) {
374        report_fatal_error("CreateAlignedMalloc: alignment must be a power of 2");
375    }
376    Module * const m = getModule();
377    IntegerType * const sizeTy = getSizeTy();
378    PointerType * const voidPtrTy = getVoidPtrTy();
379    ConstantInt * const align = ConstantInt::get(sizeTy, alignment);
380    size = CreateZExtOrTrunc(size, sizeTy);
381    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
382        CreateAssert(size, "CreateAlignedMalloc: 0-byte malloc is implementation defined");
383        CreateAssertZero(CreateURem(size, align), "CreateAlignedMalloc: size must be an integral multiple of alignment.");
384    }
385    Value * ptr = nullptr;
386    if (hasAlignedAlloc()) {
387        Function * f = m->getFunction("aligned_alloc");
388        if (LLVM_UNLIKELY(f == nullptr)) {
389            FunctionType * const fty = FunctionType::get(voidPtrTy, {sizeTy, sizeTy}, false);
390            f = Function::Create(fty, Function::ExternalLinkage, "aligned_alloc", m);
391            f->setCallingConv(CallingConv::C);
392            f->setReturnDoesNotAlias();
393        }
394        ptr = CreateCall(f, {align, size});
395    } else if (hasPosixMemalign()) {
396        Function * f = m->getFunction("posix_memalign");
397        if (LLVM_UNLIKELY(f == nullptr)) {
398            FunctionType * const fty = FunctionType::get(getInt32Ty(), {voidPtrTy->getPointerTo(), sizeTy, sizeTy}, false);
399            f = Function::Create(fty, Function::ExternalLinkage, "posix_memalign", m);
400            f->setCallingConv(CallingConv::C);
401        }
402        Value * handle = CreateAlloca(voidPtrTy);
403        CallInst * success = CreateCall(f, {handle, align, size});
404        if (codegen::DebugOptionIsSet(codegen::EnableAsserts)) {
405            CreateAssertZero(success, "CreateAlignedMalloc: posix_memalign reported bad allocation");
406        }
407        ptr = CreateLoad(handle);
408    } else {
409        report_fatal_error("stdlib.h does not contain either aligned_alloc or posix_memalign");
410    }
411    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
412        CreateAssert(ptr, "CreateAlignedMalloc: returned null (out of memory?)");
413    }
414    CreateMemZero(ptr, size, alignment);
415    return ptr;
416}
417
418inline bool CBuilder::hasAlignedAlloc() const {
419    return mDriver && mDriver->hasExternalFunction("aligned_alloc");
420}
421
422
423inline bool CBuilder::hasPosixMemalign() const {
424    return mDriver && mDriver->hasExternalFunction("posix_memalign");
425}
426
427Value * CBuilder::CreateRealloc(llvm::Type * const type, llvm::Value * const base, llvm::Value * const ArraySize) {
428    Value * size = ConstantExpr::getSizeOf(type);
429    if (ArraySize) {
430        size = CreateMul(size, CreateZExtOrTrunc(ArraySize, size->getType()));
431    }
432    return CreatePointerCast(CreateRealloc(base, size), type->getPointerTo());
433}
434
435Value * CBuilder::CreateRealloc(Value * const base, Value * const size) {
436    assert ("Ptr is not a pointer type" && base->getType()->isPointerTy());
437    assert ("Size is not an integer" && size->getType()->isIntegerTy());
438    Module * const m = getModule();
439    IntegerType * const sizeTy = getSizeTy();
440    PointerType * const voidPtrTy = getVoidPtrTy();
441    Function * f = m->getFunction("realloc");
442    if (f == nullptr) {
443        FunctionType * fty = FunctionType::get(voidPtrTy, {voidPtrTy, sizeTy}, false);
444        f = Function::Create(fty, Function::ExternalLinkage, "realloc", m);
445        f->setCallingConv(CallingConv::C);
446        f->setReturnDoesNotAlias();
447        #if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
448        f->setDoesNotAlias(1);
449        #endif
450    }
451    CallInst * const ci = CreateCall(f, {CreatePointerCast(base, voidPtrTy), CreateZExtOrTrunc(size, sizeTy)});
452    return CreatePointerCast(ci, base->getType());
453}
454
455void CBuilder::CreateFree(Value * const ptr) {
456    assert (ptr->getType()->isPointerTy());
457    Module * const m = getModule();
458    Type * const voidPtrTy =  getVoidPtrTy();
459    Function * f = m->getFunction("free");
460    if (f == nullptr) {
461        FunctionType * fty = FunctionType::get(getVoidTy(), {voidPtrTy}, false);
462        f = Function::Create(fty, Function::ExternalLinkage, "free", m);
463        f->setCallingConv(CallingConv::C);
464    }
465    CreateCall(f, CreatePointerCast(ptr, voidPtrTy));
466}
467
468Value * CBuilder::CreateAnonymousMMap(Value * size) {
469    PointerType * const voidPtrTy = getVoidPtrTy();
470    IntegerType * const intTy = getInt32Ty();
471    IntegerType * const sizeTy = getSizeTy();
472    size = CreateZExtOrTrunc(size, sizeTy);
473    ConstantInt * const prot =  ConstantInt::get(intTy, PROT_READ | PROT_WRITE);
474    ConstantInt * const flags =  ConstantInt::get(intTy, MAP_PRIVATE | MAP_ANON);
475    ConstantInt * const fd =  ConstantInt::get(intTy, -1);
476    Constant * const offset = ConstantInt::get(sizeTy, 0);
477    return CreateMMap(ConstantPointerNull::getNullValue(voidPtrTy), size, prot, flags, fd, offset);
478}
479
480Value * CBuilder::CreateFileSourceMMap(Value * fd, Value * size) {
481    PointerType * const voidPtrTy = getVoidPtrTy();
482    IntegerType * const intTy = getInt32Ty();
483    fd = CreateZExtOrTrunc(fd, intTy);
484    IntegerType * const sizeTy = getSizeTy();
485    size = CreateZExtOrTrunc(size, sizeTy);
486    ConstantInt * const prot =  ConstantInt::get(intTy, PROT_READ);
487    ConstantInt * const flags =  ConstantInt::get(intTy, MAP_PRIVATE);
488    Constant * const offset = ConstantInt::get(sizeTy, 0);
489    return CreateMMap(ConstantPointerNull::getNullValue(voidPtrTy), size, prot, flags, fd, offset);
490}
491
492Value * CBuilder::CreateMMap(Value * const addr, Value * size, Value * const prot, Value * const flags, Value * const fd, Value * const offset) {
493    Module * const m = getModule();
494    Function * fMMap = m->getFunction("mmap");
495    if (LLVM_UNLIKELY(fMMap == nullptr)) {
496        PointerType * const voidPtrTy = getVoidPtrTy();
497        IntegerType * const intTy = getInt32Ty();
498        IntegerType * const sizeTy = getSizeTy();
499        FunctionType * fty = FunctionType::get(voidPtrTy, {voidPtrTy, sizeTy, intTy, intTy, intTy, sizeTy}, false);
500        fMMap = Function::Create(fty, Function::ExternalLinkage, "mmap", m);
501    }
502    Value * ptr = CreateCall(fMMap, {addr, size, prot, flags, fd, offset});
503    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
504        DataLayout DL(m);
505        IntegerType * const intTy = getIntPtrTy(DL);
506        Value * success = CreateICmpNE(CreatePtrToInt(addr, intTy), ConstantInt::getAllOnesValue(intTy)); // MAP_FAILED = -1
507        CreateAssert(success, "CreateMMap: mmap failed to allocate memory");
508    }
509    return ptr;
510}
511
512/**
513 * @brief CBuilder::CreateMAdvise
514 * @param addr
515 * @param length
516 * @param advice
517 *
518 * Note: this funcition can fail if a kernel resource was temporarily unavailable. Test if this is more than a simple hint and handle accordingly.
519 *
520 *  ADVICE_NORMAL
521 *      No special treatment. This is the default.
522 *  ADVICE_RANDOM
523 *      Expect page references in random order. (Hence, read ahead may be less useful than normally.)
524 *  ADVICE_SEQUENTIAL
525 *      Expect page references in sequential order. (Hence, pages in the given range can be aggressively read ahead, and may be freed
526 *      soon after they are accessed.)
527 *  ADVICE_WILLNEED
528 *      Expect access in the near future. (Hence, it might be a good idea to read some pages ahead.)
529 *  ADVICE_DONTNEED
530 *      Do not expect access in the near future. (For the time being, the application is finished with the given range, so the kernel
531 *      can free resources associated with it.) Subsequent accesses of pages in this range will succeed, but will result either in
532 *      reloading of the memory contents from the underlying mapped file (see mmap(2)) or zero-fill-on-demand pages for mappings
533 *      without an underlying file.
534 *
535 * @return Value indicating success (0) or failure (-1).
536 */
537Value * CBuilder::CreateMAdvise(Value * addr, Value * length, Advice advice) {
538    Triple T(mTriple);
539    Value * result = nullptr;
540    if (T.isOSLinux() || T.isOSDarwin()) {
541        Module * const m = getModule();
542        IntegerType * const intTy = getInt32Ty();
543        IntegerType * const sizeTy = getSizeTy();
544        PointerType * const voidPtrTy = getVoidPtrTy();
545        Function * MAdviseFunc = m->getFunction("madvise");
546        if (LLVM_UNLIKELY(MAdviseFunc == nullptr)) {
547            FunctionType * fty = FunctionType::get(intTy, {voidPtrTy, sizeTy, intTy}, false);
548            MAdviseFunc = Function::Create(fty, Function::ExternalLinkage, "madvise", m);
549        }
550        addr = CreatePointerCast(addr, voidPtrTy);
551        length = CreateZExtOrTrunc(length, sizeTy);
552        int madv_flag = 0;
553        switch (advice) {
554            case Advice::ADVICE_NORMAL:
555                madv_flag = MADV_NORMAL; break;
556            case Advice::ADVICE_RANDOM:
557                madv_flag = MADV_RANDOM; break;
558            case Advice::ADVICE_SEQUENTIAL:
559                madv_flag = MADV_SEQUENTIAL; break;
560            case Advice::ADVICE_WILLNEED:
561                madv_flag = MADV_WILLNEED; break;
562            case Advice::ADVICE_DONTNEED:
563                madv_flag = MADV_DONTNEED; break;
564        }
565        result = CreateCall(MAdviseFunc, {addr, length, ConstantInt::get(intTy, madv_flag)});
566    }
567    return result;
568}
569
570#ifndef MREMAP_MAYMOVE
571#define MREMAP_MAYMOVE  1
572#endif
573
574Value * CBuilder::CreateMRemap(Value * addr, Value * oldSize, Value * newSize) {
575    Triple T(mTriple);
576    Value * ptr = nullptr;
577    if (T.isOSLinux()) {
578        Module * const m = getModule();
579        DataLayout DL(m);
580        PointerType * const voidPtrTy = getVoidPtrTy();
581        IntegerType * const sizeTy = getSizeTy();
582        IntegerType * const intTy = getIntPtrTy(DL);
583        Function * fMRemap = m->getFunction("mremap");
584        if (LLVM_UNLIKELY(fMRemap == nullptr)) {
585            FunctionType * fty = FunctionType::get(voidPtrTy, {voidPtrTy, sizeTy, sizeTy, intTy}, false);
586            fMRemap = Function::Create(fty, Function::ExternalLinkage, "mremap", m);
587        }
588        addr = CreatePointerCast(addr, voidPtrTy);
589        oldSize = CreateZExtOrTrunc(oldSize, sizeTy);
590        newSize = CreateZExtOrTrunc(newSize, sizeTy);
591        ConstantInt * const flags = ConstantInt::get(intTy, MREMAP_MAYMOVE);
592        ptr = CreateCall(fMRemap, {addr, oldSize, newSize, flags});
593        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
594            Value * success = CreateICmpNE(CreatePtrToInt(addr, intTy), ConstantInt::getAllOnesValue(intTy)); // MAP_FAILED = -1
595            CreateAssert(success, "CreateMRemap: mremap failed to allocate memory");
596        }
597    } else { // no OS mremap support
598        ptr = CreateAnonymousMMap(newSize);
599        CreateMemCpy(ptr, addr, oldSize, getPageSize());
600        CreateMUnmap(addr, oldSize);
601    }
602    return ptr;
603}
604
605Value * CBuilder::CreateMUnmap(Value * addr, Value * len) {
606    IntegerType * const sizeTy = getSizeTy();
607    PointerType * const voidPtrTy = getVoidPtrTy();
608    Module * const m = getModule();
609    Function * munmapFunc = m->getFunction("munmap");
610    if (LLVM_UNLIKELY(munmapFunc == nullptr)) {
611        FunctionType * const fty = FunctionType::get(sizeTy, {voidPtrTy, sizeTy}, false);
612        munmapFunc = Function::Create(fty, Function::ExternalLinkage, "munmap", m);
613    }
614    len = CreateZExtOrTrunc(len, sizeTy);
615    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
616        DataLayout DL(getModule());
617        IntegerType * const intPtrTy = getIntPtrTy(DL);
618        CreateAssert(len, "CreateMUnmap: length cannot be 0");
619        Value * const addrValue = CreatePtrToInt(addr, intPtrTy);
620        Value * const pageOffset = CreateURem(addrValue, ConstantInt::get(intPtrTy, getPageSize()));
621        CreateAssertZero(pageOffset, "CreateMUnmap: addr must be a multiple of the page size");
622        Value * const boundCheck = CreateICmpULT(addrValue, CreateSub(ConstantInt::getAllOnesValue(intPtrTy), CreateZExtOrTrunc(len, intPtrTy)));
623        CreateAssert(boundCheck, "CreateMUnmap: addresses in [addr, addr+len) are outside the valid address space range");
624    }
625    addr = CreatePointerCast(addr, voidPtrTy);
626    return CreateCall(munmapFunc, {addr, len});
627}
628
629Value * CBuilder::CreateMProtect(Value * addr, Value * size, const Protect protect) {
630    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
631        // mprotect() changes the access protections for the calling process's
632        // memory pages containing any part of the address range in the interval
633        // [addr, addr+len-1].  addr must be aligned to a page boundary.
634
635        // mprotect(): POSIX.1-2001, POSIX.1-2008, SVr4.  POSIX says that the
636        // behavior of mprotect() is unspecified if it is applied to a region of
637        // memory that was not obtained via mmap(2).
638
639        // On Linux, it is always permissible to call mprotect() on any address
640        // in a process's address space (except for the kernel vsyscall area).
641        // In particular, it can be used to change existing code mappings to be
642        // writable. (NOTE: does not appear to be true on UBUNTU 16.04, 16.10 or 18.04)
643
644        DataLayout DL(getModule());
645        IntegerType * const intPtrTy = getIntPtrTy(DL);
646        Constant * const pageSize = ConstantInt::get(intPtrTy, getPageSize());
647        CreateAssertZero(CreateURem(CreatePtrToInt(addr, intPtrTy), pageSize), "CreateMProtect: addr must be aligned to page boundary");
648    }
649
650    IntegerType * const sizeTy = getSizeTy();
651    PointerType * const voidPtrTy = getVoidPtrTy();
652    IntegerType * const int32Ty = getInt32Ty();
653
654    Module * const m = getModule();
655    Function * mprotectFunc = m->getFunction("mprotect");
656    if (LLVM_UNLIKELY(mprotectFunc == nullptr)) {
657        FunctionType * const fty = FunctionType::get(sizeTy, {voidPtrTy, sizeTy, int32Ty}, false);
658        mprotectFunc = Function::Create(fty, Function::ExternalLinkage, "mprotect", m);
659    }
660    addr = CreatePointerCast(addr, voidPtrTy);
661    size = CreateZExtOrTrunc(size, sizeTy);
662    Value * const result = CreateCall(mprotectFunc, {addr, size, ConstantInt::get(int32Ty, (int)protect)});
663    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
664        CreateAssertZero(result, "CreateMProtect: could not change the permission of the given address range");
665    }
666    return result;
667}
668
669IntegerType * LLVM_READNONE CBuilder::getIntAddrTy() const {
670    return TypeBuilder<intptr_t, false>::get(getContext());
671}
672
673PointerType * LLVM_READNONE CBuilder::getVoidPtrTy(const unsigned AddressSpace) const {
674    //return PointerType::get(Type::getVoidTy(getContext()), AddressSpace);
675    return PointerType::get(Type::getInt8Ty(getContext()), AddressSpace);
676}
677
678LoadInst * CBuilder::CreateAtomicLoadAcquire(Value * ptr) {
679    const auto alignment = ptr->getType()->getPointerElementType()->getPrimitiveSizeInBits() / 8;
680    LoadInst * inst = CreateAlignedLoad(ptr, alignment);
681    inst->setOrdering(AtomicOrdering::Acquire);
682    return inst;
683
684}
685
686StoreInst * CBuilder::CreateAtomicStoreRelease(Value * val, Value * ptr) {
687    const auto alignment = ptr->getType()->getPointerElementType()->getPrimitiveSizeInBits() / 8;
688    StoreInst * inst = CreateAlignedStore(val, ptr, alignment);
689    inst->setOrdering(AtomicOrdering::Release);
690    return inst;
691}
692
693PointerType * LLVM_READNONE CBuilder::getFILEptrTy() {
694    if (mFILEtype == nullptr) {
695        mFILEtype = StructType::create(getContext(), "struct._IO_FILE");
696    }
697    return mFILEtype->getPointerTo();
698}
699
700Value * CBuilder::CreateFOpenCall(Value * filename, Value * mode) {
701    Module * const m = getModule();
702    Function * fOpenFunc = m->getFunction("fopen");
703    if (fOpenFunc == nullptr) {
704        FunctionType * fty = FunctionType::get(getFILEptrTy(), {getInt8Ty()->getPointerTo(), getInt8Ty()->getPointerTo()}, false);
705        fOpenFunc = Function::Create(fty, Function::ExternalLinkage, "fopen", m);
706        fOpenFunc->setCallingConv(CallingConv::C);
707    }
708    return CreateCall(fOpenFunc, {filename, mode});
709}
710
711Value * CBuilder::CreateFReadCall(Value * ptr, Value * size, Value * nitems, Value * stream) {
712    Module * const m = getModule();
713    Function * fReadFunc = m->getFunction("fread");
714    PointerType * const voidPtrTy = getVoidPtrTy();
715    if (fReadFunc == nullptr) {
716        IntegerType * const sizeTy = getSizeTy();
717        FunctionType * fty = FunctionType::get(sizeTy, {voidPtrTy, sizeTy, sizeTy, getFILEptrTy()}, false);
718        fReadFunc = Function::Create(fty, Function::ExternalLinkage, "fread", m);
719        fReadFunc->setCallingConv(CallingConv::C);
720    }
721    ptr = CreatePointerCast(ptr, voidPtrTy);
722    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
723        CHECK_ADDRESS(ptr, CreateMul(size, nitems), "CreateFReadCall");
724    }
725    return CreateCall(fReadFunc, {ptr, size, nitems, stream});
726}
727
728Value * CBuilder::CreateFWriteCall(Value * ptr, Value * size, Value * nitems, Value * stream) {
729    Module * const m = getModule();
730    Function * fWriteFunc = m->getFunction("fwrite");
731    PointerType * const voidPtrTy = getVoidPtrTy();
732    if (fWriteFunc == nullptr) {
733        IntegerType * const sizeTy = getSizeTy();
734        FunctionType * fty = FunctionType::get(sizeTy, {voidPtrTy, sizeTy, sizeTy, getFILEptrTy()}, false);
735        fWriteFunc = Function::Create(fty, Function::ExternalLinkage, "fwrite", m);
736        fWriteFunc->setCallingConv(CallingConv::C);
737    }
738    ptr = CreatePointerCast(ptr, voidPtrTy);
739    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
740        CHECK_ADDRESS(ptr, CreateMul(size, nitems), "CreateFReadCall");
741    }
742    return CreateCall(fWriteFunc, {ptr, size, nitems, stream});
743}
744
745Value * CBuilder::CreateFCloseCall(Value * stream) {
746    Module * const m = getModule();
747    Function * fCloseFunc = m->getFunction("fclose");
748    if (fCloseFunc == nullptr) {
749        FunctionType * fty = FunctionType::get(getInt32Ty(), {getFILEptrTy()}, false);
750        fCloseFunc = Function::Create(fty, Function::ExternalLinkage, "fclose", m);
751        fCloseFunc->setCallingConv(CallingConv::C);
752    }
753    return CreateCall(fCloseFunc, {stream});
754}
755
756Value * CBuilder::CreateRenameCall(Value * oldName, Value * newName) {
757    Module * const m = getModule();
758    Function * renameFunc = m->getFunction("rename");
759    if (renameFunc == nullptr) {
760        FunctionType * fty = FunctionType::get(getInt32Ty(), {getInt8PtrTy(), getInt8PtrTy()}, false);
761        renameFunc = Function::Create(fty, Function::ExternalLinkage, "rename", m);
762        renameFunc->setCallingConv(CallingConv::C);
763    }
764    return CreateCall(renameFunc, {oldName, newName});
765}
766
767Value * CBuilder::CreateRemoveCall(Value * path) {
768    Module * const m = getModule();
769    Function * removeFunc = m->getFunction("remove");
770    if (removeFunc == nullptr) {
771        FunctionType * fty = FunctionType::get(getInt32Ty(), {getInt8PtrTy()}, false);
772        removeFunc = Function::Create(fty, Function::ExternalLinkage, "remove", m);
773        removeFunc->setCallingConv(CallingConv::C);
774    }
775    return CreateCall(removeFunc, {path});
776}
777
778Value * CBuilder::CreatePThreadCreateCall(Value * thread, Value * attr, Function * start_routine, Value * arg) {
779    Module * const m = getModule();
780    Type * const voidPtrTy = getVoidPtrTy();
781    Function * pthreadCreateFunc = m->getFunction("pthread_create");
782    if (pthreadCreateFunc == nullptr) {
783        Type * pthreadTy = getSizeTy();
784        FunctionType * funVoidPtrVoidTy = FunctionType::get(getVoidTy(), {voidPtrTy}, false);
785        FunctionType * fty = FunctionType::get(getInt32Ty(), {pthreadTy->getPointerTo(), voidPtrTy, funVoidPtrVoidTy->getPointerTo(), voidPtrTy}, false);
786        pthreadCreateFunc = Function::Create(fty, Function::ExternalLinkage, "pthread_create", m);
787        pthreadCreateFunc->setCallingConv(CallingConv::C);
788    }
789    assert (thread->getType()->isPointerTy());
790    return CreateCall(pthreadCreateFunc, {thread, attr, start_routine, CreatePointerCast(arg, voidPtrTy)});
791}
792
793Value * CBuilder::CreatePThreadYield() {
794    Module * const m = getModule();
795    Function * f = m->getFunction("pthread_yield");
796    if (f == nullptr) {
797        FunctionType * fty = FunctionType::get(getInt32Ty(), false);
798        f = Function::Create(fty, Function::ExternalLinkage, "pthread_yield", m);
799        f->setCallingConv(CallingConv::C);
800    }
801    return CreateCall(f);
802}
803
804Value * CBuilder::CreatePThreadExitCall(Value * value_ptr) {
805    Module * const m = getModule();
806    Function * pthreadExitFunc = m->getFunction("pthread_exit");
807    if (pthreadExitFunc == nullptr) {
808        FunctionType * fty = FunctionType::get(getVoidTy(), {getVoidPtrTy()}, false);
809        pthreadExitFunc = Function::Create(fty, Function::ExternalLinkage, "pthread_exit", m);
810        pthreadExitFunc->addFnAttr(Attribute::NoReturn);
811        pthreadExitFunc->setCallingConv(CallingConv::C);
812    }
813    CallInst * exitThread = CreateCall(pthreadExitFunc, {value_ptr});
814    exitThread->setDoesNotReturn();
815    return exitThread;
816}
817
818Value * CBuilder::CreatePThreadJoinCall(Value * thread, Value * value_ptr){
819    Module * const m = getModule();
820    Function * pthreadJoinFunc = m->getFunction("pthread_join");
821    if (pthreadJoinFunc == nullptr) {
822        FunctionType * fty = FunctionType::get(getInt32Ty(), {getSizeTy(), getVoidPtrTy()->getPointerTo()}, false);
823        pthreadJoinFunc = Function::Create(fty, Function::ExternalLinkage, "pthread_join", m);
824        pthreadJoinFunc->setCallingConv(CallingConv::C);
825    }
826    return CreateCall(pthreadJoinFunc, {thread, value_ptr});
827}
828
829void __report_failure(const char * name, const char * msg, const uintptr_t * trace, const uint32_t n) {
830    // TODO: look into boost stacktrace, available from version 1.65
831    raw_fd_ostream out(STDERR_FILENO, false);
832    if (trace) {
833        SmallVector<char, 4096> tmp;
834        raw_svector_ostream trace_string(tmp);
835        for (uint32_t i = 0; i < n; ++i) {
836            const auto pc = trace[i];
837            trace_string << format_hex(pc, 16) << "   ";
838            #ifdef __APPLE__
839            const auto translator = "atos -o %s %p";
840            #else
841            const auto translator = "addr2line -fpCe %s %p";
842            #endif
843            const auto cmd = boost::format(translator) % codegen::ProgramName.data() % pc;
844            FILE * const f = popen(cmd.str().data(), "r");
845            if (f) {
846                char buffer[1024] = {0};
847                while(fgets(buffer, sizeof(buffer), f)) {
848                    trace_string << buffer;
849                }
850                pclose(f);
851            } else { // TODO: internal default
852
853
854            }
855        }
856        out.changeColor(raw_fd_ostream::WHITE, true);
857        out << "Compilation Stacktrace:\n";
858        out.resetColor();
859        out << trace_string.str();
860    }
861    if (name) {
862        out.changeColor(raw_fd_ostream::RED, true);
863        out << name << ": ";
864    }
865    out.changeColor(raw_fd_ostream::WHITE, true);
866    out << msg << "\n";
867    if (trace == nullptr) {
868        out.changeColor(raw_fd_ostream::WHITE, true);
869        out << "No debug symbols loaded.\n";
870    }
871    out.resetColor();
872    out.flush();
873
874}
875
876#if defined(HAS_MACH_VM_TYPES)
877
878/*
879 * Copyright (c) 1999, 2007 Apple Inc. All rights reserved.
880 *
881 * @APPLE_LICENSE_HEADER_START@
882 *
883 * This file contains Original Code and/or Modifications of Original Code
884 * as defined in and that are subject to the Apple Public Source License
885 * Version 2.0 (the 'License'). You may not use this file except in
886 * compliance with the License. Please obtain a copy of the License at
887 * http://www.opensource.apple.com/apsl/ and read it before using this
888 * file.
889 *
890 * The Original Code and all software distributed under the License are
891 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
892 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
893 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
894 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
895 * Please see the License for the specific language governing rights and
896 * limitations under the License.
897 *
898 * @APPLE_LICENSE_HEADER_END@
899 */
900
901#include <pthread.h>
902#include <mach/mach.h>
903#include <mach/vm_statistics.h>
904#include <stdlib.h>
905
906#if defined(__i386__) || defined(__x86_64__)
907#define FP_LINK_OFFSET 1
908#elif defined(__ppc__) || defined(__ppc64__)
909#define FP_LINK_OFFSET 2
910#else
911#error  ********** Unimplemented architecture
912#endif
913
914#define INSTACK(a)      ((uintptr_t)(a) >= stackbot && (uintptr_t)(a) <= stacktop)
915#if defined(__ppc__) || defined(__ppc64__) || defined(__x86_64__)
916#define ISALIGNED(a)    ((((uintptr_t)(a)) & 0xf) == 0)
917#elif defined(__i386__)
918#define ISALIGNED(a)    ((((uintptr_t)(a)) & 0xf) == 8)
919#endif
920
921__private_extern__  __attribute__((noinline))
922void
923_thread_stack_pcs(vm_address_t *buffer, unsigned max, unsigned *nb, unsigned skip)
924{
925    void *frame, *next;
926    pthread_t self = pthread_self();
927    uintptr_t stacktop = (uintptr_t)(pthread_get_stackaddr_np(self));
928    uintptr_t stackbot = stacktop - (uintptr_t)(pthread_get_stacksize_np(self));
929
930    *nb = 0;
931
932    /* make sure return address is never out of bounds */
933    stacktop -= (FP_LINK_OFFSET + 1) * sizeof(void *);
934
935    /*
936     * The original implementation called the first_frame_address() function,
937     * which returned the stack frame pointer.  The problem was that in ppc,
938     * it was a leaf function, so no new stack frame was set up with
939     * optimization turned on (while a new stack frame was set up without
940     * optimization).  We now inline the code to get the stack frame pointer,
941     * so we are consistent about the stack frame.
942     */
943#if defined(__i386__) || defined(__x86_64__)
944    frame = __builtin_frame_address(0);
945#elif defined(__ppc__) || defined(__ppc64__)
946    /* __builtin_frame_address IS BROKEN IN BEAKER: RADAR #2340421 */
947    __asm__ volatile("mr %0, r1" : "=r" (frame));
948#endif
949    if(!INSTACK(frame) || !ISALIGNED(frame))
950        return;
951#if defined(__ppc__) || defined(__ppc64__)
952    /* back up the stack pointer up over the current stack frame */
953    next = *(void **)frame;
954    if(!INSTACK(next) || !ISALIGNED(next) || next <= frame)
955        return;
956    frame = next;
957#endif
958    while (skip--) {
959        next = *(void **)frame;
960        if(!INSTACK(next) || !ISALIGNED(next) || next <= frame)
961            return;
962        frame = next;
963    }
964    while (max--) {
965        buffer[*nb] = *(vm_address_t *)(((void **)frame) + FP_LINK_OFFSET);
966        (*nb)++;
967        next = *(void **)frame;
968        if(!INSTACK(next) || !ISALIGNED(next) || next <= frame)
969            return;
970        frame = next;
971    }
972}
973#endif
974
975void CBuilder::__CreateAssert(Value * const assertion, const Twine & failureMessage) {
976    if (LLVM_UNLIKELY(isa<Constant>(assertion))) {
977        if (LLVM_UNLIKELY(cast<Constant>(assertion)->isNullValue())) {
978            report_fatal_error(failureMessage);
979        }
980    } else if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
981        Module * const m = getModule();
982        Type * const stackTy = TypeBuilder<uintptr_t, false>::get(getContext());
983        PointerType * const stackPtrTy = stackTy->getPointerTo();
984        PointerType * const int8PtrTy = getInt8PtrTy();
985        Function * function = m->getFunction("assert");
986        if (LLVM_UNLIKELY(function == nullptr)) {
987            auto ip = saveIP();
988            IntegerType * const int1Ty = getInt1Ty();
989            FunctionType * fty = FunctionType::get(getVoidTy(), { int1Ty, int8PtrTy, int8PtrTy, stackPtrTy, getInt32Ty() }, false);
990            function = Function::Create(fty, Function::PrivateLinkage, "assert", m);
991            function->setDoesNotThrow();
992            #if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
993            function->setDoesNotAlias(2);
994            #endif
995            BasicBlock * const entry = BasicBlock::Create(getContext(), "", function);
996            BasicBlock * const failure = BasicBlock::Create(getContext(), "", function);
997            BasicBlock * const success = BasicBlock::Create(getContext(), "", function);
998            auto arg = function->arg_begin();
999            arg->setName("assertion");
1000            Value * assertion = &*arg++;
1001            arg->setName("name");
1002            Value * name = &*arg++;
1003            arg->setName("msg");
1004            Value * msg = &*arg++;
1005            arg->setName("trace");
1006            Value * trace = &*arg++;
1007            arg->setName("depth");
1008            Value * depth = &*arg++;
1009            SetInsertPoint(entry);
1010            IRBuilder<>::CreateCondBr(assertion, success, failure);
1011            IRBuilder<>::SetInsertPoint(failure);
1012            IRBuilder<>::CreateCall(LinkFunction("__report_failure", __report_failure), { name, msg, trace, depth });
1013            CreateExit(-1);
1014            IRBuilder<>::CreateBr(success); // necessary to satisfy the LLVM verifier. this is never executed.
1015            SetInsertPoint(success);
1016            IRBuilder<>::CreateRetVoid();
1017            restoreIP(ip);
1018        }
1019        #ifndef NDEBUG
1020        SmallVector<unw_word_t, 64> stack;
1021        #if defined(HAS_MACH_VM_TYPES)
1022        for (;;) {
1023            unsigned int n;
1024            _thread_stack_pcs(reinterpret_cast<vm_address_t *>(stack.data()), stack.capacity(), &n, 1);
1025            if (LLVM_UNLIKELY(n < stack.capacity() || stack[n - 1] == 0)) {
1026                while (n >= 1 && stack[n - 1] == 0) {
1027                    n -= 1;
1028                }
1029                stack.set_size(n);
1030                break;
1031            }
1032            stack.reserve(n * 2);
1033        }
1034        #elif defined(HAS_LIBUNWIND)
1035        unw_context_t context;
1036        // Initialize cursor to current frame for local unwinding.
1037        unw_getcontext(&context);
1038        unw_cursor_t cursor;
1039        unw_init_local(&cursor, &context);
1040        // Unwind frames one by one, going up the frame stack.
1041        while (unw_step(&cursor) > 0) {
1042            unw_word_t pc;
1043            unw_get_reg(&cursor, UNW_REG_IP, &pc);
1044            if (pc == 0) {
1045                break;
1046            }
1047            stack.push_back(pc);
1048        }
1049        #elif defined(HAS_EXECINFO)
1050        for (;;) {
1051            const auto n = backtrace(reinterpret_cast<void **>(stack.data()), stack.capacity());
1052            if (LLVM_LIKELY(n < (int)stack.capacity())) {
1053                stack.set_size(n);
1054                break;
1055            }
1056            stack.reserve(n * 2);
1057        }
1058        #endif
1059        // TODO: look into how to safely use __builtin_return_address(0)?
1060
1061
1062        const unsigned FIRST_NON_ASSERT = 2;
1063        Value * trace = nullptr;
1064        ConstantInt * depth = nullptr;
1065        if (LLVM_UNLIKELY(stack.size() < FIRST_NON_ASSERT)) {
1066            trace = ConstantPointerNull::get(stackPtrTy);
1067            depth = getInt32(0);
1068        } else {
1069            const auto n = stack.size() - FIRST_NON_ASSERT;
1070            for (GlobalVariable & gv : m->getGlobalList()) {
1071                Type * const ty = gv.getValueType();
1072                if (ty->isArrayTy() && ty->getArrayElementType() == stackTy && ty->getArrayNumElements() == n) {
1073                    const ConstantDataArray * const array = cast<ConstantDataArray>(gv.getOperand(0));
1074                    bool found = true;
1075                    for (size_t i = 0; i < n; ++i) {
1076                        if (LLVM_LIKELY(array->getElementAsInteger(i) != stack[i + FIRST_NON_ASSERT])) {
1077                            found = false;
1078                            break;
1079                        }
1080                    }
1081                    if (LLVM_UNLIKELY(found)) {
1082                        trace = &gv;
1083                        break;
1084                    }
1085                }
1086            }
1087            if (LLVM_LIKELY(trace == nullptr)) {
1088                Constant * const initializer = ConstantDataArray::get(getContext(), ArrayRef<unw_word_t>(stack.data() + FIRST_NON_ASSERT, n));
1089                trace = new GlobalVariable(*m, initializer->getType(), true, GlobalVariable::InternalLinkage, initializer);
1090            }
1091            trace = CreatePointerCast(trace, stackPtrTy);
1092            depth = getInt32(n);
1093        }
1094        #else
1095        Value * trace = ConstantPointerNull::get(stackPtrTy);
1096        Value * depth = getInt32(0);
1097        #endif
1098        Value * const name = GetString(getKernelName());
1099        SmallVector<char, 1024> tmp;
1100        Value * const msg = GetString(failureMessage.toStringRef(tmp));
1101        IRBuilder<>::CreateCall(function, {assertion, name, msg, trace, depth});
1102    } else { // if assertions are not enabled, make it a compiler assumption.
1103
1104        // INVESTIGATE: while interesting, this does not seem to produce faster code and only provides a trivial
1105        // reduction of compiled code size in LLVM 3.8 but nearly doubles JIT compilation time. This may have been
1106        // improved with later versions of LLVM but it's likely that assumptions ought to be hand placed once
1107        // they're proven to improve performance.
1108
1109        // IRBuilder<>::CreateAssumption(assertion);
1110    }
1111}
1112
1113void CBuilder::CreateExit(const int exitCode) {
1114    Module * const m = getModule();
1115    Function * exit = m->getFunction("exit");
1116    if (LLVM_UNLIKELY(exit == nullptr)) {
1117        FunctionType * fty = FunctionType::get(getVoidTy(), {getInt32Ty()}, false);
1118        exit = Function::Create(fty, Function::ExternalLinkage, "exit", m);
1119        exit->setDoesNotReturn();
1120        exit->setDoesNotThrow();
1121    }
1122    CreateCall(exit, getInt32(exitCode));
1123}
1124
1125BasicBlock * CBuilder::CreateBasicBlock(const StringRef name, BasicBlock * insertBefore) {
1126    return BasicBlock::Create(getContext(), name, GetInsertBlock()->getParent(), insertBefore);
1127}
1128
1129bool CBuilder::supportsIndirectBr() const {
1130    return !codegen::DebugOptionIsSet(codegen::DisableIndirectBranch);
1131}
1132
1133BranchInst * CBuilder::CreateLikelyCondBr(Value * Cond, BasicBlock * True, BasicBlock * False, const int probability) {
1134    MDBuilder mdb(getContext());
1135    if (probability < 0 || probability > 100) {
1136        report_fatal_error("branch weight probability must be in [0,100]");
1137    }
1138    return CreateCondBr(Cond, True, False, mdb.createBranchWeights(probability, 100 - probability));
1139}
1140
1141Value * CBuilder::CreatePopcount(Value * bits) {
1142    Value * ctpopFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::ctpop, bits->getType());
1143    return CreateCall(ctpopFunc, bits);
1144}
1145
1146Value * CBuilder::CreateCountForwardZeroes(Value * value, const bool guaranteedNonZero) {
1147    if (LLVM_UNLIKELY(guaranteedNonZero && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1148        CreateAssert(value, "CreateCountForwardZeroes: value cannot be zero!");
1149    }
1150    Value * cttzFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::cttz, value->getType());
1151    return CreateCall(cttzFunc, {value, getInt1(guaranteedNonZero)});
1152}
1153
1154Value * CBuilder::CreateCountReverseZeroes(Value * value, const bool guaranteedNonZero) {
1155    if (LLVM_UNLIKELY(guaranteedNonZero && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1156        CreateAssert(value, "CreateCountReverseZeroes: value cannot be zero!");
1157    }
1158    Value * ctlzFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::ctlz, value->getType());
1159    return CreateCall(ctlzFunc, {value, getInt1(guaranteedNonZero)});
1160}
1161
1162Value * CBuilder::CreateResetLowestBit(Value * bits) {
1163    return CreateAnd(bits, CreateSub(bits, ConstantInt::get(bits->getType(), 1)));
1164}
1165
1166Value * CBuilder::CreateIsolateLowestBit(Value * bits) {
1167    return CreateAnd(bits, CreateNeg(bits));
1168}
1169
1170Value * CBuilder::CreateMaskToLowestBitInclusive(Value * bits) {
1171    return CreateXor(bits, CreateSub(bits, ConstantInt::get(bits->getType(), 1)));
1172}
1173
1174Value * CBuilder::CreateMaskToLowestBitExclusive(Value * bits) {
1175    return CreateAnd(CreateSub(bits, ConstantInt::get(bits->getType(), 1)), CreateNot(bits));
1176}
1177
1178Value * CBuilder::CreateExtractBitField(Value * bits, Value * start, Value * length) {
1179    Constant * One = ConstantInt::get(bits->getType(), 1);
1180    return CreateAnd(CreateLShr(bits, start), CreateSub(CreateShl(One, length), One));
1181}
1182
1183Value * CBuilder::CreateCeilLog2(Value * value) {
1184    IntegerType * ty = cast<IntegerType>(value->getType());
1185    Value * m = CreateCountReverseZeroes(CreateSub(value, ConstantInt::get(ty, 1)));
1186    return CreateSub(ConstantInt::get(m->getType(), ty->getBitWidth()), m);
1187}
1188
1189Value * CBuilder::GetString(StringRef Str) {
1190    Module * const m = getModule();
1191    Value * ptr = m->getGlobalVariable(Str, true);
1192    if (ptr == nullptr) {
1193        ptr = CreateGlobalString(Str, Str);
1194    }
1195    Value * zero = getInt32(0);
1196    return CreateInBoundsGEP(ptr, { zero, zero });
1197}
1198
1199Value * CBuilder::CreateReadCycleCounter() {
1200    Module * const m = getModule();
1201    Value * cycleCountFunc = Intrinsic::getDeclaration(m, Intrinsic::readcyclecounter);
1202    return CreateCall(cycleCountFunc, std::vector<Value *>({}));
1203}
1204
1205Function * CBuilder::LinkFunction(StringRef name, FunctionType * type, void * functionPtr) const {
1206    assert (mDriver);
1207    return mDriver->addLinkFunction(getModule(), name, type, functionPtr);
1208}
1209
1210LoadInst * CBuilder::CreateLoad(Value *Ptr, const char * Name) {
1211    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1212        CHECK_ADDRESS(Ptr, ConstantExpr::getSizeOf(Ptr->getType()->getPointerElementType()), "CreateLoad");
1213    }
1214    return IRBuilder<>::CreateLoad(Ptr, Name);
1215}
1216
1217LoadInst * CBuilder::CreateLoad(Value * Ptr, const Twine & Name) {
1218    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1219        CHECK_ADDRESS(Ptr, ConstantExpr::getSizeOf(Ptr->getType()->getPointerElementType()), "CreateLoad");
1220    }
1221    return IRBuilder<>::CreateLoad(Ptr, Name);
1222}
1223
1224LoadInst * CBuilder::CreateLoad(Type * Ty, Value *Ptr, const Twine & Name) {
1225    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1226        CHECK_ADDRESS(Ptr, ConstantExpr::getSizeOf(Ty), "CreateLoad");
1227    }
1228    return IRBuilder<>::CreateLoad(Ty, Ptr, Name);
1229}
1230
1231LoadInst * CBuilder::CreateLoad(Value * Ptr, bool isVolatile, const Twine & Name) {
1232    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1233        CHECK_ADDRESS(Ptr, ConstantExpr::getSizeOf(Ptr->getType()->getPointerElementType()), "CreateLoad");
1234    }
1235    return IRBuilder<>::CreateLoad(Ptr, isVolatile, Name);
1236}
1237
1238StoreInst * CBuilder::CreateStore(Value * Val, Value * Ptr, bool isVolatile) {
1239    assert ("Ptr is not a pointer type for Val" &&
1240            Ptr->getType()->isPointerTy() && Val->getType() == Ptr->getType()->getPointerElementType());
1241    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1242        CHECK_ADDRESS(Ptr, ConstantExpr::getSizeOf(Val->getType()), "CreateStore");
1243    }
1244    return IRBuilder<>::CreateStore(Val, Ptr, isVolatile);
1245}
1246
1247inline bool CBuilder::hasAddressSanitizer() const {
1248    return mDriver && mDriver->hasExternalFunction("__asan_region_is_poisoned");
1249}
1250
1251LoadInst * CBuilder::CreateAlignedLoad(Value * Ptr, unsigned Align, const char * Name) {
1252    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1253        DataLayout DL(getModule());
1254        IntegerType * const intPtrTy = cast<IntegerType>(DL.getIntPtrType(Ptr->getType()));
1255        Value * alignmentOffset = CreateURem(CreatePtrToInt(Ptr, intPtrTy), ConstantInt::get(intPtrTy, Align));
1256        CreateAssertZero(alignmentOffset, "CreateAlignedLoad: pointer is misaligned");
1257    }
1258    LoadInst * LI = CreateLoad(Ptr, Name);
1259    LI->setAlignment(Align);
1260    return LI;
1261}
1262
1263LoadInst * CBuilder::CreateAlignedLoad(Value * Ptr, unsigned Align, const Twine & Name) {
1264    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1265        DataLayout DL(getModule());
1266        IntegerType * const intPtrTy = cast<IntegerType>(DL.getIntPtrType(Ptr->getType()));
1267        Value * alignmentOffset = CreateURem(CreatePtrToInt(Ptr, intPtrTy), ConstantInt::get(intPtrTy, Align));
1268        CreateAssertZero(alignmentOffset, "CreateAlignedLoad: pointer is misaligned");
1269    }
1270    LoadInst * LI = CreateLoad(Ptr, Name);
1271    LI->setAlignment(Align);
1272    return LI;
1273}
1274
1275LoadInst * CBuilder::CreateAlignedLoad(Value * Ptr, unsigned Align, bool isVolatile, const Twine & Name) {
1276    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1277        DataLayout DL(getModule());
1278        IntegerType * const intPtrTy = cast<IntegerType>(DL.getIntPtrType(Ptr->getType()));
1279        Value * alignmentOffset = CreateURem(CreatePtrToInt(Ptr, intPtrTy), ConstantInt::get(intPtrTy, Align));
1280        CreateAssertZero(alignmentOffset, "CreateAlignedLoad: pointer is misaligned");
1281    }
1282    LoadInst * LI = CreateLoad(Ptr, isVolatile, Name);
1283    LI->setAlignment(Align);
1284    return LI;
1285}
1286
1287StoreInst * CBuilder::CreateAlignedStore(Value * Val, Value * Ptr, unsigned Align, bool isVolatile) {
1288    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1289        DataLayout DL(getModule());
1290        IntegerType * const intPtrTy = cast<IntegerType>(DL.getIntPtrType(Ptr->getType()));
1291        Value * alignmentOffset = CreateURem(CreatePtrToInt(Ptr, intPtrTy), ConstantInt::get(intPtrTy, Align));
1292        CreateAssertZero(alignmentOffset, "CreateAlignedStore: pointer is misaligned");
1293    }
1294    StoreInst *SI = CreateStore(Val, Ptr, isVolatile);
1295    SI->setAlignment(Align);
1296    return SI;
1297}
1298
1299Value * CBuilder::CreateMemChr(Value * ptr, Value * byteVal, Value * num) {
1300    Module * const m = getModule();
1301    Function * memchrFn = m->getFunction("memchr");
1302    if (memchrFn == nullptr) {
1303        IntegerType * const int32Ty = getInt32Ty();
1304        IntegerType * const sizeTy = getSizeTy();
1305        PointerType * const voidPtrTy = getVoidPtrTy();
1306        memchrFn = cast<Function>(m->getOrInsertFunction("memchr",
1307                                                         voidPtrTy, voidPtrTy, int32Ty, sizeTy, nullptr));
1308    }
1309    return CreateCall(memchrFn, {ptr, byteVal, num});
1310}
1311
1312CallInst * CBuilder::CreateMemMove(Value * Dst, Value * Src, Value *Size, unsigned Align, bool isVolatile,
1313                                   MDNode *TBAATag, MDNode *ScopeTag, MDNode *NoAliasTag) {
1314    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1315        CHECK_ADDRESS(Src, Size, "CreateMemMove: Src");
1316        CHECK_ADDRESS(Dst, Size, "CreateMemMove: Dst");
1317        // If the call to this intrinisic has an alignment value that is not 0 or 1, then the caller
1318        // guarantees that both the source and destination pointers are aligned to that boundary.
1319        if (Align > 1) {
1320            DataLayout DL(getModule());
1321            IntegerType * const intPtrTy = DL.getIntPtrType(getContext());
1322            Value * intSrc = CreatePtrToInt(Src, intPtrTy);
1323            Value * intDst = CreatePtrToInt(Dst, intPtrTy);
1324            ConstantInt * align = ConstantInt::get(intPtrTy, Align);
1325            CreateAssertZero(CreateURem(intSrc, align), "CreateMemMove: Src pointer is misaligned");
1326            CreateAssertZero(CreateURem(intDst, align), "CreateMemMove: Dst pointer is misaligned");
1327
1328        }
1329    }
1330    return IRBuilder<>::CreateMemMove(Dst, Src, Size, Align, isVolatile, TBAATag, ScopeTag, NoAliasTag);
1331}
1332
1333CallInst * CBuilder::CreateMemCpy(Value *Dst, Value *Src, Value *Size, unsigned Align, bool isVolatile,
1334                                  MDNode *TBAATag, MDNode *TBAAStructTag, MDNode *ScopeTag, MDNode *NoAliasTag) {
1335    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1336        CHECK_ADDRESS(Src, Size, "CreateMemCpy: Src");
1337        CHECK_ADDRESS(Dst, Size, "CreateMemCpy: Dst");
1338        DataLayout DL(getModule());
1339        IntegerType * const intPtrTy = DL.getIntPtrType(getContext());
1340        Value * intSrc = CreatePtrToInt(Src, intPtrTy);
1341        Value * intDst = CreatePtrToInt(Dst, intPtrTy);
1342        // If the call to this intrinisic has an alignment value that is not 0 or 1, then the caller
1343        // guarantees that both the source and destination pointers are aligned to that boundary.
1344        if (Align > 1) {
1345            ConstantInt * align = ConstantInt::get(intPtrTy, Align);
1346            CreateAssertZero(CreateURem(intSrc, align), "CreateMemCpy: Src is misaligned");
1347            CreateAssertZero(CreateURem(intDst, align), "CreateMemCpy: Dst is misaligned");
1348        }
1349        Value * intSize = CreateZExtOrTrunc(Size, intPtrTy);
1350        Value * nonOverlapping = CreateOr(CreateICmpULT(CreateAdd(intSrc, intSize), intDst),
1351                                          CreateICmpULT(CreateAdd(intDst, intSize), intSrc));
1352        CreateAssert(nonOverlapping, "CreateMemCpy: overlapping ranges is undefined");
1353    }
1354    return IRBuilder<>::CreateMemCpy(Dst, Src, Size, Align, isVolatile, TBAATag, TBAAStructTag, ScopeTag, NoAliasTag);
1355}
1356
1357CallInst * CBuilder::CreateMemSet(Value * Ptr, Value * Val, Value * Size, unsigned Align,
1358                       bool isVolatile, MDNode * TBAATag, MDNode * ScopeTag, MDNode * NoAliasTag) {
1359    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1360        CHECK_ADDRESS(Ptr, Size, "CreateMemSet");
1361        if (Align > 1) {
1362            DataLayout DL(getModule());
1363            IntegerType * const intPtrTy = DL.getIntPtrType(getContext());
1364            Value * intPtr = CreatePtrToInt(Ptr, intPtrTy);
1365            ConstantInt * align = ConstantInt::get(intPtrTy, Align);
1366            CreateAssertZero(CreateURem(intPtr, align), "CreateMemSet: Ptr is misaligned");
1367        }
1368    }
1369    return IRBuilder<>::CreateMemSet(Ptr, Val, Size, Align, isVolatile, TBAATag, ScopeTag, NoAliasTag);
1370}
1371
1372CallInst * CBuilder::CreateMemCmp(Value * Ptr1, Value * Ptr2, Value * Num) {
1373    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1374        CHECK_ADDRESS(Ptr1, Num, "CreateMemCmp: Ptr1");
1375        CHECK_ADDRESS(Ptr2, Num, "CreateMemCmp: Ptr2");
1376    }
1377    Module * const m = getModule();
1378    Function * f = m->getFunction("memcmp");
1379    PointerType * const voidPtrTy = getVoidPtrTy();
1380    IntegerType * const sizeTy = getSizeTy();
1381    if (f == nullptr) {
1382        FunctionType * const fty = FunctionType::get(getInt32Ty(), {voidPtrTy, voidPtrTy, sizeTy}, false);
1383        f = Function::Create(fty, Function::ExternalLinkage, "memcmp", m);
1384        f->setCallingConv(CallingConv::C);
1385        #if LLVM_VERSION_INTEGER < LLVM_VERSION_CODE(5, 0, 0)
1386        f->setDoesNotAlias(1);
1387        f->setDoesNotAlias(2);
1388        #endif
1389    }
1390    Ptr1 = CreatePointerCast(Ptr1, voidPtrTy);
1391    Ptr2 = CreatePointerCast(Ptr2, voidPtrTy);
1392    Num = CreateZExtOrTrunc(Num, sizeTy);
1393    return CreateCall(f, {Ptr1, Ptr2, Num});
1394}
1395
1396Value * CBuilder::CreateExtractElement(Value * Vec, Value *Idx, const Twine & Name) {
1397    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1398        if (LLVM_UNLIKELY(!Vec->getType()->isVectorTy())) {
1399            report_fatal_error("CreateExtractElement: Vec argument is not a vector type");
1400        }
1401        Constant * const Size = ConstantInt::get(Idx->getType(), Vec->getType()->getVectorNumElements());
1402        // exctracting an element from a position that exceeds the length of the vector is undefined
1403        CreateAssert(CreateICmpULT(Idx, Size), "CreateExtractElement: Idx is greater than Vec size");
1404    }
1405    return IRBuilder<>::CreateExtractElement(Vec, Idx, Name);
1406}
1407
1408Value * CBuilder::CreateInsertElement(Value * Vec, Value * NewElt, Value * Idx, const Twine & Name) {
1409    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
1410        if (LLVM_UNLIKELY(!Vec->getType()->isVectorTy())) {
1411            report_fatal_error("CreateExtractElement: Vec argument is not a vector type");
1412        }
1413        Constant * const Size = ConstantInt::get(Idx->getType(), Vec->getType()->getVectorNumElements());
1414        // inserting an element into a position that exceeds the length of the vector is undefined
1415        CreateAssert(CreateICmpULT(Idx, Size), "CreateInsertElement: Idx is greater than Vec size");
1416    }
1417    return IRBuilder<>::CreateInsertElement(Vec, NewElt, Idx, Name);
1418}
1419
1420CallInst * CBuilder::CreateSRandCall(Value * randomSeed) {
1421    Module * const m = getModule();
1422    Function * srandFunc = m->getFunction("srand");
1423    if (srandFunc == nullptr) {
1424        FunctionType * fty = FunctionType::get(getVoidTy(), {getInt32Ty()}, false);
1425        srandFunc = Function::Create(fty, Function::ExternalLinkage, "srand", m);
1426        srandFunc->setCallingConv(CallingConv::C);
1427    }
1428    return CreateCall(srandFunc, randomSeed);
1429}
1430
1431CallInst * CBuilder::CreateRandCall() {
1432    Module * const m = getModule();
1433    Function * randFunc = m->getFunction("rand");
1434    if (randFunc == nullptr) {
1435        FunctionType * fty = FunctionType::get(getInt32Ty(), false);
1436        randFunc = Function::Create(fty, Function::ExternalLinkage, "rand", m);
1437        randFunc->setCallingConv(CallingConv::C);
1438    }
1439    return CreateCall(randFunc, {});
1440}
1441
1442unsigned CBuilder::getPageSize() {
1443    return boost::interprocess::mapped_region::get_page_size();
1444}
1445
1446
1447CBuilder::CBuilder(LLVMContext & C)
1448: IRBuilder<>(C)
1449, mCacheLineAlignment(64)
1450, mSizeType(TypeBuilder<size_t, false>::get(C))
1451, mFILEtype(nullptr)
1452, mDriver(nullptr) {
1453
1454}
1455
1456struct RemoveRedundantAssertionsPass : public ModulePass {
1457    static char ID;
1458    RemoveRedundantAssertionsPass() : ModulePass(ID) { }
1459
1460    virtual bool runOnModule(Module &M) override;
1461};
1462
1463ModulePass * createRemoveRedundantAssertionsPass() {
1464    return new RemoveRedundantAssertionsPass();
1465}
1466
1467char RemoveRedundantAssertionsPass::ID = 0;
1468
1469bool RemoveRedundantAssertionsPass::runOnModule(Module & M) {
1470    Function * const assertFunc = M.getFunction("assert");
1471    if (LLVM_UNLIKELY(assertFunc == nullptr)) {
1472        return false;
1473    }
1474    bool modified = false;
1475    DenseSet<Value *> S;
1476    for (auto & F : M) {
1477        for (auto & B : F) {
1478            S.clear();
1479            for (BasicBlock::iterator i = B.begin(); i != B.end(); ) {
1480                Instruction & inst = *i;
1481                if (LLVM_UNLIKELY(isa<CallInst>(inst))) {
1482                    CallInst & ci = cast<CallInst>(inst);
1483                    if (ci.getCalledFunction() == assertFunc) {
1484                        bool remove = false;
1485                        Value * const check = ci.getOperand(0);
1486                        if (LLVM_UNLIKELY(isa<Constant>(check))) {
1487                            if (LLVM_LIKELY(cast<Constant>(check)->isOneValue())) {
1488                                remove = true;
1489                            } else {
1490                                // TODO: show all static failures with their compilation context
1491                            }
1492                        } else if (LLVM_UNLIKELY(S.count(check))) { // will never be executed
1493                            remove = true;
1494                        } else {
1495                            S.insert(check);
1496                        }
1497                        if (LLVM_UNLIKELY(remove)) {
1498                            i = ci.eraseFromParent();
1499                            modified = true;
1500                            continue;
1501                        }
1502                    }
1503                }
1504                ++i;
1505            }
1506        }
1507    }
1508    return modified;
1509}
Note: See TracBrowser for help on using the repository browser.