Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

SSA最適化などで使われる支配辺境の例え話

はじめに

部屋を片付けていたら、タイガーブックが発掘されたんですよ。
そこで、SSA最適化の章を読んでいて支配辺境のことについて完全に理解した上に天才的な例え話を思いついたのでここに報告するものであります。

1. コードフロー

すべての道はローマに通じるとしましょう。
道はローマからトルコを通り、アフリカ、インドに通じていてシルクロードを通って中国、韓国、日本と通じています。
またインドからシンガポールを経由して日本に通る道もあります。そして、日本からは船でローマに使節団が送られ通じているとします。

このお話を図にすると

ローマ
^  |
|トルコーアフリカ
|  |
|  |
| インドーーーー中国
|  |       |
|  |      韓国
|シンガポール--+ |
|          ||
|            日本
+ーーーーーーーー

こんな図が書けます。

2. 支配木

ローマ
  |
トルコ
  | |
  | アフリカ
インドーーーーーーーーー
  |     |    |
シンガポール 日本  中国
            |
           韓国

支配木はこのような形になります。

3. 支配辺境

ローマ{ローマ}
トルコ{ローマ}
インド{ローマ}
アフリカ{}
中国{日本}
韓国{日本}
シンガポール{日本}
日本{ローマ}

となります。

参考になりそうなソース

https://github.com/caojoshua/CS142B-Java-Interpreter-Compiler/tree/d98dcfaa3c16599896618346f8a5a1136f5180b8/JavaByteCodeCompiler

https://github.com/Calsign/cs6120_work/tree/d8cb5c1558bcce0681f85147b9de8c2b17aa41be

https://github.com/stp59/adv-compilers/tree/fc94d14b11e5e4b8b4940d4b419e4791716bc614

https://github.com/priyasrikumar/6120/tree/5d00f93704622a21556a18ef54521f0243e008c0

https://github.com/backtracking/ocamlgraph/blob/master/src/dominator.ml

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away