(ソースコードメモ)GCCでのOpenMP/OpenACC実装を見てみる

# 1. はじめに
OpenMPおよびOpenACCは、CやFortranでディレクティブ(指示文)により、コンパイラに対して並列化を指示するものである。例えば、OpenMPの場合、以下のように`#pragma omp parallel`という指示文で指示する。これにより、明示的にマルチスレッドプログラミングをしなくても、コンパイラ側で処理が行われる。OpenACCの場合は、他デバイスの処理コード生成(NVIDIA GPUやAMD GPU等)が行われる。

```C++
 #pragma omp parallel
  {
    body;
  }
```
# 2. OpenMP/OpenACCの処理
OpenMP/OpenACCのディレクティブ(指示文)の処理は、フロントエンドだけでなく、GIMPLEのパス上でも行われている。そして、最終的にビルドイン関数を含んだライブラリを介して実行する。項目として示すと以下通りである。

- ディレクティブを検出しビルトイン関数に置き換える処理(コンパイラ)
- GCCのビルドイン関数(例：`GOMP_parallel`)として処理するlibgompに分かれる。(ランタイム)

## 2.1. GCCでのコンパイル
### コンパイルパス
コンパイラの中では、パーサの後、パス上でOpenMP/OpenACCの処理が行われている。
まず、パーサーは、C言語の場合、[`c/c-parser.c`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/c/c-parser.c)、C++言語の場合、[`cpp/parser.c`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/cp/parser.c)である。(余談:githubのコードは、1MBを超えると行指定しずらいのでコードのみリンクを張っている。)
その後、gimple形式での最適化を行う。ここで`pass_xxxx`が、gimpleの最適化関数である。関連するパス上の関数を上げると以下のとおりである。

- [gimplify.c:omp_notice_variable](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/gimplify.c#L7218-L7471)
- [gimplify.c:gimplify_expr](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/gimplify.c#L12235-L13498)
- pass_diagnose_omp_blocks
   - [omp-low.c:scan_omp_parallel()](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-low.c#L1871-L1935)
    - [omp-low.c:create_omp_child_function](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-low.c#L1659-L1778)
- pass_expand_omp
   - [omp-expand.c:expand_parallel_call](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-expand.c#L563-L769)
   - [omp-expand.c:execute_expand_omp](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-expand.c#L8375-L8403)

ここで、組み込み関数(builtin function)は以下で定義されている。

- [enum built_in_function](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-core.h#L163-L184)
- [static inline tree builtin_decl_explicit](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree.h#L5273-L5280)



### 組み込み関数(builtin)関数の生成
コンパイル時は、`pass_omp_expand`処理の延長で、`BUILT_IN_GOMP_PARALLEL`等の組み込み(builtin)関数の出力を行う。そして、`DEF_GOMP_BUILTIN`マクロでlibgompの関数である`GOMP_parallel`等へのマッピングを行う。

関連しているコードは以下である。

- [DEF_GOMP_BUILTIN (BUILT_IN_GOMP_PARALLEL, "GOMP_parallel"](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-builtins.def#L376-L377)
   - [buidins.def](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/builtins.def#L1044-L1048)
      - [enum built_in_function](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-core.h#L163-L184)


## 2.2. OpenMPのランタイム(libgomp)

### libgomp側
組み込み(builtin)関数の実体が、libgompにある。例えば、[`GOMP_parallel`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/parallel.c#L164-L173)等が定義されている。また、libgompは、環境変数により、OpenMPのスケジューリングを設定できる。このため、libgomp内には、[parse_schedule](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/env.c#L100-L204)や、[gomp_schedule_type](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/libgomp.h#L147-L155)等の関数がある。
ここでは、[`GOMP_parallel`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/team.c#L49-L61)関数を見ていく。同関数では、[`gomp_team_start`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/team.c#L300-L918)を呼び出して、スレッドを生成する。そして、中では、[`gomp_thread_start_data`](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/team.c#L49-L61)構造体で、スレッドを管理する。最終的に、`GOMP_parallel_end`関数およびその先の、`gomp_team_end`関数で同期して終了する。

```c++
void
GOMP_parallel (void (*fn) (void *), void *data, unsigned num_threads,
	       unsigned int flags)
{
  num_threads = gomp_resolve_num_threads (num_threads, 0);
  gomp_team_start (fn, data, num_threads, flags, gomp_new_team (num_threads),
		   NULL);
  fn (data);
  ialias_call (GOMP_parallel_end) ();
}
```

関連ソースコードは、主に以下のファイルである。

- [libgomp/](https://github.com/gcc-mirror/gcc/tree/releases/gcc-9.2.0/libgomp)
   - [libgomp.h](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/libgomp.h)
   - [parallel.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/parallel.c) GOMP_xxxxx 等の関数
   - [team.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/libgomp/team.c) gomp_team_xxx等の関数



# A. 参考資料
## A.1. 概要
- [OpenMPとOpenACCの違い](http://nkl.cc.u-tokyo.ac.jp/seminars/multicore/oacc-05.pdf#page=20)
- [独自CPU開発で学ぶコンピュータのしくみ](https://www.amazon.co.jp/dp/4798045365/)
    - GCCやBinutilsの新アーキへの移植概要を知るには良い本である。

## A.2. GCC
- [Openmp and automatic parallelization in gcc (2006)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.230.5179)
   - GCC 4.2の段階では、ICC9.0(Intel)より、SPEC OMP2001のベンチマークが1%程度早い。
- [Prototyping the automatic generation of MPI code from OpenMP programs in GCC(2008)](https://hal.archives-ouvertes.fr/hal-01366223/)


## A.3. libgomp
- [GNU libgomp](https://gcc.gnu.org/onlinedocs/libgomp/)
   - [3 OpenMP Environment Variables](https://gcc.gnu.org/onlinedocs/libgomp/#toc-OpenMP-Environment-Variables)
   - [10.10 Implementing PARALLEL construct](https://gcc.gnu.org/onlinedocs/libgomp/Implementing-PARALLEL-construct.html#Implementing-PARALLEL-construct)
- [Welcome to the home of GOMP](https://gcc.gnu.org/projects/gomp/)
- GCCWiki
   - [OpenMP](https://gcc.gnu.org/wiki/openmp)
   - [OpenACC](https://gcc.gnu.org/wiki/OpenACC)
   - [Offloading](https://gcc.gnu.org/wiki/Offloading)

## A.4. OpenMP
- [Specifications](https://www.openmp.org/specifications/)
  - [OpenMP Application Program Interface Version 3.0 May 2008（日本語版）](https://www.openmp.org/wp-content/uploads//OpenMP30spec-ja.pdf)
- [SPEC OMP®2012](https://www.spec.org/omp2012/)

## A.5. OpenACC
- [Speeding up Programs with OpenACC in GCC(2019/02)](https://archive.fosdem.org/2019/schedule/event/openacc/)
- [Improving GCC’s Performance on OpenACC Applications(2018/03)](https://www.openacc.org/sites/default/files/inline-images/UserGroupMeeting/OpenACC_Randy_allen_Usergroup.pdf)
   - OpenACCのGCC改造版の紹介

## A.6. gccのコンパイル手順
ubuntu 19.10でのgcc9.xのコンパイル手順は、以下のとおりである。なお、`make`で並列化オプション(`-j`)をつけないと非常に遅くなる。ここでは、8コアでコンパイルしているので8を入れている。5分程度かかる。一方このオプションを外すと20分以上かかる。

```bash
$ sudo apt update
$ sudo apt upgrade
$ sudo apt install gcc
$ sudo apt install make
$ sudo apt install build-essential
$ sudo apt install flex
$ git clone https://github.com/gcc-mirror/gcc/
$ cd gcc
$ git checkout releases/gcc-9.3.0
$ ./contrib/download_prerequisites
$ mkdir build && cd build
$ ../configure --enable-languages=c,c++ --prefix=/usr/local --disable-bootstrap --disable-multilib
$ make
$ make install
$ /usr/local/bin/gcc -v
$ /usr/local/bin/g++ -v
```
この手順は、gccのmaster(c5bac7d127f288fd2f8a1f15c3f30da5903141c6)(2020/04/18)に対して行ったが、コンパイルできた。


### 参考資料
- [Building GCC 9 on Ubuntu Linux](https://solarianprogrammer.com/2016/10/07/building-gcc-ubuntu-linux/)

## A.7. GCCのコンパイルパス

gimpleレベルでの最適化を行うコンパイルパスは、以下の通りである。コンパイルパスは、[passes.def](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/passes.def)で定義されている。

- [pass_diagnose_omp_blocks](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-low.c#L10936-L10953)
- [pass_lower_omp](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-low.c#L10634-L10644)
- [pass_expand_omp](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-expand.c#L8422-L8444)
- pass_simd_clone
- [pass_ipa_oacc](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-ssa-loop.c#L222-L238)
- [pass_ipa_oacc_kernels](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-ssa-loop.c#L265-L272)
- [pass_oacc_kernels](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-ssa-loop.c#L185-L195)
- [pass_expand_omp_ssa](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-expand.c#L8469-L8484)
- [pass_oacc_device_lower](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-offload.c#L1764-L1779)
- [pass_omp_device_lower](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-offload.c#L1977-L1994)
- [pass_omp_target_link](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-offload.c#L2021-L2040)

openmpに関するソースコードは以下の通りである。

- gcc/
   - [omp-low.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-low.c)
   - [omp-expand.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-expand.c)
   - [tree-ssa-loop.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/tree-ssa-loop.c)
   - [omp-offload.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-offload.c)
   - [omp-simd-clone.c](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9.2.0/gcc/omp-simd-clone.c)


### 参考文献
- [GNU Compiler Collection (GCC) Internals](https://gcc.gnu.org/onlinedocs/gccint/index.html#Top)
   - [9 Passes and Files of the Compiler](https://gcc.gnu.org/onlinedocs/gccint/Passes.html#Passes)
      - [9.5 Tree SSA passes](https://gcc.gnu.org/onlinedocs/gccint/Tree-SSA-passes.html#Tree-SSA-passes)