<commit_before>// MemCheckUninitialized.h (Oclgrind)
// Copyright (c) 2015, <NAME>
// Imperial College London. All rights reserved.
//
// This program is provided under a three-clause BSD license. For full
// license terms please see the LICENSE file distributed with this
// source code.

#include "core/common.h"

#include "core/Context.h"
#include "core/Memory.h"
#include "core/WorkItem.h"
#include "core/WorkGroup.h"
#include "core/Kernel.h"
#include "core/KernelInvocation.h"

#include "llvm/IR/Instructions.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Type.h"

#include "MemCheckUninitialized.h"
#include <mutex>

using namespace oclgrind;
using namespace std;

//void MemCheckUninitialized::memoryAllocated(const Memory *memory, size_t address,
//                                 size_t size, cl_mem_flags flags,
//                                 const uint8_t *initData)
//{
//    cout << "Memory: " << memory << ", address: " << hex << address << dec << ", size: " << size << endl;
//}

// Multiple mutexes to mitigate risk of unnecessary synchronisation in atomics
#define NUM_ATOMIC_MUTEXES 64 // Must be power of two
static std::mutex atomicShadowMutex[NUM_ATOMIC_MUTEXES];
#define ATOMIC_MUTEX(offset) \
  atomicShadowMutex[(((offset)>>2) & (NUM_ATOMIC_MUTEXES-1))]

THREAD_LOCAL ShadowContext::WorkSpace ShadowContext::m_workSpace = {NULL, NULL, NULL, 0};

MemCheckUninitialized::MemCheckUninitialized(const Context *context)
 : Plugin(context), shadowContext(sizeof(size_t)==8 ? 32 : 16)
{
    shadowContext.createMemoryPool();
}

MemCheckUninitialized::~MemCheckUninitialized()
{
    shadowContext.destroyMemoryPool();
}

void MemCheckUninitialized::kernelBegin(const KernelInvocation *kernelInvocation)
{
    const Kernel *kernel = kernelInvocation->getKernel();

    // Initialise kernel arguments and global variables
    for (auto value = kernel->values_begin(); value != kernel->values_end(); value++)
    {
        const llvm::Type *type = value->first->getType();

        if(!type->isSized())
        {
            continue;
        }

        if(type->isPointerTy())
        {
            switch(type->getPointerAddressSpace())
            {
                case AddrSpaceConstant:
                {
                    // Constants
                    // value->second.data == ptr
                    // value->second.size == ptr size
                    TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                    shadowContext.setGlobalValue(value->first, cleanValue);
                    const llvm::Type *elementTy = type->getPointerElementType();
                    allocAndStoreShadowMemory(AddrSpaceConstant, value->second.getPointer(), ShadowContext::getCleanValue(elementTy));
                    break;
                }
                case AddrSpaceGlobal:
                {
                    // Global pointer kernel arguments
                    // value->second.data == ptr
                    // value->second.size == ptr size
                    size_t address = value->second.getPointer();

                    if(m_context->getGlobalMemory()->isAddressValid(address) && !shadowContext.getGlobalMemory()->isAddressValid(address))
                    {
                        // Allocate poisoned global memory if there was no host store
                        size_t size = m_context->getGlobalMemory()->getBuffer(address)->size;
                        allocAndStoreShadowMemory(AddrSpaceGlobal, address, ShadowContext::getPoisonedValue(size), NULL, NULL, true);
                    }

                    m_deferredInit.push_back(*value);
                    break;
                }
                case AddrSpaceLocal:
                {
                    // Local pointer kernel arguments and local data variables
                    // value->second.data == NULL
                    // value->second.size == val size
                    if(llvm::isa<llvm::Argument>(value->first))
                    {
                        // Arguments have a private pointer
                        m_deferredInit.push_back(*value);
                    }
                    else
                    {
                        // Variables have a global pointer
                        TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                        shadowContext.setGlobalValue(value->first, cleanValue);
                    }

                    m_deferredInitGroup.push_back(*value);
                    break;
                }
                case AddrSpacePrivate:
                {
                    const llvm::Argument *A = llvm::dyn_cast<llvm::Argument>(value->first);

                    if(A && A->hasByValAttr())
                    {
                        // ByVal kernel argument
                        // value->second.data == val
                        // value->second.size == val size
                        m_deferredInit.push_back(*value);
                    }
                    else
                    {
                        // Private struct/Union definitions with global type
                        // value->second.data == val
                        // value->second.size == val size
                        m_deferredInit.push_back(*value);
                        TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                        //TODO: Structs can have posioned padding bytes. Is this important?
                        shadowContext.setGlobalValue(value->first, cleanValue);
                    }
                    break;
                }
                default:
                    FATAL_ERROR("Unsupported addressspace %d", type->getPointerAddressSpace());
            }
        }
        else
        {
            // Non pointer type kernel arguments
            // value->second.data == val
            // value->second.size == val size
            m_deferredInit.push_back(*value);
        }
    }
}

void MemCheckUninitialized::workItemBegin(const WorkItem *workItem)
{
    shadowContext.createMemoryPool();
    shadowContext.allocateWorkItems();
    ShadowWorkItem *shadowWI = shadowContext.createShadowWorkItem(workItem);

    for(auto value : m_deferredInit)
    {
        const llvm::Type *type = value.first->getType();

        if(type->isPointerTy())
        {
            switch(type->getPointerAddressSpace())
            {
                case AddrSpaceGlobal:
                    {
                        // Global pointer kernel arguments
                        // value.second.data == ptr
                        // value.second.size == ptr size
                        shadowWI->setValue(value.first, ShadowContext::getCleanValue(type));
                        break;
                    }
                case AddrSpaceLocal:
                    {
                        // Local pointer kernel arguments
                        // value.second.data == NULL
                        // value.second.size == val size
                        shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
                        break;
                    }
                case AddrSpacePrivate:
                    {
                        const llvm::Argument *A = llvm::dyn_cast<llvm::Argument>(value.first);

                        if(A && A->hasByValAttr())
                        {
                            // ByVal kernel argument
                            // value.second.data == val
                            // value.second.size == val size
                            size_t address = workItem->getOperand(value.first).getPointer();
                            TypedValue cleanValue = ShadowContext::getCleanValue(value.second.size);
                            allocAndStoreShadowMemory(AddrSpacePrivate, address, cleanValue, workItem);
                            shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
                        }
                        else
                        {
                            // Private struct/Union definitions with global type
                            // value.second.data == NULL
                            // value.second.size == val size
                            size_t address = workItem->getOperand(value.first).getPointer();
                            TypedValue cleanValue = ShadowContext::getCleanValue(value.second.size);
                            allocAndStoreShadowMemory(AddrSpacePrivate, address, cleanValue, workItem);
                        }
                        break;
                    }
            }
        }
        else
        {
            // Non pointer type kernel arguments
            // value->second.data == val
            // value->second.size == val size
            shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
        }
    }

#ifdef DUMP_SHADOW
    //shadowContext.dump(workItem);
#endif
}

void MemCheckUninitialized::workGroupBegin(const WorkGroup *workGroup)
{
    shadowContext.allocateWorkGroups();
    ShadowWorkGroup *shadowWG = shadowContext.createShadowWorkGroup(workGroup);

    for(auto value : m_deferredInitGroup)
    {
        // Local data variables
        // value->second.data == NULL
        // value->second.size == val size
        size_t address = workGroup->getLocalMemoryAddress(value.first);
        TypedValue v;

        if(llvm::isa<llvm::Argument>(value.first))
        {
            //TODO: Local memory clean or poisoned? May need to differentiate between kernel argument (?) and variable (poisoned)
            v = ShadowContext::getPoisonedValue(value.second.size);
        }
        else
        {
            v = ShadowContext::getPoisonedValue(value.second.size);
        }

        allocAndStoreShadowMemory(AddrSpaceLocal, address, v, NULL, workGroup, true);
    }
}

void MemCheckUninitialized::workItemComplete(const WorkItem *workItem)
{
    shadowContext.destroyShadowWorkItem(workItem);
    shadowContext.freeWorkItems();
    shadowContext.destroyMemoryPool();
}

void MemCheckUninitialized::workGroupComplete(const WorkGroup *workGroup)
{
    shadowContext.destroyShadowWorkGroup(workGroup);
    shadowContext.freeWorkGroups();
}

void MemCheckUninitialized::hostMemoryStore(const Memory *memory,
                             size_t address, size_t size,
                             const uint8_t *storeData)
{
    if(memory->getAddressSpace() == AddrSpaceGlobal)
    {
        TypedValue v = ShadowContext::getCleanValue(size);
        allocAndStoreShadowMemory(AddrSpaceGlobal, address, v);
    }
}

void MemCheckUninitialized::instructionExecuted(const WorkItem *workItem,
                                        const llvm::Instruction *instruction,
                                        const TypedValue& result)
{
#ifdef DUMP_SHADOW
    cout << "++++++++++++++++++++++++++++++++++++++++++++" << endl;
    instruction->dump();
#endif

    switch(instruction->getOpcode())
    {
        case llvm::Instruction::Add:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::Alloca:
        {
            const llvm::AllocaInst *allocaInst = ((const llvm::AllocaInst*)instruction);

            size_t address = result.getPointer();

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getCleanValue(instruction));

            TypedValue v = ShadowContext::getPoisonedValue(allocaInst->getAllocatedType());
            allocAndStoreShadowMemory(AddrSpacePrivate, address, v, workItem);
            break;
        }
        case llvm::Instruction::And:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::AShr:
        {
            TypedValue S0 = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue S1 = shadowContext.getValue(workItem, instruction->getOperand(1));

            if(!ShadowContext::isCleanValue(S1))
            {
                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getPoisonedValue(instruction));
            }
            else
            {
                TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);
                TypedValue Shift = workItem->getOperand(instruction->getOperand(1));
                uint64_t shiftMask = (S0.num > 1 ? S0.size : max((size_t)S0.size, sizeof(uint32_t))) * 8 - 1;

                for (unsigned i = 0; i < S0.num; i++)
                {
                    newShadow.setUInt(S0.getSInt(i) >> (Shift.getUInt(i) & shiftMask), i);
                }

                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            }

            break;
        }
        case llvm::Instruction::BitCast:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            memcpy(newShadow.data, shadow.data, newShadow.size*newShadow.num);
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::Br:
        {
            checkAllOperandsDefined(workItem, instruction);
#ifdef DUMP_SHADOW
            // Insert pseudo value to keep numbering
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getCleanValue(3));
#endif
            break;
        }
        case llvm::Instruction::Call:
        {
            const llvm::CallInst *callInst = ((const llvm::CallInst*)instruction);
            const llvm::Function *function = callInst->getCalledFunction();

            // Check for indirect function calls
            if (!function)
            {
                // Resolve indirect function pointer
                const llvm::Value *func = callInst->getCalledValue();
                const llvm::Value *funcPtr = ((const llvm::User*)func)->getOperand(0);
                function = (const llvm::Function*)funcPtr;
            }

            assert(!function->isVarArg() && "Variadic functions are not supported!");

            ShadowWorkItem *shadowWI = shadowContext.getShadowWorkItem(workItem);

            // For inline asm, do the usual thing: check argument shadow and mark all
            // outputs as clean. Note that any side effects of the inline asm that are
            // not immediately visible in its constraints are not handled.
            if (callInst->isInlineAsm())
            {
                checkAllOperandsDefined(workItem, instruction);
                shadowWI->setValue(instruction, ShadowContext::getCleanValue(instruction));
                break;
            }

            if(const llvm::IntrinsicInst *II = llvm::dyn_cast<const llvm::IntrinsicInst>(instruction))
            {
                handleIntrinsicInstruction(workItem, II);
                break;
            }

            if(function->isDeclaration())
            {
                if(!handleBuiltinFunction(workItem, function->getName().str(), callInst, result))
                {
                    // Handle external function calls
                    checkAllOperandsDefined(workItem, instruction);

                    if(callInst->getType()->isSized())
                    {
                        // Set return value only if function is non-void
                        shadowWI->setValue(instruction, ShadowContext::getCleanValue(instruction));
                    }
                }
                break;
            }

            assert(!llvm::isa<const llvm::IntrinsicInst>(instruction) && "intrinsics are handled elsewhere");

            // Fresh values for function
            ShadowValues *values = shadowWI->createCleanShadowValues();

            llvm::Function::const_arg_iterator argItr;
            for (argItr = function->arg_begin(); argItr != function->arg_end(); argItr++)
            {
                const llvm::Value *Val = callInst->getArgOperand(argItr->getArgNo());

                if (!Val->getType()->isSized())
                {
                    continue;
                }

                if(argItr->hasByValAttr())
                {
                    assert(Val->getType()->isPointerTy() && "ByVal argument is not a pointer!");
                    //// Make new copy of shadow in private memory
                    size_t origShadowAddress = workItem->getOperand(Val).getPointer();
                    size_t newShadowAddress = workItem->getOperand(argItr).getPointer();
                    unsigned char *origShadowData = (unsigned char*)shadowWI->getMemoryPointer(origShadowAddress);
                    size_t size = getTypeSize(argItr->getType()->getPointerElementType());

                    // Set new shadow memory
                    TypedValue v = ShadowContext::getCleanValue(size);
                    memcpy(v.data, origShadowData, size);
                    allocAndStoreShadowMemory(AddrSpacePrivate, newShadowAddress, v, workItem);
                    values->setValue(argItr, ShadowContext::getCleanValue(argItr));
                }
                else
                {
                    TypedValue newShadow = shadowContext.getMemoryPool()->clone(shadowContext.getValue(workItem, Val));
                    values->setValue(argItr, newShadow);
                }
            }

            // Now, get the shadow for the RetVal.
            if(callInst->getType()->isSized())
            {
                values->setCall(callInst);
            }

            shadowWI->pushValues(values);

            break;
        }
        case llvm::Instruction::ExtractElement:
        {
            const llvm::ExtractElementInst *extractInst = ((const llvm::ExtractElementInst*)instruction);

            TypedValue indexShadow = shadowContext.getValue(workItem, extractInst->getIndexOperand());

            if(!ShadowContext::isCleanValue(indexShadow))
            {
                logUninitializedIndex();
            }

            TypedValue vectorShadow = shadowContext.getValue(workItem, extractInst->getVectorOperand());
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            unsigned index = workItem->getOperand(extractInst->getIndexOperand()).getUInt();
            memcpy(newShadow.data, vectorShadow.data + newShadow.size*index, newShadow.size);

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::ExtractValue:
        {
            const llvm::ExtractValueInst *extractInst = ((const llvm::ExtractValueInst*)instruction);

            const llvm::Value *Agg = extractInst->getAggregateOperand();
            TypedValue ResShadow = shadowContext.getMemoryPool()->clone(result);

            llvm::ArrayRef<unsigned int> indices = extractInst->getIndices();

            // Compute offset for target value
            int offset = 0;
            const llvm::Type *type = Agg->getType();
            for (unsigned i = 0; i < indices.size(); i++)
            {
                if (type->isArrayTy())
                {
                    type = type->getArrayElementType();
                    offset += getTypeSize(type) * indices[i];
                }
                else if (type->isStructTy())
                {
                    offset += getStructMemberOffset((const llvm::StructType*)type, indices[i]);
                    type = type->getStructElementType(indices[i]);
                }
                else
                {
                    FATAL_ERROR("Unsupported aggregate type: %d", type->getTypeID())
                }
            }

            // Copy target value to result
            memcpy(ResShadow.data, shadowContext.getValue(workItem, Agg).data + offset, getTypeSize(type));

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ResShadow);
            break;
        }
        case llvm::Instruction::FAdd:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FCmp:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FDiv:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FMul:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPExt:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPToSI:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPToUI:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPTrunc:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FRem:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FSub:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::GetElementPtr:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::ICmp:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::InsertElement:
        {
            TypedValue indexShadow = shadowContext.getValue(workItem, instruction->getOperand(2));

            if(!ShadowContext::isCleanValue(indexShadow))
            {
                logUninitializedIndex();
            }

            TypedValue vectorShadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue elementShadow = shadowContext.getValue(workItem, instruction->getOperand(1));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            unsigned index = workItem->getOperand(instruction->getOperand(2)).getUInt();
            memcpy(newShadow.data, vectorShadow.data, newShadow.size*newShadow.num);
            memcpy(newShadow.data + index*newShadow.size, elementShadow.data, newShadow.size);

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::InsertValue:
        {
            const llvm::InsertValueInst *insertInst = (const llvm::InsertValueInst*)instruction;

            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            // Load original aggregate data
            const llvm::Value *agg = insertInst->getAggregateOperand();
            memcpy(newShadow.data, shadowContext.getValue(workItem, agg).data, newShadow.size*newShadow.num);

            // Compute offset for inserted value
            int offset = 0;
            llvm::ArrayRef<unsigned int> indices = insertInst->getIndices();
            const llvm::Type *type = agg->getType();
            for (unsigned i = 0; i < indices.size(); i++)
            {
                if (type->isArrayTy())
                {
                    type = type->getArrayElementType();
                    offset += getTypeSize(type) * indices[i];
                }
                else if (type->isStructTy())
                {
                    offset += getStructMemberOffset((const llvm::StructType*)type, indices[i]);
                    type = type->getStructElementType(indices[i]);
                }
                else
                {
                    FATAL_ERROR("Unsupported aggregate type: %d", type->getTypeID())
                }
            }

            // Copy inserted value into result
            const llvm::Value *value = insertInst->getInsertedValueOperand();
            memcpy(newShadow.data + offset, shadowContext.getValue(workItem, value).data, getTypeSize(value->getType()));

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::IntToPtr:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            for (unsigned i = 0; i < newShadow.num; i++)
            {
                newShadow.setPointer(shadow.getUInt(i), i);
            }

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::Load:
        {
            assert(instruction->getType()->isSized() && "Load type must have size");
            const llvm::LoadInst *loadInst = ((const llvm::LoadInst*)instruction);
            const llvm::Value *Addr = loadInst->getPointerOperand();

            size_t address = workItem->getOperand(Addr).getPointer();
            unsigned addrSpace = loadInst->getPointerAddressSpace();

            TypedValue v = shadowContext.getMemoryPool()->clone(result);
            loadShadowMemory(addrSpace, address, v, workItem);
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, v);

//            if (ClCheckAccessAddress)
//                insertShadowCheck(I.getPointerOperand(), &I);
//
//            if (I.isAtomic())
//                I.setOrdering(addAcquireOrdering(I.getOrdering()));

            break;
        }
        case llvm::Instruction::LShr:
        {
            TypedValue S0 = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue S1 = shadowContext.getValue(workItem, instruction->getOperand(1));

            if(!ShadowContext::isCleanValue(S1))
            {
                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getPoisonedValue(instruction));
            }
            else
            {
                TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);
                TypedValue Shift = workItem->getOperand(instruction->getOperand(1));
                uint64_t shiftMask = (S0.num > 1 ? S0.size : max((size_t)S0.size, sizeof(uint32_t))) * 8 - 1;

                for (unsigned i = 0; i < S0.num; i++)
                {
                    newShadow.setUInt(S0.getUInt(i) >> (Shift.getUInt(i) & shiftMask), i);
                }

                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            }

            break;
        }
        case llvm::Instruction::Mul:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::Or:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::PHI:
        {
            //FIXME: m_position is private
            const llvm::PHINode *phiNode = (const llvm::PHINode*)instruction;
            //const llvm::Value *value = phiNode->getIncomingValueForBlock(
            //        (const llvm::BasicBlock*)m_position->prevBlock);

            //TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            //memcpy(newShadow.data, getValue(value).data, newShadow.size*newShadow.num);
            //setValue(instruction, newShadow);

            bool poisoned = false;

            for(int i = 0; i < phiNode->getNumIncomingValues(); ++i)
            {
                const llvm::Value *V = phiNode->getIncomingValue(i);

                if(!shadowContext.hasValue(workItem, V))
                {
                    continue;
                }

                if(!ShadowContext::isCleanValue(shadowContext.getValue(workItem, V)))
                {
                    shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getPoisonedValue(instruction));
                    poisoned = true;
                    break;
                }
            }

            if(!poisoned)
            {
                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getCleanValue(instruction));
            }
            break;
        }
        case llvm::Instruction::PtrToInt:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            for (unsigned i = 0; i < newShadow.num; i++)
            {<commit_msg>Precise shadow propagation of PHI instructions<commit_after>// MemCheckUninitialized.h (Oclgrind)
// Copyright (c) 2015, <NAME>
// Imperial College London. All rights reserved.
//
// This program is provided under a three-clause BSD license. For full
// license terms please see the LICENSE file distributed with this
// source code.

#include "core/common.h"

#include "core/Context.h"
#include "core/Memory.h"
#include "core/WorkItem.h"
#include "core/WorkGroup.h"
#include "core/Kernel.h"
#include "core/KernelInvocation.h"

#include "llvm/IR/Instructions.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Type.h"

#include "MemCheckUninitialized.h"
#include <mutex>

using namespace oclgrind;
using namespace std;

//void MemCheckUninitialized::memoryAllocated(const Memory *memory, size_t address,
//                                 size_t size, cl_mem_flags flags,
//                                 const uint8_t *initData)
//{
//    cout << "Memory: " << memory << ", address: " << hex << address << dec << ", size: " << size << endl;
//}

// Multiple mutexes to mitigate risk of unnecessary synchronisation in atomics
#define NUM_ATOMIC_MUTEXES 64 // Must be power of two
static std::mutex atomicShadowMutex[NUM_ATOMIC_MUTEXES];
#define ATOMIC_MUTEX(offset) \
  atomicShadowMutex[(((offset)>>2) & (NUM_ATOMIC_MUTEXES-1))]

THREAD_LOCAL ShadowContext::WorkSpace ShadowContext::m_workSpace = {NULL, NULL, NULL, 0};

MemCheckUninitialized::MemCheckUninitialized(const Context *context)
 : Plugin(context), shadowContext(sizeof(size_t)==8 ? 32 : 16)
{
    shadowContext.createMemoryPool();
}

MemCheckUninitialized::~MemCheckUninitialized()
{
    shadowContext.destroyMemoryPool();
}

void MemCheckUninitialized::kernelBegin(const KernelInvocation *kernelInvocation)
{
    const Kernel *kernel = kernelInvocation->getKernel();

    // Initialise kernel arguments and global variables
    for (auto value = kernel->values_begin(); value != kernel->values_end(); value++)
    {
        const llvm::Type *type = value->first->getType();

        if(!type->isSized())
        {
            continue;
        }

        if(type->isPointerTy())
        {
            switch(type->getPointerAddressSpace())
            {
                case AddrSpaceConstant:
                {
                    // Constants
                    // value->second.data == ptr
                    // value->second.size == ptr size
                    TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                    shadowContext.setGlobalValue(value->first, cleanValue);
                    const llvm::Type *elementTy = type->getPointerElementType();
                    allocAndStoreShadowMemory(AddrSpaceConstant, value->second.getPointer(), ShadowContext::getCleanValue(elementTy));
                    break;
                }
                case AddrSpaceGlobal:
                {
                    // Global pointer kernel arguments
                    // value->second.data == ptr
                    // value->second.size == ptr size
                    size_t address = value->second.getPointer();

                    if(m_context->getGlobalMemory()->isAddressValid(address) && !shadowContext.getGlobalMemory()->isAddressValid(address))
                    {
                        // Allocate poisoned global memory if there was no host store
                        size_t size = m_context->getGlobalMemory()->getBuffer(address)->size;
                        allocAndStoreShadowMemory(AddrSpaceGlobal, address, ShadowContext::getPoisonedValue(size), NULL, NULL, true);
                    }

                    m_deferredInit.push_back(*value);
                    break;
                }
                case AddrSpaceLocal:
                {
                    // Local pointer kernel arguments and local data variables
                    // value->second.data == NULL
                    // value->second.size == val size
                    if(llvm::isa<llvm::Argument>(value->first))
                    {
                        // Arguments have a private pointer
                        m_deferredInit.push_back(*value);
                    }
                    else
                    {
                        // Variables have a global pointer
                        TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                        shadowContext.setGlobalValue(value->first, cleanValue);
                    }

                    m_deferredInitGroup.push_back(*value);
                    break;
                }
                case AddrSpacePrivate:
                {
                    const llvm::Argument *A = llvm::dyn_cast<llvm::Argument>(value->first);

                    if(A && A->hasByValAttr())
                    {
                        // ByVal kernel argument
                        // value->second.data == val
                        // value->second.size == val size
                        m_deferredInit.push_back(*value);
                    }
                    else
                    {
                        // Private struct/Union definitions with global type
                        // value->second.data == val
                        // value->second.size == val size
                        m_deferredInit.push_back(*value);
                        TypedValue cleanValue = m_pool.clone(ShadowContext::getCleanValue(value->first));
                        //TODO: Structs can have posioned padding bytes. Is this important?
                        shadowContext.setGlobalValue(value->first, cleanValue);
                    }
                    break;
                }
                default:
                    FATAL_ERROR("Unsupported addressspace %d", type->getPointerAddressSpace());
            }
        }
        else
        {
            // Non pointer type kernel arguments
            // value->second.data == val
            // value->second.size == val size
            m_deferredInit.push_back(*value);
        }
    }
}

void MemCheckUninitialized::workItemBegin(const WorkItem *workItem)
{
    shadowContext.createMemoryPool();
    shadowContext.allocateWorkItems();
    ShadowWorkItem *shadowWI = shadowContext.createShadowWorkItem(workItem);

    for(auto value : m_deferredInit)
    {
        const llvm::Type *type = value.first->getType();

        if(type->isPointerTy())
        {
            switch(type->getPointerAddressSpace())
            {
                case AddrSpaceGlobal:
                    {
                        // Global pointer kernel arguments
                        // value.second.data == ptr
                        // value.second.size == ptr size
                        shadowWI->setValue(value.first, ShadowContext::getCleanValue(type));
                        break;
                    }
                case AddrSpaceLocal:
                    {
                        // Local pointer kernel arguments
                        // value.second.data == NULL
                        // value.second.size == val size
                        shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
                        break;
                    }
                case AddrSpacePrivate:
                    {
                        const llvm::Argument *A = llvm::dyn_cast<llvm::Argument>(value.first);

                        if(A && A->hasByValAttr())
                        {
                            // ByVal kernel argument
                            // value.second.data == val
                            // value.second.size == val size
                            size_t address = workItem->getOperand(value.first).getPointer();
                            TypedValue cleanValue = ShadowContext::getCleanValue(value.second.size);
                            allocAndStoreShadowMemory(AddrSpacePrivate, address, cleanValue, workItem);
                            shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
                        }
                        else
                        {
                            // Private struct/Union definitions with global type
                            // value.second.data == NULL
                            // value.second.size == val size
                            size_t address = workItem->getOperand(value.first).getPointer();
                            TypedValue cleanValue = ShadowContext::getCleanValue(value.second.size);
                            allocAndStoreShadowMemory(AddrSpacePrivate, address, cleanValue, workItem);
                        }
                        break;
                    }
            }
        }
        else
        {
            // Non pointer type kernel arguments
            // value->second.data == val
            // value->second.size == val size
            shadowWI->setValue(value.first, ShadowContext::getCleanValue(value.first));
        }
    }

#ifdef DUMP_SHADOW
    //shadowContext.dump(workItem);
#endif
}

void MemCheckUninitialized::workGroupBegin(const WorkGroup *workGroup)
{
    shadowContext.createMemoryPool();
    shadowContext.allocateWorkGroups();
    shadowContext.createShadowWorkGroup(workGroup);

    for(auto value : m_deferredInitGroup)
    {
        // Local data variables
        // value->second.data == NULL
        // value->second.size == val size
        size_t address = workGroup->getLocalMemoryAddress(value.first);
        TypedValue v;

        if(llvm::isa<llvm::Argument>(value.first))
        {
            //TODO: Local memory clean or poisoned? May need to differentiate between kernel argument (?) and variable (poisoned)
            v = ShadowContext::getPoisonedValue(value.second.size);
        }
        else
        {
            v = ShadowContext::getPoisonedValue(value.second.size);
        }

        allocAndStoreShadowMemory(AddrSpaceLocal, address, v, NULL, workGroup, true);
    }
}

void MemCheckUninitialized::workItemComplete(const WorkItem *workItem)
{
    shadowContext.destroyShadowWorkItem(workItem);
    shadowContext.freeWorkItems();
    shadowContext.destroyMemoryPool();
}

void MemCheckUninitialized::workGroupComplete(const WorkGroup *workGroup)
{
    shadowContext.destroyShadowWorkGroup(workGroup);
    shadowContext.freeWorkGroups();
}

void MemCheckUninitialized::hostMemoryStore(const Memory *memory,
                             size_t address, size_t size,
                             const uint8_t *storeData)
{
    if(memory->getAddressSpace() == AddrSpaceGlobal)
    {
        TypedValue v = ShadowContext::getCleanValue(size);
        allocAndStoreShadowMemory(AddrSpaceGlobal, address, v);
    }
}

void MemCheckUninitialized::instructionExecuted(const WorkItem *workItem,
                                        const llvm::Instruction *instruction,
                                        const TypedValue& result)
{
#ifdef DUMP_SHADOW
    cout << "++++++++++++++++++++++++++++++++++++++++++++" << endl;
    instruction->dump();
#endif

    switch(instruction->getOpcode())
    {
        case llvm::Instruction::Add:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::Alloca:
        {
            const llvm::AllocaInst *allocaInst = ((const llvm::AllocaInst*)instruction);

            size_t address = result.getPointer();

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getCleanValue(instruction));

            TypedValue v = ShadowContext::getPoisonedValue(allocaInst->getAllocatedType());
            allocAndStoreShadowMemory(AddrSpacePrivate, address, v, workItem);
            break;
        }
        case llvm::Instruction::And:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::AShr:
        {
            TypedValue S0 = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue S1 = shadowContext.getValue(workItem, instruction->getOperand(1));

            if(!ShadowContext::isCleanValue(S1))
            {
                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getPoisonedValue(instruction));
            }
            else
            {
                TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);
                TypedValue Shift = workItem->getOperand(instruction->getOperand(1));
                uint64_t shiftMask = (S0.num > 1 ? S0.size : max((size_t)S0.size, sizeof(uint32_t))) * 8 - 1;

                for (unsigned i = 0; i < S0.num; i++)
                {
                    newShadow.setUInt(S0.getSInt(i) >> (Shift.getUInt(i) & shiftMask), i);
                }

                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            }

            break;
        }
        case llvm::Instruction::BitCast:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            memcpy(newShadow.data, shadow.data, newShadow.size*newShadow.num);
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::Br:
        {
            checkAllOperandsDefined(workItem, instruction);
#ifdef DUMP_SHADOW
            // Insert pseudo value to keep numbering
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getCleanValue(3));
#endif
            break;
        }
        case llvm::Instruction::Call:
        {
            const llvm::CallInst *callInst = ((const llvm::CallInst*)instruction);
            const llvm::Function *function = callInst->getCalledFunction();

            // Check for indirect function calls
            if (!function)
            {
                // Resolve indirect function pointer
                const llvm::Value *func = callInst->getCalledValue();
                const llvm::Value *funcPtr = ((const llvm::User*)func)->getOperand(0);
                function = (const llvm::Function*)funcPtr;
            }

            assert(!function->isVarArg() && "Variadic functions are not supported!");

            ShadowWorkItem *shadowWI = shadowContext.getShadowWorkItem(workItem);

            // For inline asm, do the usual thing: check argument shadow and mark all
            // outputs as clean. Note that any side effects of the inline asm that are
            // not immediately visible in its constraints are not handled.
            if (callInst->isInlineAsm())
            {
                checkAllOperandsDefined(workItem, instruction);
                shadowWI->setValue(instruction, ShadowContext::getCleanValue(instruction));
                break;
            }

            if(const llvm::IntrinsicInst *II = llvm::dyn_cast<const llvm::IntrinsicInst>(instruction))
            {
                handleIntrinsicInstruction(workItem, II);
                break;
            }

            if(function->isDeclaration())
            {
                if(!handleBuiltinFunction(workItem, function->getName().str(), callInst, result))
                {
                    // Handle external function calls
                    checkAllOperandsDefined(workItem, instruction);

                    if(callInst->getType()->isSized())
                    {
                        // Set return value only if function is non-void
                        shadowWI->setValue(instruction, ShadowContext::getCleanValue(instruction));
                    }
                }
                break;
            }

            assert(!llvm::isa<const llvm::IntrinsicInst>(instruction) && "intrinsics are handled elsewhere");

            // Fresh values for function
            ShadowValues *values = shadowWI->createCleanShadowValues();

            llvm::Function::const_arg_iterator argItr;
            for (argItr = function->arg_begin(); argItr != function->arg_end(); argItr++)
            {
                const llvm::Value *Val = callInst->getArgOperand(argItr->getArgNo());

                if (!Val->getType()->isSized())
                {
                    continue;
                }

                if(argItr->hasByValAttr())
                {
                    assert(Val->getType()->isPointerTy() && "ByVal argument is not a pointer!");
                    //// Make new copy of shadow in private memory
                    size_t origShadowAddress = workItem->getOperand(Val).getPointer();
                    size_t newShadowAddress = workItem->getOperand(argItr).getPointer();
                    unsigned char *origShadowData = (unsigned char*)shadowWI->getMemoryPointer(origShadowAddress);
                    size_t size = getTypeSize(argItr->getType()->getPointerElementType());

                    // Set new shadow memory
                    TypedValue v = ShadowContext::getCleanValue(size);
                    memcpy(v.data, origShadowData, size);
                    allocAndStoreShadowMemory(AddrSpacePrivate, newShadowAddress, v, workItem);
                    values->setValue(argItr, ShadowContext::getCleanValue(argItr));
                }
                else
                {
                    TypedValue newShadow = shadowContext.getMemoryPool()->clone(shadowContext.getValue(workItem, Val));
                    values->setValue(argItr, newShadow);
                }
            }

            // Now, get the shadow for the RetVal.
            if(callInst->getType()->isSized())
            {
                values->setCall(callInst);
            }

            shadowWI->pushValues(values);

            break;
        }
        case llvm::Instruction::ExtractElement:
        {
            const llvm::ExtractElementInst *extractInst = ((const llvm::ExtractElementInst*)instruction);

            TypedValue indexShadow = shadowContext.getValue(workItem, extractInst->getIndexOperand());

            if(!ShadowContext::isCleanValue(indexShadow))
            {
                logUninitializedIndex();
            }

            TypedValue vectorShadow = shadowContext.getValue(workItem, extractInst->getVectorOperand());
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            unsigned index = workItem->getOperand(extractInst->getIndexOperand()).getUInt();
            memcpy(newShadow.data, vectorShadow.data + newShadow.size*index, newShadow.size);

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::ExtractValue:
        {
            const llvm::ExtractValueInst *extractInst = ((const llvm::ExtractValueInst*)instruction);

            const llvm::Value *Agg = extractInst->getAggregateOperand();
            TypedValue ResShadow = shadowContext.getMemoryPool()->clone(result);

            llvm::ArrayRef<unsigned int> indices = extractInst->getIndices();

            // Compute offset for target value
            int offset = 0;
            const llvm::Type *type = Agg->getType();
            for (unsigned i = 0; i < indices.size(); i++)
            {
                if (type->isArrayTy())
                {
                    type = type->getArrayElementType();
                    offset += getTypeSize(type) * indices[i];
                }
                else if (type->isStructTy())
                {
                    offset += getStructMemberOffset((const llvm::StructType*)type, indices[i]);
                    type = type->getStructElementType(indices[i]);
                }
                else
                {
                    FATAL_ERROR("Unsupported aggregate type: %d", type->getTypeID())
                }
            }

            // Copy target value to result
            memcpy(ResShadow.data, shadowContext.getValue(workItem, Agg).data + offset, getTypeSize(type));

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ResShadow);
            break;
        }
        case llvm::Instruction::FAdd:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FCmp:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FDiv:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FMul:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPExt:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPToSI:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPToUI:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FPTrunc:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FRem:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::FSub:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::GetElementPtr:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::ICmp:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::InsertElement:
        {
            TypedValue indexShadow = shadowContext.getValue(workItem, instruction->getOperand(2));

            if(!ShadowContext::isCleanValue(indexShadow))
            {
                logUninitializedIndex();
            }

            TypedValue vectorShadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue elementShadow = shadowContext.getValue(workItem, instruction->getOperand(1));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            unsigned index = workItem->getOperand(instruction->getOperand(2)).getUInt();
            memcpy(newShadow.data, vectorShadow.data, newShadow.size*newShadow.num);
            memcpy(newShadow.data + index*newShadow.size, elementShadow.data, newShadow.size);

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::InsertValue:
        {
            const llvm::InsertValueInst *insertInst = (const llvm::InsertValueInst*)instruction;

            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            // Load original aggregate data
            const llvm::Value *agg = insertInst->getAggregateOperand();
            memcpy(newShadow.data, shadowContext.getValue(workItem, agg).data, newShadow.size*newShadow.num);

            // Compute offset for inserted value
            int offset = 0;
            llvm::ArrayRef<unsigned int> indices = insertInst->getIndices();
            const llvm::Type *type = agg->getType();
            for (unsigned i = 0; i < indices.size(); i++)
            {
                if (type->isArrayTy())
                {
                    type = type->getArrayElementType();
                    offset += getTypeSize(type) * indices[i];
                }
                else if (type->isStructTy())
                {
                    offset += getStructMemberOffset((const llvm::StructType*)type, indices[i]);
                    type = type->getStructElementType(indices[i]);
                }
                else
                {
                    FATAL_ERROR("Unsupported aggregate type: %d", type->getTypeID())
                }
            }

            // Copy inserted value into result
            const llvm::Value *value = insertInst->getInsertedValueOperand();
            memcpy(newShadow.data + offset, shadowContext.getValue(workItem, value).data, getTypeSize(value->getType()));

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::IntToPtr:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            for (unsigned i = 0; i < newShadow.num; i++)
            {
                newShadow.setPointer(shadow.getUInt(i), i);
            }

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            break;
        }
        case llvm::Instruction::Load:
        {
            assert(instruction->getType()->isSized() && "Load type must have size");
            const llvm::LoadInst *loadInst = ((const llvm::LoadInst*)instruction);
            const llvm::Value *Addr = loadInst->getPointerOperand();

            size_t address = workItem->getOperand(Addr).getPointer();
            unsigned addrSpace = loadInst->getPointerAddressSpace();

            TypedValue v = shadowContext.getMemoryPool()->clone(result);
            loadShadowMemory(addrSpace, address, v, workItem);
            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, v);

//            if (ClCheckAccessAddress)
//                insertShadowCheck(I.getPointerOperand(), &I);
//
//            if (I.isAtomic())
//                I.setOrdering(addAcquireOrdering(I.getOrdering()));

            break;
        }
        case llvm::Instruction::LShr:
        {
            TypedValue S0 = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue S1 = shadowContext.getValue(workItem, instruction->getOperand(1));

            if(!ShadowContext::isCleanValue(S1))
            {
                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, ShadowContext::getPoisonedValue(instruction));
            }
            else
            {
                TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);
                TypedValue Shift = workItem->getOperand(instruction->getOperand(1));
                uint64_t shiftMask = (S0.num > 1 ? S0.size : max((size_t)S0.size, sizeof(uint32_t))) * 8 - 1;

                for (unsigned i = 0; i < S0.num; i++)
                {
                    newShadow.setUInt(S0.getUInt(i) >> (Shift.getUInt(i) & shiftMask), i);
                }

                shadowContext.getShadowWorkItem(workItem)->setValue(instruction, newShadow);
            }

            break;
        }
        case llvm::Instruction::Mul:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::Or:
        {
            SimpleOr(workItem, instruction);
            break;
        }
        case llvm::Instruction::PHI:
        {
            const llvm::PHINode *phiNode = (const llvm::PHINode*)instruction;
            const llvm::Value *value = phiNode->getIncomingValueForBlock(workItem->getPreviousBlock());
            TypedValue shadowValue = shadowContext.getValue(workItem, value);

            shadowContext.getShadowWorkItem(workItem)->setValue(instruction, shadowValue);
            break;
        }
        case llvm::Instruction::PtrToInt:
        {
            TypedValue shadow = shadowContext.getValue(workItem, instruction->getOperand(0));
            TypedValue newShadow = shadowContext.getMemoryPool()->clone(result);

            for (unsigned i = 0; i < newShadow.num; i++)
            {
{'fraction_non_alphanumeric': 0.10607241550343655, 'fraction_numerical': 0.0024622688301565933, 'mean_word_length': 1.7501826862181518, 'pattern_counts': {'":': 0, '<': 80, '<?xml version=': 0, '>': 363, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7643948', 'n_tokens_mistral': 14036, 'n_tokens_neox': 13773, 'n_words': 2582}