【Clang/LLVM】CFGの生成

# はじめに
[きつねさんの本](https://www.amazon.co.jp/%E3%81%8D%E3%81%A4%E3%81%AD%E3%81%95%E3%82%93%E3%81%A7%E3%82%82%E3%82%8F%E3%81%8B%E3%82%8BLLVM-%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%92%E8%87%AA%E4%BD%9C%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%AC%E3%82%A4%E3%83%89%E3%83%96%E3%83%83%E3%82%AF-%E6%9F%8F%E6%9C%A8-%E9%A4%85%E5%AD%90/dp/4844334158)を用いてLLVMの勉強を始めたところ、LLVMのVersion違いのために、CFGの生成に失敗してしまいました。同じ問題に直面する方がいるかと思いましたので、この記事では、LLVMのVersion 14.0.6（2022年8月時点の最新）で確認したCFGの生成方法を紹介します。尚、今回生成するCFGは単純な分岐処理を行うプログラムを対象としたもので、最終的に以下のように表示されます。
![main.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2756450/3d931e60-c403-dca9-1542-a209e76a5e1d.png)
<!--
LLVM初学者が**LLVMの特徴であるSSAを理解する際にCFGの生成は役立ちます**。
しかし、CFGの生成方法として古い情報が共有されている場合があり、学習の障壁になることがあります。
この記事では、筆者が確認したCFGの生成方法を紹介することで、LLVM初学者の学習を助けることを目指しています。
-->
### 対象読者
LLVMに関する学習を開始した方
### 目標
CFGの生成ができるようになること
# 目次
1. LLVMとは
2. 環境構築
3. CFGの生成
4. まとめ
# 本文
## 1. LLVMとは
### 1.1 概要
LLVMは、プログラミング言語開発における主に**ミドルエンドとバックエンドの処理に必要な機能（コンパイル時、リンク時、実行時の最適化などの複雑な処理に関する機能）をAPIとして提供**することで、プログラミング言語の開発を支援します。

また、下記の図に示すように、LLVMを用いたプログラミング言語開発では、ミドルエンドが抽象化されているために、複数のフロントエンド、複数のバックエンドに対応することができます。

![Screenshot from 2022-08-14 10-52-21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2756450/525235b3-6da3-c815-5511-13b6b1d4a81e.png)
[引用元：Intro to LLVM](http://www.aosabook.org/en/llvm.html)


### 1.2 CFG （Control Flow Graph）
LLVMで解析する対象のプログラムはBasic Blockと呼ばれる単位に分解されます。
[Basic Block](https://llvm.org/doxygen/group__LLVMCCoreValueBasicBlock.html)とは、１つの入口と1つの出口を備え、内部に命令を含むコードのセクションです。
[CFG](https://releases.llvm.org/11.0.0/tools/flang/docs/ControlFlowGraph.html)は、1つ以上のBasic Blockの入口と出口を矢印でつないだグラフであり、プログラムの制御フローを可視化したものです。
<!--
### 1.3 SSA (Static Single Assignment)
(Wikipediaより引用)
「静的単一代入（せいてきたんいつだいにゅう、英: Static Single Assignment form, SSA）形式は、コンパイラ設計における 中間表現 (IR) のひとつで、各変数が一度のみ代入されるよう定義されたものである。」

各変数が一度のみ代入されるという単純な特徴から、IRに対するコンパイル最適化が容易になるという利点がある。
-->
## 2. 環境構築

### 2.1 事前準備
今回の環境を示します。
- OS
Ubuntu 20.04.3 LTS

- Kernel
5.15.0-46-generic

- Tool
clang 10.0.0-4ubuntu1 
cmake 3.16.3 
gcc 9.4.0
python 3.8.10
make 4.2.1
### 2.2 LLVMビルド
LLVMをビルドします。
```:/bin/bash
git clone https://github.com/llvm/llvm-project.git
cd llvm-project
mkdir build 
cd build
cmake -DLLVM_ENABLE_PROJECTS=clang -DCMAKE_BUILD_TYPE=Release -G "Unix Makefiles" ../llvm
make
make check-clang
```
### 2.3 環境変数の設定
buildしたbinのパスを通します。
また、includeへのパスを変数として定義しておきます。
```:.bashrc
# llvm binのパス : $HOME/llvm-project/build/bin
export LLVM_BIN_PATH = "$HOME/llvm-project/build/bin"
export PATH=$PATH:$LLVM_BIN_PATH
# llvm includeのパス : $HOME/llvm-project/llvm/include
export LLVM_INC_PATH = "$HOME/llvm-project/llvm/include"
```
## 3. CFGの生成
確認用に、分岐のあるソースコードを準備します。
```:main.cpp
#include <stdio.h>

int main(int argc, char ** argv) {
	int i;
	if(argc == 0){
		i = 1;
	}else{
		i=2;
	}
	return 0;
}
```
以下のコマンドを実行し、中間表現のコード（LLVM IR）を生成します。
```:/bin/bash
clang++ -S -emit-llvm -I ${LLVM_INC_PATH} -o main.ll main.cpp
```
以下のコマンドを実行し、CFGの情報を隠しファイル（.main.dot）として生成します。
```:/bin/bash
opt -dot-cfg main.ll -disable-output -enable-new-pm=0
```
これまでに生成されたファイルを確認します。
```:/bin/bash
ls -a
main.cpp  .main.dot  main.ll
```
以下のコマンドを実行し、png形式の画像を生成します。
```:/bin/bash
dot -Tpng .main.dot -o main.png
```
以下のコマンドを実行し、png形式に変換した画像を表示します。
```:/bin/bash
eog main.png 
```
冒頭にも示しましたが、無事に表示されることが確認できました。
![main.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2756450/3d931e60-c403-dca9-1542-a209e76a5e1d.png)

## 4. まとめ
LLVMにおけるCFGの生成方法について紹介しました。
 
## 参考文献
[LLVM Documentation](https://llvm.org/docs/index.html)
[LLVM Control Flow Graph](https://releases.llvm.org/11.0.0/tools/flang/docs/ControlFlowGraph.html)
[きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック](https://www.amazon.co.jp/%E3%81%8D%E3%81%A4%E3%81%AD%E3%81%95%E3%82%93%E3%81%A7%E3%82%82%E3%82%8F%E3%81%8B%E3%82%8BLLVM-%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%92%E8%87%AA%E4%BD%9C%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%AC%E3%82%A4%E3%83%89%E3%83%96%E3%83%83%E3%82%AF-%E6%9F%8F%E6%9C%A8-%E9%A4%85%E5%AD%90/dp/4844334158)
<!-- 
[LLVM Requirements](https://llvm.org/docs/GettingStarted.html#requirements)
-->