素人プログラマーRYOの勉強日誌。


by R-STUDY

COINS・・・その2

COINSの機能

LIRでのSSA最適化機能には

LIRからSSA形式への変換3種類

最小SSAへの変換(ssa-opt=mini)
半ば刈り込んだSSAへの変換(ssa-opt=semi)
刈り込んだSSA への変換(ssa-opt=prun)
SSA形式からLIRへの逆変換4種類

Briggsの方法(ssa-opt=brig)
Sreedharの方法I(ssa-opt=srd1)
Sreedharの方法II(ssa-opt=srd2)
Sreedharの方法III(ssa-opt=srd3)
コピー伝播(ssa-opt=cpyp)
共通部分式削除(ssa-opt=cse)
条件分岐を考慮した定数畳み込みと定数伝播(ssa-opt=cstp)
無用命令削除(ssa-opt=dce)
複雑な演算の展開(代入の右辺の演算子は1つだけとする)(ssa-opt=divex)
ループ不変コードの巻き上げ(ssa-opt=hli)
演算の強さの軽減とテスト置換(ssa-opt=osr)
質問伝播による部分冗長性削除(ssa-opt=preqp)
などがある。SSA最適化を指定する場合は、最初にSSA形式への変換を1つ選んで指定し、最後にLIRへの逆変換を1つ選んで指定し、その間にいくつかの最適化機能を実施したい順番に並べれば良い。同じ最適化機能を何箇所かで指定しても良い。

COINSの概要

注目すべきは、無用命令の削除。
これを行うことで、アルゴリズムの類似性を計るに於いて、無駄なコードを削除できる。
また、変数の変化を追うことで、While文とfor文の違いを吸収してくれるか?

COINSでは、各ソース言語プログラムをHIRに変換するフロントエンド
HIRからLIRに変換するモジュールが用意されている。それを利用することで
プログラムコードをSSA形式に直すことが可能となるはず。

問題は、コードクローン発見の手法とどう違いを出すか?という部分。
アルゴリズムが同じとコードが同じは等しいようで違う。
同じアルゴリズムで違う書き方を考え、考察する必要がある。
[PR]
# by R-STUDY | 2005-11-01 18:03 | 勉強メモ

COINSとは・・・その1

COINSは、複数言語、複数機種を扱えるコンパイラのインフラストラクチャ。教育、研究はもとより種々の用途のコンパイラの開発に利用することができる。

COINSで可能なこと

誰にでもわかるOpenMP(多分)

SSA形式とは?

LIRとは?プログラム言語
COINSにおけるLIRその1その2

・データフローダイアグラムとは
システム間のデータの流れを示す図。データを発生・吸収・処理・蓄積するシステムの間を、データの流れを示す矢印で繋いで作成する。データの流れが明確になることによって、効率化しやすい場所を容易に発見できる等のメリットがある。

も、覚えることいっぱい...。眠いし~。
[PR]
# by R-STUDY | 2005-10-28 07:22 | 勉強メモ

C言語の基本

そんなところからか?と突っ込まれそうな感じだけれども、
そんなところからです。

C言語の基本から...。
というより、プログラミングの基本って感じか?
ソートのお勉強です。
基本ってのは大切で、いつになっても役に立つはず。

ってことで、メモ。
TECHSCORE ~ C言語の基本 ~
[PR]
# by R-STUDY | 2005-10-27 20:47 | 勉強メモ
プログラムのコードを判定する場合、抽象構文木を利用して判定しようとすると、連続していないコードクローンを判定できない場合がある。
しかし、プログラム依存グラフを利用する方法では、プログラムをスライスし、変数の依存関係を調べることによってコードクローンの発見を行える為、連続していないコードクローンを発見することができる。

その依存関係は以下の条件による。

データ依存関係(DD)の定義
 ソースプログラム中の2文s,tに関して、以下の条件を満たすとき、
 変数vに関して文sから文tの間にデータ依存関係が存在するという。
   1.sはvを定義する。
   2.tはvを参照する。
   3.sからtへの1つ以上の実行経路の中に 、vの再定義が起こらない経路が少なくとも1つ存在する。
 制御依存関係(CD)の定義
 ソースプログラム中の2文s,tに関して、 以下の条件を満たすとき、
 文sから文tの間に制御依存関係が存在するという。
   1.sは条件文である。
   2.tの実行はsの判定結果に依存する。


プログラム評価のための問題の自動生成 参照
[PR]
# by R-STUDY | 2005-10-18 15:28 | 勉強メモ

あいまいな抽象構文木

抽象構文木を実際に描いてみようと思い、色々なサイト、色々な資料を見ながら
描いてみるが、正解かどうか分からない。
なにせ、構文木の書き方はある程度自由で作るコンパイラに合わせればいいと
どこかに書いてあったように、サイトによって結構マチマチな描き方がしてある。

とりあえずこのページに則って1つのプログラムを描き終わったところで力尽きた。
これでいいんだろうか?と思いながら、今週はここまで...。

明日はお休み。
月曜は、残り2つ分の構文木を描いてみて、同じ結果を返すが違うアルゴリズムで書かれたプログラムは、構文木の中でどこが似ていてどこが違うのかを考察してみることにする。またfor文+if文で書いたものをwhile文に直してみて、同じアルゴリズムで書かれているプログラムは抽象構文木で見た時にどこを見ることによって等しく見れるかも考察したい。
[PR]
# by R-STUDY | 2005-10-16 05:42 | 日記
文法にあいまいさがあると、LR 構文解析ができなくなるので、yacc は警告メッセージをだす。メッセージには2種類あり、 shift/reduce conflict, reduce/reduce conflictがある。shift/reduce conflictとは、文法規則が shift(つまり、さらに長い非終端記号にreduceできる)なのか、reduce(そこで打ち切って、非終端記号にしてしまう)か、解釈ができることを示す。この conflictは一概に文法定義が間違っているということではない場合がある。有名な例として、IF文の定義がある。

statement : IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
....;

これは次の場合にあいまいになる。
if (a > 0)
if (b > 0) c = 100;
else
c = 2000;

else を読んだとき、この token は内側の if 文の一部であると考え、遷移すればよいのだろうか、それとも、内側のif 文は完了したと考え、還元して、読みこんだ else は外側の if 文の一部であるとして遷移すればよいのだろうか?一般に yacc は、shift/reduce conflict がおきたときには、例外条件として、遷移(shift)を優先させる。したがって上のelse は内側の if 文の一部と解釈される。この解釈は、C 言語を始めほとんどの言語の仕様と一致するので、一般にif 文にまつわる shift/reduce conflict はそのままにしておいて問題ない。
[PR]
# by R-STUDY | 2005-10-16 05:05 | 勉強メモ

字句解析/構文解析

字句解析、構文解析の基本を忘れていることに気づき、勉強開始。
とりあえず、構文木を作れるようにせねば...。

字句解析、構文解析の基本 OS/Programming
[PR]
# by R-STUDY | 2005-10-16 01:33 | 勉強メモ
プログラムをやる上であんまり気にしてないけど、友人に教えてもらったのでちょっとメモ。
今まで、無意識、習慣的に基本的にfor文の条件文は0と比べていた。
教科書に載っていたからというのをそのままやってたわけだけど、意味があるらしい。

コーディングレベルの速度の最適化

足し算のほうが掛け算よりも計算コストが少ないとか、色々あるらしいけど、
とりあえず、まともなプログラムが作れるようになってからのお話かと(苦笑。
[PR]
# by R-STUDY | 2005-10-16 01:23 | 勉強メモ

研究を始める

そろそろ修士論文をやらねば、と思い立ち、どうせなら記録しておくかと
筆をとることにする。

論文のテーマは「バグモデルの自動生成」。
プログラミングで間違った例を自動的に作って初心者に見せようという
正直、無謀極まりないテーマ。

まずはその基盤となる、多くのプログラムから正しいもの、間違ったもの、そして
プログラムのアルゴリズムによってプログラムを分けるところから...。
その手始めとして、2つのプログラムを抽象構文木にして比べてみる。

むぅ...。プログラムを作ったはいいけど、これを抽象構文木にするのって面倒くさい。
やり方はこんな感じなのか...。

とりあえず、今日はここまででいいや。
明日は、プログラムを抽象構文木に分けることをやってみようと思う。
[PR]
# by R-STUDY | 2005-10-15 03:00 | 日記