第 4 章 生成 IR 代码的基础知识 - 学习笔记

1

%b.loop = phi i32 [ %rem, %while.body ], [ %b, %entry ]

1
2
3

[前序语句] → while.cond → while.body → while.cond
                ↓              ↓
            after.while ← (循环出口)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:352-375

void CGProcedure::emitStmt(WhileStatement *Stmt) {
  llvm::BasicBlock *WhileCondBB = llvm::BasicBlock::Create(
      CGM.getLLVMCtx(), "while.cond", Fn);
  llvm::BasicBlock *WhileBodyBB = llvm::BasicBlock::Create(
      CGM.getLLVMCtx(), "while.body", Fn);
  llvm::BasicBlock *AfterWhileBB = llvm::BasicBlock::Create(
      CGM.getLLVMCtx(), "after.while", Fn);

  Builder.CreateBr(WhileCondBB);   // 当前块跳到条件块
  sealBlock(Curr);                 // 密封当前块

  setCurr(WhileCondBB);
  llvm::Value *Cond = emitExpr(Stmt->getCond());
  Builder.CreateCondBr(Cond, WhileBodyBB, AfterWhileBB);

  setCurr(WhileBodyBB);
  emit(Stmt->getWhileStmts());
  Builder.CreateBr(WhileCondBB);   // 循环体末尾回到条件
  sealBlock(WhileCondBB);          // 密封条件块（前驱已全部确定）
  sealBlock(Curr);

  setCurr(AfterWhileBB);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:316-350

void CGProcedure::emitStmt(IfStatement *Stmt) {
  bool HasElse = Stmt->getElseStmts().size() > 0;

  llvm::BasicBlock *IfBB = llvm::BasicBlock::Create(...);
  llvm::BasicBlock *ElseBB = HasElse ? ... : nullptr;
  llvm::BasicBlock *AfterIfBB = llvm::BasicBlock::Create(...);

  llvm::Value *Cond = emitExpr(Stmt->getCond());
  Builder.CreateCondBr(Cond, IfBB, HasElse ? ElseBB : AfterIfBB);
  sealBlock(Curr);

  setCurr(IfBB);
  emit(Stmt->getIfStmts());
  if (!Curr->getTerminator()) Builder.CreateBr(AfterIfBB);
  sealBlock(Curr);

  if (HasElse) {
    setCurr(ElseBB);
    emit(Stmt->getElseStmts());
    if (!Curr->getTerminator()) Builder.CreateBr(AfterIfBB);
    sealBlock(Curr);
  }
  setCurr(AfterIfBB);
}

1
2
3
4
5
6
7
8
9

// Chapter04/tinylang/include/tinylang/CodeGen/CGProcedure.h:26-41

struct BasicBlockDef {
  llvm::DenseMap<Decl *, llvm::TrackingVH<llvm::Value>> Defs;  // 变量/形参 → 当前值
  llvm::DenseMap<llvm::PHINode *, Decl *> IncompletePhis;    // 待补全的 phi
  unsigned Sealed : 1;                                        // 块是否已密封
};

llvm::DenseMap<llvm::BasicBlock *, BasicBlockDef> CurrentDef;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:33-53

llvm::Value *CGProcedure::readLocalVariableRecursive(
    llvm::BasicBlock *BB, Decl *Decl) {
  llvm::Value *Val = nullptr;
  if (!CurrentDef[BB].Sealed) {
    // 块未密封：插入空 phi，避免循环
    llvm::PHINode *Phi = addEmptyPhi(BB, Decl);
    CurrentDef[BB].IncompletePhis[Phi] = Decl;
    Val = Phi;
  } else if (auto *PredBB = BB->getSinglePredecessor()) {
    // 单前驱：直接从前驱读取
    Val = readLocalVariable(PredBB, Decl);
  } else {
    // 多前驱：创建 phi，收集所有前驱的值
    llvm::PHINode *Phi = addEmptyPhi(BB, Decl);
    writeLocalVariable(BB, Decl, Phi);
    Val = addPhiOperands(BB, Decl, Phi);
  }
  writeLocalVariable(BB, Decl, Val);
  return Val;
}

1
2
3
4
5
6
7
8
9

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:98-106

void CGProcedure::sealBlock(llvm::BasicBlock *BB) {
  for (auto PhiDecl : CurrentDef[BB].IncompletePhis) {
    addPhiOperands(BB, PhiDecl.second, PhiDecl.first);
  }
  CurrentDef[BB].IncompletePhis.clear();
  CurrentDef[BB].Sealed = true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:72-96

llvm::Value *CGProcedure::optimizePhi(llvm::PHINode *Phi) {
  llvm::Value *Same = nullptr;
  for (llvm::Value *V : Phi->incoming_values()) {
    if (V == Same || V == Phi) continue;
    if (Same && V != Same) return Phi;  // 有不同值，保留 phi
    Same = V;
  }
  if (Same == nullptr)
    Same = llvm::UndefValue::get(Phi->getType());
  // 替换 phi 后，递归优化使用该 phi 的其他 phi
  Phi->replaceAllUsesWith(Same);
  Phi->eraseFromParent();
  for (auto *P : CandidatePhis) optimizePhi(P);
  return Same;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:154-166

llvm::Type *CGProcedure::mapType(Decl *Decl, bool HonorReference) {
  if (auto *FP = llvm::dyn_cast<FormalParameterDeclaration>(Decl)) {
    if (FP->isVar() && HonorReference)
      return llvm::PointerType::get(CGM.getLLVMCtx(), 0);
    return CGM.convertType(FP->getType());
  }
  if (auto *V = llvm::dyn_cast<VariableDeclaration>(Decl))
    return CGM.convertType(V->getType());
  return CGM.convertType(llvm::cast<TypeDeclaration>(Decl));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:195-204

if (FP->isVar()) {
  llvm::AttrBuilder Attr(CGM.getLLVMCtx());
  llvm::TypeSize Sz = CGM.getModule()->getDataLayout()
      .getTypeStoreSize(CGM.convertType(FP->getType()));
  Attr.addDereferenceableAttr(Sz);   // 指针可解引用
  Attr.addAttribute(llvm::Attribute::NoCapture);  // 不捕获
  Arg.addAttrs(Attr);
}

1
2
3

CodeGenerator (顶层入口)
    └── CGModule (模块级：全局变量、过程)
            └── CGProcedure (过程级：函数体、SSA)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Chapter04/tinylang/lib/CodeGen/CodeGenerator.cpp
std::unique_ptr<llvm::Module>
CodeGenerator::run(ModuleDeclaration *Mod, std::string FileName) {
  std::unique_ptr<llvm::Module> M =
      std::make_unique<llvm::Module>(FileName, Ctx);
  M->setTargetTriple(TM->getTargetTriple().getTriple());
  M->setDataLayout(TM->createDataLayout());
  CGModule CGM(M.get());
  CGM.run(Mod);
  return M;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Chapter04/tinylang/lib/CodeGen/CGModule.cpp:42-60

void CGModule::run(ModuleDeclaration *Mod) {
  for (auto *Decl : Mod->getDecls()) {
    if (auto *Var = llvm::dyn_cast<VariableDeclaration>(Decl)) {
      llvm::GlobalVariable *V = new llvm::GlobalVariable(
          *M, convertType(Var->getType()),
          /*isConstant=*/false,
          llvm::GlobalValue::PrivateLinkage, nullptr,
          mangleName(Var));
      Globals[Var] = V;
    } else if (auto *Proc = llvm::dyn_cast<ProcedureDeclaration>(Decl)) {
      CGProcedure CGP(*this);
      CGP.run(Proc);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Chapter04/tinylang/lib/CodeGen/CGModule.cpp:25-35

std::string CGModule::mangleName(Decl *D) {
  std::string Mangled("_t");
  llvm::SmallVector<llvm::StringRef, 4> Parts;
  for (; D; D = D->getEnclosingDecl())
    Parts.push_back(D->getName());
  while (!Parts.empty()) {
    llvm::StringRef Name = Parts.pop_back_val();
    Mangled.append(llvm::Twine(Name.size()).concat(Name).str());
  }
  return Mangled;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:210-261

plus      → CreateNSWAdd
minus     → CreateNSWSub
star      → CreateNSWMul
kw_DIV    → CreateSDiv
kw_MOD    → CreateSRem
equal     → CreateICmpEQ
hash      → CreateICmpNE
less      → CreateICmpSLT
lessequal → CreateICmpSLE
greater   → CreateICmpSGT
greaterequal → CreateICmpSGE
kw_AND    → CreateAnd
kw_OR     → CreateOr

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// Chapter04/tinylang/lib/CodeGen/CGProcedure.cpp:402-340

void CGProcedure::run(ProcedureDeclaration *Proc) {
  this->Proc = Proc;
  Fty = createFunctionType(Proc);
  Fn = createFunction(Proc, Fty);

  llvm::BasicBlock *BB = llvm::BasicBlock::Create(
      CGM.getLLVMCtx(), "entry", Fn);
  setCurr(BB);

  // 初始化形参映射
  for (auto Pair : llvm::enumerate(Fn->args())) {
    FormalParams[FP] = Arg;
    writeLocalVariable(Curr, FP, Arg);
  }

  // 聚合类型局部变量（如有）分配 alloca
  for (auto *D : Proc->getDecls()) {
    if (auto *Var = llvm::dyn_cast<VariableDeclaration>(D)) {
      if (Ty->isAggregateType()) {
        llvm::Value *Val = Builder.CreateAlloca(Ty);
        writeLocalVariable(Curr, Var, Val);
      }
    }
  }

  emit(Proc->getStmts());
  if (!Curr->getTerminator())
    Builder.CreateRetVoid();
  sealBlock(Curr);
}

1
2

createFunctionType(Proc)  → llvm::FunctionType::get(ResultTy, ParamTypes, false)
createFunction(Proc, Fty) → llvm::Function::Create(FTy, ExternalLinkage, mangleName(Proc), M)

1
2
3
4

main → InitLLVM → 初始化目标 → createTargetMachine
     → 解析 (Lexer → Parser → Sema)
     → CodeGenerator::create(Ctx, TM) → CG->run(Mod, InputFile)
     → emit(Argv[0], M.get(), TM, InputFile)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// Chapter04/tinylang/tools/driver/Driver.cpp:58-85

llvm::TargetMachine *createTargetMachine(const char *Argv0) {
  llvm::Triple Triple = !MTriple.empty()
      ? llvm::Triple::normalize(MTriple)
      : llvm::sys::getDefaultTargetTriple();
  llvm::TargetOptions TargetOptions =
      codegen::InitTargetOptionsFromCodeGenFlags(Triple);
  std::string CPUStr = codegen::getCPUStr();
  std::string FeatureStr = codegen::getFeaturesStr();

  const llvm::Target *Target =
      llvm::TargetRegistry::lookupTarget(codegen::getMArch(), Triple, Error);
  if (!Target) { /* 错误处理 */ }

  return Target->createTargetMachine(
      Triple.getTriple(), CPUStr, FeatureStr, TargetOptions,
      std::optional<llvm::Reloc::Model>(codegen::getRelocModel()));
}

1
2
3
4
5

InputFile           // 位置参数，默认 "-"
OutputFilename (-o) // 输出文件名
MTriple             // 覆盖目标三元组
EmitLLVM            // 输出 IR 而非汇编
+ codegen::RegisterCodeGenFlags  // -march, -mcpu, -mattr 等

1
2

tinylang --filetype=obj Gcd.mod
# 生成 Gcd.o

1
2

tinylang --filetype=asm --emit-llvm -o - Gcd.mod
# 输出到标准输出

1
2
3
4
5
6
7
8
9

// callgcd.c
extern long _t3Gcd3GCD(long, long);

int main(int argc, char *argv[]) {
  printf("gcd(25, 20) = %ld\n", _t3Gcd3GCD(25, 20));
  printf("gcd(3, 5) = %ld\n", _t3Gcd3GCD(3, 5));
  printf("gcd(21, 28) = %ld\n", _t3Gcd3GCD(21, 28));
  return 0;
}

1
2
3

tinylang --filetype=obj Gcd.mod
clang callgcd.c Gcd.o -o gcd
./gcd

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

Chapter04/tinylang/
├── include/tinylang/
│   ├── CodeGen/
│   │   ├── CodeGenerator.h
│   │   ├── CGModule.h
│   │   └── CGProcedure.h
│   ├── AST/、Basic/、Lexer/、Parser/、Sema/
├── lib/
│   ├── CodeGen/
│   │   ├── CodeGenerator.cpp
│   │   ├── CGModule.cpp
│   │   └── CGProcedure.cpp
│   └── ...
├── tools/driver/
│   └── Driver.cpp
└── examples/
    ├── Gcd.mod
    └── callgcd.ll