13884489619

Committed 16 Mar 2025 02:44PM UTC coverage: 77.883% (+1.2%) from 76.638%

Build # 13884489619

Build Type

Pull #212

github

Committed by

web-flow

Commit Message

Merge 37571da47 into 9f356f9ca

Pull Request Pull Request #212: Implement fold control flow optimization

Run Details

25 of 37 new or added lines in 1 file covered. (67.57%)

323 existing lines in 11 files now uncovered.

4437 of 5697 relevant lines covered (77.88%)

250.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

73.2

/compiler/lib/codegen/optree_to_llvmir/llvmir_generator.cpp

#include "llvmir_generator.hpp"

#include <cstddef>
#include <cstdint>
#include <iterator>
#include <string>
#include <string_view>
#include <system_error>
#include <vector>

#include <llvm/IR/CFG.h>
#include <llvm/IR/Constants.h>
#include <llvm/IR/DerivedTypes.h>
#include <llvm/IR/Type.h>
#include <llvm/IR/Value.h>
#include <llvm/Support/Casting.h>
#include <llvm/Support/raw_ostream.h>

#include "compiler/optree/adaptors.hpp"
#include "compiler/optree/definitions.hpp"
#include "compiler/optree/operation.hpp"
#include "compiler/optree/program.hpp"
#include "compiler/optree/types.hpp"
#include "compiler/optree/value.hpp"
#include "compiler/utils/debug.hpp"

using namespace optree;
using namespace optree::llvmir_generator;

// NOLINTBEGIN(readability-avoid-return-with-void-value)
namespace {

namespace external {

constexpr std::string_view printf = "printf";
constexpr std::string_view scanf = "scanf";

} // namespace external

std::string_view getFormatSpecifier(const Type::Ptr &type) {
    if (type->is<IntegerType>())
        return "%lld";
    if (type->is<FloatType>())
        return "%lf";
    if (type->is<StrType>())
        return "%s";
    if (type->is<NoneType>())
        return "None";
    if (type->is<PointerType>())
        return "%p";
    COMPILER_UNREACHABLE("unexpected type for a format specifier");
}

} // namespace

LLVMIRGenerator::LLVMIRGenerator(const std::string &moduleName)
    : context(), builder(context), mod(moduleName, context), currentFunction(nullptr) {
}

llvm::Value *LLVMIRGenerator::findValue(const Value::Ptr &value) const {
    auto it = values.find(value.get());
    if (it == values.end())
        return nullptr;
    return it->second;
}

void LLVMIRGenerator::saveValue(const Value::Ptr &value, llvm::Value *llvmValue) {
    values[value.get()] = llvmValue;
}

llvm::Type *LLVMIRGenerator::convertType(const Type::Ptr &type) {
    if (type->is<NoneType>())
        return llvm::Type::getVoidTy(context);
    if (type->is<BoolType>())
        return llvm::Type::getInt1Ty(context);
    if (type->is<IntegerType>())
        return llvm::Type::getIntNTy(context, type->bitWidth());
    if (type->is<FloatType>())
        return llvm::Type::getDoubleTy(context);
    if (type->is<StrType>())
        return llvm::Type::getIntNPtrTy(context, type->as<StrType>().charWidth);
    if (type->is<PointerType>())
        return llvm::PointerType::getUnqual(context);
    COMPILER_UNREACHABLE("unexpected type");
}

llvm::BasicBlock *LLVMIRGenerator::createBlock() {
    auto *bb = llvm::BasicBlock::Create(context, "bb", currentFunction);
    basicBlocks.push_back(bb);
    return bb;
}

void LLVMIRGenerator::eraseDeadBlocks() {
    for (auto *&bb : basicBlocks) {
        if (bb == nullptr)
            continue;
        if (llvm::pred_empty(bb) && !bb->isEntryBlock()) {
            bb->eraseFromParent();
            bb = nullptr;
        }
    }
}

llvm::Value *LLVMIRGenerator::normalizePredicate(const Value::Ptr &cond) {
    auto *pred = findValue(cond);
    if (!pred)
        return nullptr;
    if (pred->getType()->isIntegerTy(1))
        return pred;
    auto *i1Type = llvm::Type::getInt1Ty(context);
    auto *trunc = builder.CreateTrunc(pred, i1Type);
    return builder.CreateICmpEQ(trunc, llvm::ConstantInt::get(i1Type, 1U));
}

llvm::Value *LLVMIRGenerator::getGlobalString(const std::string &str) {
    auto it = globalStrings.find(str);
    if (it != globalStrings.end())
        return it->second;
    return globalStrings[str] = builder.CreateGlobalString(str);
}

llvm::FunctionCallee LLVMIRGenerator::getExternalFunction(std::string_view name) {
    auto it = externalFunctions.find(name);
    if (it != externalFunctions.end())
        return it->second;
    return externalFunctions[name] = loadExternalFunction(name);
}

llvm::FunctionCallee LLVMIRGenerator::loadExternalFunction(std::string_view name) {
    auto createVarArgFunction = [&](std::string_view name) {
        std::vector<llvm::Type *> arguments = {llvm::PointerType::getUnqual(context)};
        auto *llvmType = llvm::FunctionType::get(llvm::Type::getInt32Ty(context),
                                                 {llvm::PointerType::getUnqual(context)}, /*isVarArg*/ true);
        return mod.getOrInsertFunction(name, llvmType);
    };

    if (name == external::printf)
        return createVarArgFunction(name);
    if (name == external::scanf)
        return createVarArgFunction(name);
    COMPILER_UNREACHABLE("unexpected external function");
}

void LLVMIRGenerator::visit(const Operation::Ptr &op) {
    if (auto concreteOp = op->as<ModuleOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<FunctionOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<FunctionCallOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ReturnOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ConstantOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ArithBinaryOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<LogicBinaryOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ArithCastOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ArithUnaryOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<LogicUnaryOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<AllocateOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<LoadOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<StoreOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<IfOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ThenOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ElseOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<WhileOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ConditionOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<ForOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<InputOp>())
        return visit(concreteOp);
    if (auto concreteOp = op->as<PrintOp>())
        return visit(concreteOp);
    COMPILER_UNREACHABLE("unexpected operation");
}

void LLVMIRGenerator::visitBody(const Operation::Ptr &op) {
    for (const auto &inner : op->body)
        visit(inner);
}

void LLVMIRGenerator::visit(const ModuleOp &op) {
    for (const auto &inner : op->body)
        visit(inner);
}

void LLVMIRGenerator::visit(const FunctionOp &op) {
    const auto &funcType = op.type();
    std::vector<llvm::Type *> arguments;
    std::vector<llvm::Type *> elemTypes;
    for (const auto &arg : funcType.arguments) {
        arguments.push_back(convertType(arg));
        elemTypes.push_back(arg->is<PointerType>() ? convertType(arg->as<PointerType>().pointee) : nullptr);
    }
    auto *llvmType = llvm::FunctionType::get(convertType(funcType.result), arguments, /*isVarArg*/ false);
    currentFunction = llvm::cast<llvm::Function>(mod.getOrInsertFunction(op.name(), llvmType).getCallee());
    for (size_t i = 0; i < op->numInwards(); i++) {
        auto *argValue = currentFunction->getArg(i);
        saveValue(op->inward(i), argValue);
        if (auto *elemType = elemTypes[i])
            typedValues[argValue] = elemType;
    }
    auto *bb = createBlock();
    builder.SetInsertPoint(bb);
    visitBody(op);
}

void LLVMIRGenerator::visit(const FunctionCallOp &op) {
    std::vector<llvm::Value *> arguments;
    for (const auto &arg : op->operands)
        arguments.push_back(findValue(arg));
    auto *inst = builder.CreateCall(mod.getFunction(op.name()), arguments);
    if (op->numResults() != 0)
        saveValue(op.result(), inst);
}

void LLVMIRGenerator::visit(const ReturnOp &op) {
    if (op->numOperands() == 0)
        builder.CreateRetVoid();
    else
        builder.CreateRet(findValue(op.value()));
    auto *bb = createBlock();
    builder.SetInsertPoint(bb);
}

void LLVMIRGenerator::visit(const ConstantOp &op) {
    const auto &type = op.result()->type;
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    if (type->is<BoolType>())
        return result(llvm::ConstantInt::get(convertType(type), op.value().as<bool>()));
    if (type->is<IntegerType>()) {
        auto num = static_cast<int64_t>(op.value().as<NativeInt>());
        auto *value = llvm::ConstantInt::get(convertType(type), reinterpret_cast<uint64_t &>(num), /*IsSigned*/ true);
        return result(value);
    }
    if (type->is<FloatType>())
        return result(llvm::ConstantFP::get(convertType(type), static_cast<double>(op.value().as<NativeFloat>())));
    if (type->is<StrType>())
        return result(getGlobalString(op.value().as<NativeStr>()));
    COMPILER_UNREACHABLE("unexpected result type in ConstantOp");
}

void LLVMIRGenerator::visit(const ArithBinaryOp &op) {
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    auto *lhs = findValue(op.lhs());
    auto *rhs = findValue(op.rhs());
    switch (op.kind()) {
    case ArithBinOpKind::AddI:
        return result(builder.CreateAdd(lhs, rhs));
    case ArithBinOpKind::SubI:
        return result(builder.CreateSub(lhs, rhs));
    case ArithBinOpKind::MulI:
        return result(builder.CreateMul(lhs, rhs));
    case ArithBinOpKind::DivI:
        return result(builder.CreateSDiv(lhs, rhs));
    case ArithBinOpKind::AddF:
        return result(builder.CreateFAdd(lhs, rhs));
    case ArithBinOpKind::SubF:
        return result(builder.CreateFSub(lhs, rhs));
    case ArithBinOpKind::MulF:
        return result(builder.CreateFMul(lhs, rhs));
    case ArithBinOpKind::DivF:
        return result(builder.CreateFDiv(lhs, rhs));
    default:
        COMPILER_UNREACHABLE("unexpected kind in ArithBinaryOp");
    }
}

void LLVMIRGenerator::visit(const LogicBinaryOp &op) {
    const auto &type = op.lhs()->type;
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    auto *lhs = findValue(op.lhs());
    auto *rhs = findValue(op.rhs());
    switch (op.kind()) {
    case LogicBinOpKind::Equal:
        if (type->is<IntegerType>())
            return result(builder.CreateICmpEQ(lhs, rhs));
        return result(builder.CreateFCmpOEQ(lhs, rhs));
    case LogicBinOpKind::NotEqual:
        if (type->is<IntegerType>())
            return result(builder.CreateICmpNE(lhs, rhs));
        return result(builder.CreateFCmpONE(lhs, rhs));
    case LogicBinOpKind::AndI:
        return result(builder.CreateLogicalAnd(lhs, rhs));
    case LogicBinOpKind::OrI:
        return result(builder.CreateLogicalOr(lhs, rhs));
    case LogicBinOpKind::LessI:
        return result(builder.CreateICmpSLT(lhs, rhs));
    case LogicBinOpKind::GreaterI:
        return result(builder.CreateICmpSGT(lhs, rhs));
    case LogicBinOpKind::LessEqualI:
        return result(builder.CreateICmpSLE(lhs, rhs));
    case LogicBinOpKind::GreaterEqualI:
        return result(builder.CreateICmpSGE(lhs, rhs));
    case LogicBinOpKind::LessF:
        return result(builder.CreateFCmpOLT(lhs, rhs));
    case LogicBinOpKind::GreaterF:
        return result(builder.CreateFCmpOGT(lhs, rhs));
    case LogicBinOpKind::LessEqualF:
        return result(builder.CreateFCmpOLE(lhs, rhs));
    case LogicBinOpKind::GreaterEqualF:
        return result(builder.CreateFCmpOGE(lhs, rhs));
    default:
        COMPILER_UNREACHABLE("unexpected kind in LogicBinaryOp");
    }
}

void LLVMIRGenerator::visit(const ArithCastOp &op) {
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    auto *operand = findValue(op.value());
    auto *destType = convertType(op.result()->type);
    switch (op.kind()) {
    case ArithCastOpKind::IntToFloat:
        return result(builder.CreateSIToFP(operand, destType));
    case ArithCastOpKind::FloatToInt:
        return result(builder.CreateFPToSI(operand, destType));
    case ArithCastOpKind::ExtI:
        return result(builder.CreateSExt(operand, destType));
    case ArithCastOpKind::TruncI:
        return result(builder.CreateTrunc(operand, destType));
    case ArithCastOpKind::ExtF:
        return result(builder.CreateFPExt(operand, destType));
    case ArithCastOpKind::TruncF:
        return result(builder.CreateFPTrunc(operand, destType));
    default:
        COMPILER_UNREACHABLE("unexpected kind in ArithCastOp");
    }
}

void LLVMIRGenerator::visit(const ArithUnaryOp &op) {
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    auto *operand = findValue(op.value());
    switch (op.kind()) {
    case ArithUnaryOpKind::NegI:
        return result(builder.CreateNeg(operand));
    case ArithUnaryOpKind::NegF:
        return result(builder.CreateFNeg(operand));
    default:
        COMPILER_UNREACHABLE("unexpected kind in ArithUnaryOp");
    }
}

void LLVMIRGenerator::visit(const LogicUnaryOp &op) {
    auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };
    auto *operand = findValue(op.value());
    switch (op.kind()) {
    case LogicUnaryOpKind::Not:
        return result(builder.CreateNot(operand));
    default:
        COMPILER_UNREACHABLE("unexpected kind in LogicUnaryOp");
    }
}

void LLVMIRGenerator::visit(const AllocateOp &op) {
    const auto &type = op.result()->type->as<PointerType>();
    auto *llvmType = convertType(type.pointee);
    llvm::Value *size = nullptr;
    if (type.numElements == PointerType::dynamic)
        size = findValue(op.dynamicSize());
    else if (type.numElements > 1U)
        size = llvm::ConstantInt::get(llvm::Type::getIntNTy(context, 64U), type.numElements);
    auto *inst = builder.CreateAlloca(llvmType, size);
    saveValue(op.result(), inst);
    typedValues[inst] = llvmType;
}

void LLVMIRGenerator::visit(const LoadOp &op) {
    auto *ptr = findValue(op.src());
    auto *type = typedValues[ptr];
    if (auto offset = op.offset()) {
        auto *index = findValue(offset);
        ptr = builder.CreateGEP(type, ptr, index);
    }
    saveValue(op.result(), builder.CreateLoad(type, ptr));
}

void LLVMIRGenerator::visit(const StoreOp &op) {
    auto *ptr = findValue(op.dst());
    if (auto offset = op.offset()) {
        auto *index = findValue(offset);
        ptr = builder.CreateGEP(typedValues[ptr], ptr, index);
    }
    builder.CreateStore(findValue(op.valueToStore()), ptr);
}

void LLVMIRGenerator::visit(const IfOp &op) {
    auto *prevBlock = builder.GetInsertBlock();
    auto *thenBlock = createBlock();
    builder.SetInsertPoint(thenBlock);
    visit(op.thenOp());
    auto *newThenBlock = builder.GetInsertBlock();
    auto *elseBlock = createBlock();
    auto *nextBlock = elseBlock;
    if (auto elseOp = op.elseOp()) {
        builder.SetInsertPoint(elseBlock);
        visit(elseOp);
        nextBlock = createBlock();
        builder.CreateBr(nextBlock);
    }
    builder.SetInsertPoint(newThenBlock);
    builder.CreateBr(nextBlock);
    builder.SetInsertPoint(prevBlock);
    builder.CreateCondBr(normalizePredicate(op.cond()), thenBlock, elseBlock);
    builder.SetInsertPoint(nextBlock);
}

void LLVMIRGenerator::visit(const ThenOp &op) {
    visitBody(op);
}

void LLVMIRGenerator::visit(const ElseOp &op) {
    visitBody(op);
}

void LLVMIRGenerator::visit(const WhileOp &op) {
    auto *condBlock = createBlock();
    builder.CreateBr(condBlock);
    builder.SetInsertPoint(condBlock);
    auto condOp = op.conditionOp();
    visit(condOp);
    auto *thenBlock = createBlock();
    auto *nextBlock = createBlock();
    builder.CreateCondBr(normalizePredicate(condOp.terminator()), thenBlock, nextBlock);
    builder.SetInsertPoint(thenBlock);
    for (auto it = std::next(op->body.begin()); it != op->body.end(); ++it)
        visit(*it);
    builder.CreateBr(condBlock);
    builder.SetInsertPoint(nextBlock);
}

void LLVMIRGenerator::visit(const ConditionOp &op) {
    visitBody(op);
}

void LLVMIRGenerator::visit(const ForOp &op) {
    auto *llvmType = convertType(op.start()->type);
    auto *allocaI = builder.CreateAlloca(llvmType);
    builder.CreateStore(findValue(op.start()), allocaI);
    auto *condBlock = createBlock();
    builder.CreateBr(condBlock);
    builder.SetInsertPoint(condBlock);
    auto *loadedI = builder.CreateLoad(llvmType, allocaI);
    saveValue(op.iterator(), loadedI);
    auto *cond = builder.CreateICmpSLT(loadedI, findValue(op.stop()));
    auto *thenBlock = createBlock();
    auto *nextBlock = createBlock();
    builder.CreateCondBr(cond, thenBlock, nextBlock);
    builder.SetInsertPoint(thenBlock);
    visitBody(op);
    auto *nextI = builder.CreateAdd(loadedI, findValue(op.step()));
    builder.CreateStore(nextI, allocaI);
    builder.CreateBr(condBlock);
    builder.SetInsertPoint(nextBlock);
}

void LLVMIRGenerator::visit(const InputOp &op) {
    std::string format(getFormatSpecifier(op.dst()->type->as<PointerType>().pointee));
    builder.CreateCall(getExternalFunction(external::scanf), {getGlobalString(format), findValue(op.dst())});
}

void LLVMIRGenerator::visit(const PrintOp &op) {
    std::vector<llvm::Value *> arguments;
    arguments.reserve(op->numOperands() + 1U);
    arguments.push_back(nullptr);
    std::string format;
    format.reserve(4U * op->numOperands());
    for (const auto &operand : op->operands) {
        arguments.push_back(findValue(operand));
        format += getFormatSpecifier(operand->type);
    }
    arguments.front() = getGlobalString(format);
    builder.CreateCall(getExternalFunction(external::printf), arguments);
}

void LLVMIRGenerator::process(const Program &program) {
    visit(program.root);
    eraseDeadBlocks();
}

std::string LLVMIRGenerator::dump() const {
    std::string str;
    llvm::raw_string_ostream os(str);
    dump(os);
    return str;
}

void LLVMIRGenerator::dump(llvm::raw_ostream &stream) const {
    mod.print(stream, nullptr);
}

void LLVMIRGenerator::dumpToFile(const std::string &filename) const {
    std::error_code error;
    llvm::raw_fd_ostream os(filename, error);
    dump(os);
    os.close();
}

// NOLINTEND(readability-avoid-return-with-void-value)

1	#include "llvmir_generator.hpp"
2
3	#include <cstddef>
4	#include <cstdint>
5	#include <iterator>
6	#include <string>
7	#include <string_view>
8	#include <system_error>
9	#include <vector>
10
11	#include <llvm/IR/CFG.h>
12	#include <llvm/IR/Constants.h>
13	#include <llvm/IR/DerivedTypes.h>
14	#include <llvm/IR/Type.h>
15	#include <llvm/IR/Value.h>
16	#include <llvm/Support/Casting.h>
17	#include <llvm/Support/raw_ostream.h>
18
19	#include "compiler/optree/adaptors.hpp"
20	#include "compiler/optree/definitions.hpp"
21	#include "compiler/optree/operation.hpp"
22	#include "compiler/optree/program.hpp"
23	#include "compiler/optree/types.hpp"
24	#include "compiler/optree/value.hpp"
25	#include "compiler/utils/debug.hpp"
26
27	using namespace optree;
28	using namespace optree::llvmir_generator;
29
30	// NOLINTBEGIN(readability-avoid-return-with-void-value)
31	namespace {
32
33	namespace external {
34
35	constexpr std::string_view printf = "printf";
36	constexpr std::string_view scanf = "scanf";
37
38	} // namespace external
39
40	std::string_view getFormatSpecifier(const Type::Ptr &type) {	39✔
41	if (type->is<IntegerType>())	39✔
42	return "%lld";	13✔
43	if (type->is<FloatType>())	26✔
44	return "%lf";	8✔
45	if (type->is<StrType>())	18✔
46	return "%s";	18✔
47	if (type->is<NoneType>())	×
48	return "None";	×
49	if (type->is<PointerType>())	×
50	return "%p";	×
51	COMPILER_UNREACHABLE("unexpected type for a format specifier");	×
52	}
53
54	} // namespace
55
56	LLVMIRGenerator::LLVMIRGenerator(const std::string &moduleName)	7✔
57	: context(), builder(context), mod(moduleName, context), currentFunction(nullptr) {	7✔
58	}	7✔
59
60	llvm::Value *LLVMIRGenerator::findValue(const Value::Ptr &value) const {	192✔
61	auto it = values.find(value.get());	192✔
62	if (it == values.end())	192✔
63	return nullptr;	×
64	return it->second;	192✔
65	}
66
67	void LLVMIRGenerator::saveValue(const Value::Ptr &value, llvm::Value *llvmValue) {	151✔
68	values[value.get()] = llvmValue;	151✔
69	}	151✔
70
71	llvm::Type *LLVMIRGenerator::convertType(const Type::Ptr &type) {	96✔
72	if (type->is<NoneType>())	96✔
73	return llvm::Type::getVoidTy(context);	11✔
74	if (type->is<BoolType>())	85✔
75	return llvm::Type::getInt1Ty(context);	×
76	if (type->is<IntegerType>())	85✔
77	return llvm::Type::getIntNTy(context, type->bitWidth());	74✔
78	if (type->is<FloatType>())	11✔
79	return llvm::Type::getDoubleTy(context);	10✔
80	if (type->is<StrType>())	1✔
81	return llvm::Type::getIntNPtrTy(context, type->as<StrType>().charWidth);	×
82	if (type->is<PointerType>())	1✔
83	return llvm::PointerType::getUnqual(context);	1✔
84	COMPILER_UNREACHABLE("unexpected type");	×
85	}
86
87	llvm::BasicBlock *LLVMIRGenerator::createBlock() {	48✔
88	auto *bb = llvm::BasicBlock::Create(context, "bb", currentFunction);	48✔
89	basicBlocks.push_back(bb);	48✔
90	return bb;	48✔
91	}
92
93	void LLVMIRGenerator::eraseDeadBlocks() {	6✔
94	for (auto *&bb : basicBlocks) {	54✔
95	if (bb == nullptr)	48✔
96	continue;	×
97	if (llvm::pred_empty(bb) && !bb->isEntryBlock()) {	48✔
98	bb->eraseFromParent();	11✔
99	bb = nullptr;	11✔
100	}
101	}
102	}	6✔
103
104	llvm::Value *LLVMIRGenerator::normalizePredicate(const Value::Ptr &cond) {	1✔
105	auto *pred = findValue(cond);	1✔
106	if (!pred)	1✔
107	return nullptr;	×
108	if (pred->getType()->isIntegerTy(1))	1✔
109	return pred;	1✔
110	auto *i1Type = llvm::Type::getInt1Ty(context);	×
111	auto *trunc = builder.CreateTrunc(pred, i1Type);	×
112	return builder.CreateICmpEQ(trunc, llvm::ConstantInt::get(i1Type, 1U));	×
113	}
114
115	llvm::Value *LLVMIRGenerator::getGlobalString(const std::string &str) {	39✔
116	auto it = globalStrings.find(str);	39✔
117	if (it != globalStrings.end())	39✔
118	return it->second;	15✔
119	return globalStrings[str] = builder.CreateGlobalString(str);	24✔
120	}
121
122	llvm::FunctionCallee LLVMIRGenerator::getExternalFunction(std::string_view name) {	21✔
123	auto it = externalFunctions.find(name);	21✔
124	if (it != externalFunctions.end())	21✔
125	return it->second;	13✔
126	return externalFunctions[name] = loadExternalFunction(name);	8✔
127	}
128
129	llvm::FunctionCallee LLVMIRGenerator::loadExternalFunction(std::string_view name) {	8✔
130	auto createVarArgFunction = [&](std::string_view name) {	8✔
131	std::vector<llvm::Type *> arguments = {llvm::PointerType::getUnqual(context)};	8✔
132	auto *llvmType = llvm::FunctionType::get(llvm::Type::getInt32Ty(context),	8✔
133	{llvm::PointerType::getUnqual(context)}, /isVarArg/ true);	8✔
134	return mod.getOrInsertFunction(name, llvmType);	16✔
135	};	8✔
136
137	if (name == external::printf)	8✔
138	return createVarArgFunction(name);	6✔
139	if (name == external::scanf)	2✔
140	return createVarArgFunction(name);	2✔
141	COMPILER_UNREACHABLE("unexpected external function");	×
142	}
143
144	void LLVMIRGenerator::visit(const Operation::Ptr &op) {	217✔
145	if (auto concreteOp = op->as<ModuleOp>())	217✔
146	return visit(concreteOp);	217✔
147	if (auto concreteOp = op->as<FunctionOp>())	211✔
148	return visit(concreteOp);	211✔
149	if (auto concreteOp = op->as<FunctionCallOp>())	200✔
150	return visit(concreteOp);	200✔
151	if (auto concreteOp = op->as<ReturnOp>())	194✔
152	return visit(concreteOp);	194✔
153	if (auto concreteOp = op->as<ConstantOp>())	183✔
154	return visit(concreteOp);	183✔
155	if (auto concreteOp = op->as<ArithBinaryOp>())	108✔
156	return visit(concreteOp);	108✔
157	if (auto concreteOp = op->as<LogicBinaryOp>())	93✔
158	return visit(concreteOp);	93✔
159	if (auto concreteOp = op->as<ArithCastOp>())	92✔
160	return visit(concreteOp);	92✔
161	if (auto concreteOp = op->as<ArithUnaryOp>())	88✔
162	return visit(concreteOp);	88✔
163	if (auto concreteOp = op->as<LogicUnaryOp>())	88✔
164	return visit(concreteOp);	88✔
165	if (auto concreteOp = op->as<AllocateOp>())	88✔
166	return visit(concreteOp);	88✔
167	if (auto concreteOp = op->as<LoadOp>())	75✔
168	return visit(concreteOp);	75✔
169	if (auto concreteOp = op->as<StoreOp>())	48✔
170	return visit(concreteOp);	48✔
171	if (auto concreteOp = op->as<IfOp>())	30✔
172	return visit(concreteOp);	30✔
173	if (auto concreteOp = op->as<ThenOp>())	29✔
174	return visit(concreteOp);	29✔
175	if (auto concreteOp = op->as<ElseOp>())	29✔
176	return visit(concreteOp);	29✔
177	if (auto concreteOp = op->as<WhileOp>())	29✔
178	return visit(concreteOp);	29✔
179	if (auto concreteOp = op->as<ConditionOp>())	29✔
180	return visit(concreteOp);	29✔
181	if (auto concreteOp = op->as<ForOp>())	29✔
182	return visit(concreteOp);	29✔
183	if (auto concreteOp = op->as<InputOp>())	21✔
184	return visit(concreteOp);	21✔
185	if (auto concreteOp = op->as<PrintOp>())	15✔
186	return visit(concreteOp);	15✔
UNCOV 187	COMPILER_UNREACHABLE("unexpected operation");	×
188	}
189
190	void LLVMIRGenerator::visitBody(const Operation::Ptr &op) {	20✔
191	for (const auto &inner : op->body)	220✔
192	visit(inner);	200✔
193	}	20✔
194
195	void LLVMIRGenerator::visit(const ModuleOp &op) {	6✔
196	for (const auto &inner : op->body)	17✔
197	visit(inner);	11✔
198	}	6✔
199
200	void LLVMIRGenerator::visit(const FunctionOp &op) {	11✔
201	const auto &funcType = op.type();	11✔
202	std::vector<llvm::Type *> arguments;	11✔
203	std::vector<llvm::Type *> elemTypes;	11✔
204	for (const auto &arg : funcType.arguments) {	13✔
205	arguments.push_back(convertType(arg));	2✔
206	elemTypes.push_back(arg->is<PointerType>() ? convertType(arg->as<PointerType>().pointee) : nullptr);	2✔
207	}
208	auto llvmType = llvm::FunctionType::get(convertType(funcType.result), arguments, /isVarArg*/ false);	11✔
209	currentFunction = llvm::cast<llvm::Function>(mod.getOrInsertFunction(op.name(), llvmType).getCallee());	11✔
210	for (size_t i = 0; i < op->numInwards(); i++) {	13✔
211	auto *argValue = currentFunction->getArg(i);	2✔
212	saveValue(op->inward(i), argValue);	2✔
213	if (auto *elemType = elemTypes[i])	2✔
214	typedValues[argValue] = elemType;	1✔
215	}
216	auto *bb = createBlock();	11✔
217	builder.SetInsertPoint(bb);	11✔
218	visitBody(op);	11✔
219	}	11✔
220
221	void LLVMIRGenerator::visit(const FunctionCallOp &op) {	6✔
222	std::vector<llvm::Value *> arguments;	6✔
223	for (const auto &arg : op->operands)	10✔
224	arguments.push_back(findValue(arg));	4✔
225	auto *inst = builder.CreateCall(mod.getFunction(op.name()), arguments);	6✔
226	if (op->numResults() != 0)	6✔
227	saveValue(op.result(), inst);	6✔
228	}	6✔
229
230	void LLVMIRGenerator::visit(const ReturnOp &op) {	11✔
231	if (op->numOperands() == 0)	11✔
232	builder.CreateRetVoid();	11✔
233	else
234	builder.CreateRet(findValue(op.value()));	×
235	auto *bb = createBlock();	11✔
236	builder.SetInsertPoint(bb);	11✔
237	}	11✔
238
239	void LLVMIRGenerator::visit(const ConstantOp &op) {	75✔
240	const auto &type = op.result()->type;	75✔
241	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	75✔
242	if (type->is<BoolType>())	75✔
UNCOV 243	return result(llvm::ConstantInt::get(convertType(type), op.value().as<bool>()));	×
244	if (type->is<IntegerType>()) {	75✔
245	auto num = static_cast<int64_t>(op.value().as<NativeInt>());	54✔
246	auto value = llvm::ConstantInt::get(convertType(type), reinterpret_cast<uint64_t &>(num), /IsSigned*/ true);	54✔
247	return result(value);	54✔
248	}
249	if (type->is<FloatType>())	21✔
250	return result(llvm::ConstantFP::get(convertType(type), static_cast<double>(op.value().as<NativeFloat>())));	3✔
251	if (type->is<StrType>())	18✔
252	return result(getGlobalString(op.value().as<NativeStr>()));	18✔
UNCOV 253	COMPILER_UNREACHABLE("unexpected result type in ConstantOp");	×
254	}
255
256	void LLVMIRGenerator::visit(const ArithBinaryOp &op) {	15✔
257	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	15✔
258	auto *lhs = findValue(op.lhs());	15✔
259	auto *rhs = findValue(op.rhs());	15✔
260	switch (op.kind()) {	15✔
261	case ArithBinOpKind::AddI:	5✔
262	return result(builder.CreateAdd(lhs, rhs));	5✔
263	case ArithBinOpKind::SubI:	3✔
264	return result(builder.CreateSub(lhs, rhs));	3✔
265	case ArithBinOpKind::MulI:	3✔
266	return result(builder.CreateMul(lhs, rhs));	3✔
267	case ArithBinOpKind::DivI:	2✔
268	return result(builder.CreateSDiv(lhs, rhs));	2✔
269	case ArithBinOpKind::AddF:	1✔
270	return result(builder.CreateFAdd(lhs, rhs));	1✔
271	case ArithBinOpKind::SubF:	1✔
272	return result(builder.CreateFSub(lhs, rhs));	1✔
273	case ArithBinOpKind::MulF:	×
274	return result(builder.CreateFMul(lhs, rhs));	×
275	case ArithBinOpKind::DivF:	×
276	return result(builder.CreateFDiv(lhs, rhs));	×
277	default:	×
278	COMPILER_UNREACHABLE("unexpected kind in ArithBinaryOp");	×
279	}
280	}
281
282	void LLVMIRGenerator::visit(const LogicBinaryOp &op) {	1✔
283	const auto &type = op.lhs()->type;	1✔
284	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	1✔
285	auto *lhs = findValue(op.lhs());	1✔
286	auto *rhs = findValue(op.rhs());	1✔
287	switch (op.kind()) {	1✔
288	case LogicBinOpKind::Equal:	×
289	if (type->is<IntegerType>())	×
290	return result(builder.CreateICmpEQ(lhs, rhs));	×
291	return result(builder.CreateFCmpOEQ(lhs, rhs));	×
292	case LogicBinOpKind::NotEqual:	×
293	if (type->is<IntegerType>())	×
294	return result(builder.CreateICmpNE(lhs, rhs));	×
295	return result(builder.CreateFCmpONE(lhs, rhs));	×
296	case LogicBinOpKind::AndI:	×
297	return result(builder.CreateLogicalAnd(lhs, rhs));	×
298	case LogicBinOpKind::OrI:	×
299	return result(builder.CreateLogicalOr(lhs, rhs));	×
300	case LogicBinOpKind::LessI:	×
301	return result(builder.CreateICmpSLT(lhs, rhs));	×
302	case LogicBinOpKind::GreaterI:	1✔
303	return result(builder.CreateICmpSGT(lhs, rhs));	1✔
304	case LogicBinOpKind::LessEqualI:	×
305	return result(builder.CreateICmpSLE(lhs, rhs));	×
306	case LogicBinOpKind::GreaterEqualI:	×
307	return result(builder.CreateICmpSGE(lhs, rhs));	×
308	case LogicBinOpKind::LessF:	×
UNCOV 309	return result(builder.CreateFCmpOLT(lhs, rhs));	×
UNCOV 310	case LogicBinOpKind::GreaterF:	×
UNCOV 311	return result(builder.CreateFCmpOGT(lhs, rhs));	×
UNCOV 312	case LogicBinOpKind::LessEqualF:	×
UNCOV 313	return result(builder.CreateFCmpOLE(lhs, rhs));	×
UNCOV 314	case LogicBinOpKind::GreaterEqualF:	×
UNCOV 315	return result(builder.CreateFCmpOGE(lhs, rhs));	×
UNCOV 316	default:	×
UNCOV 317	COMPILER_UNREACHABLE("unexpected kind in LogicBinaryOp");	×
318	}
319	}
320
321	void LLVMIRGenerator::visit(const ArithCastOp &op) {	4✔
322	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	4✔
323	auto *operand = findValue(op.value());	4✔
324	auto *destType = convertType(op.result()->type);	4✔
325	switch (op.kind()) {	4✔
326	case ArithCastOpKind::IntToFloat:	4✔
327	return result(builder.CreateSIToFP(operand, destType));	4✔
328	case ArithCastOpKind::FloatToInt:	×
329	return result(builder.CreateFPToSI(operand, destType));	×
330	case ArithCastOpKind::ExtI:	×
UNCOV 331	return result(builder.CreateSExt(operand, destType));	×
UNCOV 332	case ArithCastOpKind::TruncI:	×
UNCOV 333	return result(builder.CreateTrunc(operand, destType));	×
334	case ArithCastOpKind::ExtF:	×
335	return result(builder.CreateFPExt(operand, destType));	×
336	case ArithCastOpKind::TruncF:	×
337	return result(builder.CreateFPTrunc(operand, destType));	×
338	default:	×
339	COMPILER_UNREACHABLE("unexpected kind in ArithCastOp");	×
340	}
341	}
342
UNCOV 343	void LLVMIRGenerator::visit(const ArithUnaryOp &op) {	×
UNCOV 344	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	×
UNCOV 345	auto *operand = findValue(op.value());	×
UNCOV 346	switch (op.kind()) {	×
UNCOV 347	case ArithUnaryOpKind::NegI:	×
UNCOV 348	return result(builder.CreateNeg(operand));	×
UNCOV 349	case ArithUnaryOpKind::NegF:	×
UNCOV 350	return result(builder.CreateFNeg(operand));	×
UNCOV 351	default:	×
UNCOV 352	COMPILER_UNREACHABLE("unexpected kind in ArithUnaryOp");	×
353	}
354	}
355
UNCOV 356	void LLVMIRGenerator::visit(const LogicUnaryOp &op) {	×
UNCOV 357	auto result = [&](llvm::Value *v) -> void { saveValue(op.result(), v); };	×
UNCOV 358	auto *operand = findValue(op.value());	×
UNCOV 359	switch (op.kind()) {	×
UNCOV 360	case LogicUnaryOpKind::Not:	×
UNCOV 361	return result(builder.CreateNot(operand));	×
UNCOV 362	default:	×
UNCOV 363	COMPILER_UNREACHABLE("unexpected kind in LogicUnaryOp");	×
364	}
365	}
366
367	void LLVMIRGenerator::visit(const AllocateOp &op) {	13✔
368	const auto &type = op.result()->type->as<PointerType>();	13✔
369	auto *llvmType = convertType(type.pointee);	13✔
370	llvm::Value *size = nullptr;	13✔
371	if (type.numElements == PointerType::dynamic)	13✔
372	size = findValue(op.dynamicSize());	2✔
373	else if (type.numElements > 1U)	11✔
374	size = llvm::ConstantInt::get(llvm::Type::getIntNTy(context, 64U), type.numElements);	2✔
375	auto *inst = builder.CreateAlloca(llvmType, size);	13✔
376	saveValue(op.result(), inst);	13✔
377	typedValues[inst] = llvmType;	13✔
378	}	13✔
379
380	void LLVMIRGenerator::visit(const LoadOp &op) {	27✔
381	auto *ptr = findValue(op.src());	27✔
382	auto *type = typedValues[ptr];	27✔
383	if (auto offset = op.offset()) {	27✔
384	auto *index = findValue(offset);	10✔
385	ptr = builder.CreateGEP(type, ptr, index);	10✔
386	}	27✔
387	saveValue(op.result(), builder.CreateLoad(type, ptr));	27✔
388	}	27✔
389
390	void LLVMIRGenerator::visit(const StoreOp &op) {	18✔
391	auto *ptr = findValue(op.dst());	18✔
392	if (auto offset = op.offset()) {	18✔
393	auto *index = findValue(offset);	13✔
394	ptr = builder.CreateGEP(typedValues[ptr], ptr, index);	13✔
395	}	18✔
396	builder.CreateStore(findValue(op.valueToStore()), ptr);	18✔
397	}	18✔
398
399	void LLVMIRGenerator::visit(const IfOp &op) {	1✔
400	auto *prevBlock = builder.GetInsertBlock();	1✔
401	auto *thenBlock = createBlock();	1✔
402	builder.SetInsertPoint(thenBlock);	1✔
403	visit(op.thenOp());	1✔
404	auto *newThenBlock = builder.GetInsertBlock();	1✔
405	auto *elseBlock = createBlock();	1✔
406	auto *nextBlock = elseBlock;	1✔
407	if (auto elseOp = op.elseOp()) {	1✔
408	builder.SetInsertPoint(elseBlock);	×
409	visit(elseOp);	×
410	nextBlock = createBlock();	×
411	builder.CreateBr(nextBlock);	×
412	}	1✔
413	builder.SetInsertPoint(newThenBlock);	1✔
414	builder.CreateBr(nextBlock);	1✔
415	builder.SetInsertPoint(prevBlock);	1✔
416	builder.CreateCondBr(normalizePredicate(op.cond()), thenBlock, elseBlock);	1✔
417	builder.SetInsertPoint(nextBlock);	1✔
418	}	1✔
419
420	void LLVMIRGenerator::visit(const ThenOp &op) {	1✔
421	visitBody(op);	1✔
422	}	1✔
423
424	void LLVMIRGenerator::visit(const ElseOp &op) {	×
UNCOV 425	visitBody(op);	×
UNCOV 426	}	×
427
UNCOV 428	void LLVMIRGenerator::visit(const WhileOp &op) {	×
UNCOV 429	auto *condBlock = createBlock();	×
UNCOV 430	builder.CreateBr(condBlock);	×
UNCOV 431	builder.SetInsertPoint(condBlock);	×
UNCOV 432	auto condOp = op.conditionOp();	×
UNCOV 433	visit(condOp);	×
UNCOV 434	auto *thenBlock = createBlock();	×
UNCOV 435	auto *nextBlock = createBlock();	×
UNCOV 436	builder.CreateCondBr(normalizePredicate(condOp.terminator()), thenBlock, nextBlock);	×
UNCOV 437	builder.SetInsertPoint(thenBlock);	×
UNCOV 438	for (auto it = std::next(op->body.begin()); it != op->body.end(); ++it)	×
UNCOV 439	visit(*it);	×
UNCOV 440	builder.CreateBr(condBlock);	×
UNCOV 441	builder.SetInsertPoint(nextBlock);	×
UNCOV 442	}	×
443
UNCOV 444	void LLVMIRGenerator::visit(const ConditionOp &op) {	×
UNCOV 445	visitBody(op);	×
UNCOV 446	}	×
447
448	void LLVMIRGenerator::visit(const ForOp &op) {	8✔
449	auto *llvmType = convertType(op.start()->type);	8✔
450	auto *allocaI = builder.CreateAlloca(llvmType);	8✔
451	builder.CreateStore(findValue(op.start()), allocaI);	8✔
452	auto *condBlock = createBlock();	8✔
453	builder.CreateBr(condBlock);	8✔
454	builder.SetInsertPoint(condBlock);	8✔
455	auto *loadedI = builder.CreateLoad(llvmType, allocaI);	8✔
456	saveValue(op.iterator(), loadedI);	8✔
457	auto *cond = builder.CreateICmpSLT(loadedI, findValue(op.stop()));	8✔
458	auto *thenBlock = createBlock();	8✔
459	auto *nextBlock = createBlock();	8✔
460	builder.CreateCondBr(cond, thenBlock, nextBlock);	8✔
461	builder.SetInsertPoint(thenBlock);	8✔
462	visitBody(op);	8✔
463	auto *nextI = builder.CreateAdd(loadedI, findValue(op.step()));	8✔
464	builder.CreateStore(nextI, allocaI);	8✔
465	builder.CreateBr(condBlock);	8✔
466	builder.SetInsertPoint(nextBlock);	8✔
467	}	8✔
468
469	void LLVMIRGenerator::visit(const InputOp &op) {	6✔
470	std::string format(getFormatSpecifier(op.dst()->type->as<PointerType>().pointee));	6✔
471	builder.CreateCall(getExternalFunction(external::scanf), {getGlobalString(format), findValue(op.dst())});	6✔
472	}	6✔
473
474	void LLVMIRGenerator::visit(const PrintOp &op) {	15✔
475	std::vector<llvm::Value *> arguments;	15✔
476	arguments.reserve(op->numOperands() + 1U);	15✔
477	arguments.push_back(nullptr);	15✔
478	std::string format;	15✔
479	format.reserve(4U * op->numOperands());	15✔
480	for (const auto &operand : op->operands) {	48✔
481	arguments.push_back(findValue(operand));	33✔
482	format += getFormatSpecifier(operand->type);	33✔
483	}
484	arguments.front() = getGlobalString(format);	15✔
485	builder.CreateCall(getExternalFunction(external::printf), arguments);	15✔
486	}	15✔
487
488	void LLVMIRGenerator::process(const Program &program) {	6✔
489	visit(program.root);	6✔
490	eraseDeadBlocks();	6✔
491	}	6✔
492
493	std::string LLVMIRGenerator::dump() const {	1✔
494	std::string str;	1✔
495	llvm::raw_string_ostream os(str);	1✔
496	dump(os);	1✔
497	return str;	2✔
498	}	1✔
499
500	void LLVMIRGenerator::dump(llvm::raw_ostream &stream) const {	7✔
501	mod.print(stream, nullptr);	7✔
502	}	7✔
503
504	void LLVMIRGenerator::dumpToFile(const std::string &filename) const {	6✔
505	std::error_code error;	6✔
506	llvm::raw_fd_ostream os(filename, error);	6✔
507	dump(os);	6✔
508	os.close();	6✔
509	}	6✔
510
511	// NOLINTEND(readability-avoid-return-with-void-value)

vla5924-practice / compiler-project / 13884489619

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous