Compiler Development in C++

// Classic pipeline
Source text
  → Lexer    → Token stream
  → Parser   → AST
  → Semantic → Typed AST
  → Codegen  → LLVM IR / bytecode / machine code

enum class TokenKind {
    Number, Plus, Minus, Star, Slash,
    LParen, RParen, Eof, Invalid
};

struct Token {
    TokenKind kind;
    std::string_view text;
    int line, col;
};

class Lexer {
    std::string_view src_;
    size_t pos_ = 0;
    int line_ = 1, col_ = 1;

    char peek(int ahead = 0) const {
        return pos_ + ahead < src_.size() ? src_[pos_ + ahead] : '\0';
    }

    char advance() {
        char c = src_[pos_++];
        if (c == '\n') { ++line_; col_ = 1; } else ++col_;
        return c;
    }

public:
    explicit Lexer(std::string_view src) : src_(src) {}

    Token next() {
        // Skip whitespace
        while (pos_ < src_.size() && std::isspace(peek())) advance();
        if (pos_ >= src_.size()) return {TokenKind::Eof, {}, line_, col_};

        int start_line = line_, start_col = col_;
        size_t start = pos_;

        char c = advance();

        if (std::isdigit(c)) {
            while (std::isdigit(peek())) advance();
            if (peek() == '.' && std::isdigit(peek(1))) {
                advance();
                while (std::isdigit(peek())) advance();
            }
            return {TokenKind::Number, src_.substr(start, pos_ - start),
                    start_line, start_col};
        }
        switch (c) {
        case '+': return {TokenKind::Plus,   "+", start_line, start_col};
        case '-': return {TokenKind::Minus,  "-", start_line, start_col};
        case '*': return {TokenKind::Star,   "*", start_line, start_col};
        case '/': return {TokenKind::Slash,  "/", start_line, start_col};
        case '(': return {TokenKind::LParen, "(", start_line, start_col};
        case ')': return {TokenKind::RParen, ")", start_line, start_col};
        default:  return {TokenKind::Invalid, src_.substr(start,1), start_line, start_col};
        }
    }
};

// Polymorphic AST with unique_ptr ownership
struct Expr {
    virtual ~Expr() = default;
};
using ExprPtr = std::unique_ptr<Expr>;

struct NumberExpr : Expr {
    double value;
    explicit NumberExpr(double v) : value(v) {}
};

struct BinaryExpr : Expr {
    char op;
    ExprPtr left, right;
    BinaryExpr(char op, ExprPtr l, ExprPtr r)
        : op(op), left(std::move(l)), right(std::move(r)) {}
};

struct UnaryExpr : Expr {
    char op;
    ExprPtr operand;
};

// Variant-based AST (no virtual, value semantics)
using ExprV = std::variant<
    struct NumberNode,
    struct BinaryNode,
    struct VariableNode
>;

struct NumberNode { double value; };
struct BinaryNode {
    char op;
    std::shared_ptr<ExprV> left, right;
};
struct VariableNode { std::string name; };

class Parser {
    Lexer lexer_;
    Token current_;

    Token consume() {
        Token t = current_;
        current_ = lexer_.next();
        return t;
    }

    Token expect(TokenKind kind) {
        if (current_.kind != kind)
            throw std::runtime_error(
                std::format("expected {} at {}:{}", (int)kind, current_.line, current_.col));
        return consume();
    }

public:
    explicit Parser(std::string_view src) : lexer_(src) {
        current_ = lexer_.next();  // prime the pump
    }

    ExprPtr parse_expr() { return parse_additive(); }

private:
    ExprPtr parse_primary() {
        if (current_.kind == TokenKind::Number) {
            double val = std::stod(std::string(consume().text));
            return std::make_unique<NumberExpr>(val);
        }
        if (current_.kind == TokenKind::LParen) {
            consume();
            auto e = parse_expr();
            expect(TokenKind::RParen);
            return e;
        }
        throw std::runtime_error("expected expression");
    }

    ExprPtr parse_multiplicative() {
        auto left = parse_primary();
        while (current_.kind == TokenKind::Star || current_.kind == TokenKind::Slash) {
            char op = consume().text[0];
            left = std::make_unique<BinaryExpr>(op, std::move(left), parse_primary());
        }
        return left;
    }

    ExprPtr parse_additive() {
        auto left = parse_multiplicative();
        while (current_.kind == TokenKind::Plus || current_.kind == TokenKind::Minus) {
            char op = consume().text[0];
            left = std::make_unique<BinaryExpr>(op, std::move(left), parse_multiplicative());
        }
        return left;
    }
};

// Visitor interface
struct ExprVisitor {
    virtual ~ExprVisitor() = default;
    virtual void visit(NumberExpr&) = 0;
    virtual void visit(BinaryExpr&) = 0;
};

// Add accept() to AST nodes
struct Expr {
    virtual ~Expr() = default;
    virtual void accept(ExprVisitor& v) = 0;
};

struct NumberExpr : Expr {
    double value;
    void accept(ExprVisitor& v) override { v.visit(*this); }
};

struct BinaryExpr : Expr {
    char op; ExprPtr left, right;
    void accept(ExprVisitor& v) override { v.visit(*this); }
};

// Evaluator visitor
class Evaluator : public ExprVisitor {
    double result_;
public:
    double evaluate(Expr& e) { e.accept(*this); return result_; }

    void visit(NumberExpr& e) override { result_ = e.value; }
    void visit(BinaryExpr& e) override {
        double l = evaluate(*e.left);
        double r = evaluate(*e.right);
        switch (e.op) {
        case '+': result_ = l + r; break;
        case '-': result_ = l - r; break;
        case '*': result_ = l * r; break;
        case '/': result_ = l / r; break;
        }
    }
};

// std::visit with variant AST (no virtual)
double eval(const ExprV& node) {
    return std::visit(overloaded{
        [](const NumberNode& n) { return n.value; },
        [](const BinaryNode& b) {
            double l = eval(*b.left), r = eval(*b.right);
            switch (b.op) {
            case '+': return l + r;
            case '-': return l - r;
            case '*': return l * r;
            case '/': return l / r;
            default: throw std::runtime_error("bad op");
            }
        },
        [](const VariableNode&) -> double { throw std::runtime_error("no vars yet"); },
    }, node);
}

#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/IRBuilder.h>

class LLVMCodegen : public ExprVisitor {
    llvm::LLVMContext ctx_;
    std::unique_ptr<llvm::Module> module_;
    llvm::IRBuilder<> builder_;
    llvm::Value* value_ = nullptr;

public:
    LLVMCodegen() : module_(std::make_unique<llvm::Module>("jit", ctx_)),
                    builder_(ctx_) {}

    llvm::Value* codegen(Expr& e) { e.accept(*this); return value_; }

    void visit(NumberExpr& e) override {
        value_ = llvm::ConstantFP::get(ctx_, llvm::APFloat(e.value));
    }

    void visit(BinaryExpr& e) override {
        llvm::Value* l = codegen(*e.left);
        llvm::Value* r = codegen(*e.right);
        switch (e.op) {
        case '+': value_ = builder_.CreateFAdd(l, r, "addtmp"); break;
        case '-': value_ = builder_.CreateFSub(l, r, "subtmp"); break;
        case '*': value_ = builder_.CreateFMul(l, r, "multmp"); break;
        case '/': value_ = builder_.CreateFDiv(l, r, "divtmp"); break;
        }
    }
};

#include "clang/Tooling/CommonOptionsParser.h"
#include "clang/Tooling/Tooling.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"

using namespace clang;
using namespace clang::ast_matchers;

// Find all calls to a specific function
class FunctionCallFinder : public MatchFinder::MatchCallback {
public:
    void run(const MatchFinder::MatchResult& result) override {
        if (const auto* call = result.Nodes.getNodeAs<CallExpr>("call"))
            llvm::outs() << "Found call at line "
                         << result.SourceManager->getSpellingLineNumber(call->getBeginLoc())
                         << "\n";
    }
};

int main(int argc, const char** argv) {
    auto op = clang::tooling::CommonOptionsParser::create(argc, argv, MyCategory);
    clang::tooling::ClangTool tool(op->getCompilations(), op->getSourcePathList());

    FunctionCallFinder finder;
    MatchFinder match_finder;
    match_finder.addMatcher(
        callExpr(callee(functionDecl(hasName("malloc")))).bind("call"),
        &finder);

    return tool.run(clang::tooling::newFrontendActionFactory(&match_finder).get());
}

template<typename Value>
class SymbolTable {
    std::vector<std::unordered_map<std::string, Value>> scopes_;

public:
    void push_scope() { scopes_.emplace_back(); }
    void pop_scope()  { scopes_.pop_back(); }

    void define(std::string name, Value val) {
        scopes_.back()[std::move(name)] = std::move(val);
    }

    std::optional<Value> lookup(const std::string& name) const {
        for (auto it = scopes_.rbegin(); it != scopes_.rend(); ++it) {
            auto found = it->find(name);
            if (found != it->end()) return found->second;
        }
        return {};
    }
};

// Usage in semantic analysis
struct Type { std::string name; bool is_const; };
SymbolTable<Type> sym;

sym.push_scope();    // function scope
sym.define("x", Type{"int", false});
sym.define("y", Type{"double", true});
auto t = sym.lookup("x");  // {int, false}
sym.pop_scope();

#include "llvm/IR/Function.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"

// A function pass that prints each function's name and instruction count
struct InstructionCountPass : llvm::PassInfoMixin<InstructionCountPass> {
    llvm::PreservedAnalyses run(llvm::Function& F,
                                llvm::FunctionAnalysisManager& AM) {
        int count = 0;
        for (auto& BB : F)
            for (auto& I : BB)
                ++count;

        llvm::errs() << F.getName() << ": " << count << " instructions\n";

        // We haven't transformed anything — tell the pass manager all analyses remain valid
        return llvm::PreservedAnalyses::all();
    }

    // Required: mark this pass as not needing a module-level analysis
    static bool isRequired() { return true; }
};

// Register the pass as a plugin loadable by opt/clang:
llvm::PassPluginLibraryInfo getInstructionCountPluginInfo() {
    return {LLVM_PLUGIN_API_VERSION, "InstructionCount", LLVM_VERSION_STRING,
        [](llvm::PassBuilder& PB) {
            // Register with the pass pipeline parser
            PB.registerPipelineParsingCallback(
                [](llvm::StringRef Name, llvm::FunctionPassManager& FPM,
                   llvm::ArrayRef<llvm::PassBuilder::PipelineElement>) {
                    if (Name == "instruction-count") {
                        FPM.addPass(InstructionCountPass{});
                        return true;
                    }
                    return false;
                });
        }};
}

// The mandatory entry point for dynamically loaded plugins:
extern "C" LLVM_ATTRIBUTE_WEAK llvm::PassPluginLibraryInfo llvmGetPassPluginInfo() {
    return getInstructionCountPluginInfo();
}

# CMakeLists.txt for a pass plugin
find_package(LLVM REQUIRED CONFIG)
list(APPEND CMAKE_MODULE_PATH ${LLVM_CMAKE_DIR})
include(AddLLVM)

add_library(InstructionCountPass MODULE pass.cpp)
target_include_directories(InstructionCountPass PRIVATE ${LLVM_INCLUDE_DIRS})
target_compile_definitions(InstructionCountPass PRIVATE ${LLVM_DEFINITIONS})
# Link only what the pass uses — let the host (opt/clang) provide the rest
target_link_libraries(InstructionCountPass PRIVATE LLVMCore LLVMSupport)

# Compile a C file to LLVM IR
clang -O0 -S -emit-llvm example.c -o example.ll

# Run the pass with opt:
opt --load-pass-plugin=./InstructionCountPass.so \
    --passes="instruction-count" example.ll -S -o /dev/null

# Insert into the default O2 pipeline (runs just before O2 optimizations):
opt --load-pass-plugin=./InstructionCountPass.so \
    --passes="module(function(instruction-count),default<O2>)" example.ll -o opt.bc

// A pass that replaces calls to known 1-instruction functions with their body
struct TrivialInlinerPass : llvm::PassInfoMixin<TrivialInlinerPass> {
    llvm::PreservedAnalyses run(llvm::Function& F,
                                llvm::FunctionAnalysisManager&) {
        bool changed = false;
        for (auto& BB : F) {
            for (auto& I : BB) {
                auto* call = llvm::dyn_cast<llvm::CallInst>(&I);
                if (!call) continue;
                auto* callee = call->getCalledFunction();
                if (!callee || callee->size() != 1) continue;
                auto& callee_bb = callee->front();
                if (callee_bb.size() > 2) continue; // only trivial: 1 real instr + ret

                llvm::InlineFunctionInfo IFI;
                llvm::InlineResult res = llvm::InlineFunction(*call, IFI);
                if (res.isSuccess()) changed = true;
            }
        }
        return changed ? llvm::PreservedAnalyses::none()
                       : llvm::PreservedAnalyses::all();
    }
};

#include "clang/AST/ASTConsumer.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Frontend/FrontendPluginRegistry.h"

using namespace clang;

// Visitor: walks the AST and finds classes with raw-pointer member variables
class RawPtrChecker : public RecursiveASTVisitor<RawPtrChecker> {
    ASTContext& ctx_;
    DiagnosticsEngine& diag_;
    unsigned diag_id_;

public:
    explicit RawPtrChecker(ASTContext& ctx)
        : ctx_(ctx)
        , diag_(ctx.getDiagnostics())
        , diag_id_(diag_.getCustomDiagID(DiagnosticsEngine::Warning,
              "class member %0 is a raw pointer — consider a smart pointer")) {}

    bool VisitCXXRecordDecl(CXXRecordDecl* decl) {
        if (!decl->isThisDeclarationADefinition()) return true;

        for (auto* field : decl->fields()) {
            QualType qt = field->getType();
            if (qt->isPointerType()) {
                diag_.Report(field->getLocation(), diag_id_)
                    << field->getName();
            }
        }
        return true;  // continue traversal
    }
};

// Consumer: entry point per translation unit
class RawPtrConsumer : public ASTConsumer {
    RawPtrChecker checker_;
public:
    explicit RawPtrConsumer(ASTContext& ctx) : checker_(ctx) {}

    void HandleTranslationUnit(ASTContext& ctx) override {
        checker_.TraverseDecl(ctx.getTranslationUnitDecl());
    }
};

// FrontendAction: called by the compiler for each source file
class RawPtrAction : public PluginASTAction {
protected:
    std::unique_ptr<ASTConsumer> CreateASTConsumer(
            CompilerInstance& ci, llvm::StringRef) override {
        return std::make_unique<RawPtrConsumer>(ci.getASTContext());
    }

    bool ParseArgs(const CompilerInstance&,
                   const std::vector<std::string>&) override { return true; }

    // Run after the main action (parsing) completes
    PluginASTAction::ActionType getActionType() override {
        return AddAfterMainAction;
    }
};

// Register the plugin under the name "rawptr-check"
static FrontendPluginRegistry::Add<RawPtrAction>
    X("rawptr-check", "Warn on raw pointer class members");

# CMakeLists.txt for a Clang plugin
find_package(Clang REQUIRED CONFIG)
include_directories(${CLANG_INCLUDE_DIRS})

add_library(RawPtrPlugin MODULE plugin.cpp)
target_link_libraries(RawPtrPlugin PRIVATE clangAST clangFrontend clangBasic)

# Build and load the plugin during compilation:
clang++ -fplugin=./RawPtrPlugin.so -c myfile.cpp

# With extra plugin args:
clang++ -fplugin=./RawPtrPlugin.so -fplugin-arg-rawptr-check-verbose -c myfile.cpp

# Emit LLVM IR (text format .ll):
clang++ -O0 -S -emit-llvm example.cpp -o example.ll

# Emit optimized IR:
clang++ -O2 -S -emit-llvm example.cpp -o example_opt.ll

# See exactly what passes run at O2:
clang++ -O2 -mllvm -debug-pass-manager example.cpp -c 2>&1 | head -40

# Run specific passes manually with opt:
opt --passes="mem2reg,simplifycfg,instcombine" example.ll -S -o simplified.ll

# View the call graph
opt --passes="print<call-graph>" example.ll -S -disable-output 2>&1

# Emit bitcode (binary) then disassemble:
clang++ -O2 -emit-llvm -c example.cpp -o example.bc
llvm-dis example.bc -o example.ll

# Diff IR before and after a pass:
opt --passes="mem2reg" example.ll -S -o after.ll
diff <(cat example.ll) <(cat after.ll)

; function: int add(int a, int b)
define i32 @_Z3addii(i32 %a, i32 %b) {
entry:
  %add = add nsw i32 %a, %b   ; nsw = no signed wrap (UB assumption)
  ret i32 %add
}

; alloca + store/load (unoptimized -O0 output)
define i32 @_Z3addii(i32 %a, i32 %b) {
entry:
  %a.addr = alloca i32
  %b.addr = alloca i32
  store i32 %a, ptr %a.addr    ; write param to stack slot
  store i32 %b, ptr %b.addr
  %0 = load i32, ptr %a.addr   ; read back (mem2reg eliminates this)
  %1 = load i32, ptr %b.addr
  %add = add nsw i32 %0, %1
  ret i32 %add
}