# HG changeset patch # User kent # Date 1265024256 -32400 # Node ID aa09c34b90d36b01d3f93e712ff10ad0a89fcef6 # Parent e9ecd5b5f29a11c574083d79f5f2c2da6805c3c8 add quicksort_for_pcc add sources, figures. diff -r e9ecd5b5f29a -r aa09c34b90d3 .hgignore --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/.hgignore Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,14 @@ +syntax: glob + +*.o +*.s + +.*.swp +.*.swo +*.aux +*.lof +*.log +*.lot +*.out +*.toc + diff -r e9ecd5b5f29a -r aa09c34b90d3 cbc.tex --- a/cbc.tex Fri Jan 29 15:45:41 2010 +0900 +++ b/cbc.tex Mon Feb 01 20:37:36 2010 +0900 @@ -11,8 +11,8 @@ オブジェクト指向技術とそれに基づいたJava などの言語が注目されているが 、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ -ベルな言語による記述に比べて、余分な条件判断(Method search, Meta level -での実行) を増やしてしまい、コンパクトで高速な応答を期待される +ベルな言語による記述に比べて、余分な条件判断（Method search, Meta level +での実行） を増やしてしまい、コンパクトで高速な応答を期待される Real-time 処理や組み込み用途には適さない。 ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記 @@ -66,7 +66,7 @@ 、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移 記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に -適した言語を作ることを考え、スタックマシンを避けてContinuation(継続) +適した言語を作ることを考え、スタックマシンを避けてContinuation（継続） が導入されている。 @@ -78,9 +78,10 @@ 呼出し元はスタックに復帰先アドレス及び環境を保持しておく事で呼出し先か らの復帰を可能とする。これはcall-return制御と呼ばれるものである（図 \ref{fig:call-return}）。 -しかし復帰先さえ決まっていれば、このcall-return制御は図 -\ref{fig:continuation}の様に手続き呼び出しの前後で分割する事ができ、環 -境の保持を伴わないシーケンシャルな呼び出しに変換する事ができる。 +しかし復帰先が決まっていて環境を受け継ぐことができれば、この +call-return制御は図 \ref{fig:continuation}の様に手続き呼び出しの前後で +分割する事ができ、スタック操作を伴わないシーケンシャルな呼び出しに変換 +する事ができる。 これは継続制御構造と呼ばれている。schemeのcall-with-continuationの実装 や、 Java,C++の例外処理、Cのsetjmp()/longjmp()による大域脱出もこの継続 制御の一種である。 @@ -119,7 +120,7 @@ %と同様の記述が可能であり、処理単位としてはステートメントより大きいもの %となる。 -\subsection{軽量継続（light-weight continuation）} +\subsection{軽量継続(light-weight continuation)} コードセグメントはCにおける関数とは違い、呼出し元への復帰は存在しない。 そのためコードセグメントの処理の末尾で別のコードセグメントへ継続するこ とになる。CbCではこの継続制御を``軽量継続''(light-weight continuation) @@ -163,7 +164,7 @@ \section{C with Continuation} -\ref{chp:purp}でも述べたようにCbCはCと互換性を持つことが望ましい。 +\ref{chp:intro}でも述べたようにCbCはCと互換性を持つことが望ましい。 CbCをCと相互に利用するためには、Cの関数から継続を行った場合に元の環境 に戻るための、特殊な継続を導入する必要がある。これを環境付き継続と呼ぶ。 @@ -171,8 +172,8 @@ CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え られるので（図 \ref{fig:cwc}）、CwCのコンパイラをCbCに使用する事ができ る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc -、共に厳密にはCwCのコンパイラである。すなわち、Cの関数やforなどを使う -ことができ、mcでは環境付き継続も実装されている。 +共に実際にはCwCのコンパイラとして実装されている。すなわち、Cの関数や +forなどを使うことができ、mcでは環境付き継続も実装されている。 \begin{figure}[htpb] \begin{center} @@ -186,15 +187,26 @@ \subsection{環境付き継続} 環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に \_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ -ード\ref{}参照。 +ード\ref{code:cbcreturn}参照。 継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する 事で元のCの環境に復帰することが可能となる。 ただし復帰先は\_\_returnを参照した関数が終了する位置である。 - +図\ref{fig:cbcreturn}にこの様子を表した。 \lstinputlisting[ caption=\_\_returnの例, - label=code:return-example] - {sources/return-example.cbc} + label=code:cbcreturn, + emph=\_\_return] + {sources/cbcreturn.cbc} +この様な形にすることでcode segment側では関数から呼ばれたか、コードセグ +メントからの継続かを考慮する必要がない。また、\verb|funcA|からもその内 +部でコードセグメントが使われていることを隠蔽できる。 +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=.6\textwidth]{figures/cbcreturn.eps} + \end{center} + \caption{\_\_returnの例} + \label{fig:cbcreturn} +\end{figure}% @@ -204,7 +216,7 @@ \section{gccベースコンパイラの現時点の問題点} - +\label{sec:cbc-problem} 当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも @@ -217,7 +229,6 @@ 以下にその問題点を列記する。 %この問題に対せる解決を \ref{chp:impl}章にて説明する。 - \begin{itemize} \item 環境付き継続 @@ -227,9 +238,9 @@ \item 並列代入 CbCでは現在のコードセグメントのインタフェイスと次に継続するコード - セグメントの引数は同じメモリスペース(もしくはレジスタ)に格納してい - る。そのためコード\ref{code:paralell_example}のように変数の値を入 - れ替えるような処理では並列代入が行われることになる。 + セグメントの引数は同じメモリスペース（もしくはレジスタ）に格納して + いる。そのためコード\ref{code:paralell_example}のように変数の値を + 入れ替えるような処理では並列代入が行われることになる。 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる 複雑な並列代入ではバグが見つかっている。 \lstinputlisting[ @@ -243,12 +254,16 @@ (indirect call)の様にコードセグメントポインタを用いた間接継続が可 能である。 \lstinputlisting[ - caption=間接継続の例(2つめのgoto文), + caption=間接継続の例（2つめのgoto文）, label=code:indirect-example] {sources/indirect-example.cbc} しかしPowerPCアーキテクチャでは最適化の問題でこの機能が働かないこ とが分かっている。 + 間接継続はCbCでのプログラミングには必須であり、また本研究室の主要 + プロジェクトであるCeriumはPS3をメインターゲットとしているため、こ + の対応は必須のものである。 + \item プロトタイプ宣言 Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。 @@ -256,6 +271,7 @@ 述という性質上、プログラムを記述する際は上から下に実行順にコードセ グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大 な数になる。 + これはプログラミングにおける障害とも言える。 \item x86での継続制御のオーバヘッド @@ -267,4 +283,10 @@ \end{itemize} +これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ +ていた。 +%特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。 +次章ではこれらの問題の解決を行う。 + + diff -r e9ecd5b5f29a -r aa09c34b90d3 evaluations.tex --- a/evaluations.tex Fri Jan 29 15:45:41 2010 +0900 +++ b/evaluations.tex Mon Feb 01 20:37:36 2010 +0900 @@ -7,6 +7,7 @@ 最後に、\ref{chp:task}章のTaskManagerの開発を元に、CbC言語そのものの記述性、プログラミング手法などについて考察する。 + \section{gccでを使うことの利点・欠点} \label{sec:merit} @@ -86,6 +87,9 @@ % 互換性,ソースコード、ABI + + + \section{性能評価} \subsection{評価手法と環境} @@ -223,3 +227,10 @@ +\section{本研究における成果} +本研究では、これまでバグが多くプログラムの動作に問題のあった +GCCベースのCbCコンパイラを、実用的なプログラムが動くレベルまで改善する +ことができた。 + + +\section{以前のバージョンとの速度比較} diff -r e9ecd5b5f29a -r aa09c34b90d3 figures/cbcreturn.dia Binary file figures/cbcreturn.dia has changed diff -r e9ecd5b5f29a -r aa09c34b90d3 figures/interfacestack.dia Binary file figures/interfacestack.dia has changed diff -r e9ecd5b5f29a -r aa09c34b90d3 figures/tailcall.dia Binary file figures/tailcall.dia has changed diff -r e9ecd5b5f29a -r aa09c34b90d3 introduction.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/introduction.tex Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,124 @@ +\chapter{序論} +\label{chp:intro} +\pagenumbering{arabic} + +%% 問題提起 +%% 解決案の提示 +%% 研究目標 +%% 本論文の各章の概要 + + +\section{背景と目的} + + +企業システムの多様化、IT導入の加速により、ソフトウェアは大規模化・複雑 +化する傾向にある。また家電製品のデジタル化も進み、組み込みシステムの需 +要も増大している。 + +それにともないハードウェアはムーアの法則よろしく驚異的な進歩を遂げ、近 +年はCPUのマルチコア化が進み、また新たな段階を築こうとしている。 + +ハードウェアの進歩に対し、ソフトウェアの開発に用いられる記述言語は、オ +ブジェクト指向プログラミングの発明・導入やデザインパターンに見られる技 +術の集約などが行われ、注目されてきた。 +%しかしながら90年代以降、言語その物に対する大きな変化は見られない。 +オブジェクト指向を主としたJavaはその有用性が認められ多くのシステム開発 +に取り入られている。 +しかしその反面、Cなどの低レベルな言語による記述に比べてこれらの技術は +余分な条件判断やメモリアクセスを増やしてしまう。そのため軽量かつ高速な +応答が要求される Real-time処理や組み込み用途には適さない。 + +またCellに見られるような複雑なアーキテクチャをもつマシンではプログラミ +ング自体も複雑になる。Cで記述されたプログラムからアーキテクチャに直接 +関わる命令 （DMAやシグナル）を使用するのでは、高級言語の設計思想と矛盾す +るともみられる。 + +大規模システムにおけるバグの存在も深刻な問題である。 +テストファーストな開発スタイルなどで工学的なアプローチからバグの抑制が +試みられているが、完全な排除は難しい。数学的なアプローチから無矛盾を証 +明する技術の研究も進んでいるが、現在のスタックベースのプログラミングは +状態数が膨大になり、実用化された例は少ない。しかしマルチコアの台頭によ +り並列プログラミングの必要性も高まっており、これからより検証の必要性が +増すと考えられる。 + +ハードウェアの進化、数学的検証にソフトウェアが対応するためにはこれまで +とは違う新たな視点を持ったプログラミング言語が望ましい。 +しかし既存のソフトウェアやシステムは膨大な数に上り、これらを新しい言語 +に書き換えるのは無理がある。新しい言語は古い言語との互換性が必須である。 + + +我々はこれらの問題に取り組むため、Continuation based Cという言語を提案 +している。Continuation based C（以下CbC）はCからサブルーチンやループ構造 +を除いたCの下位言語であり、ハードウェアの記述、また記述したプログラム +の検証などを目的としている。 + +これまでCbCのコンパイルにはmicro-cをベースとしたコンパイラとGNUコンパ +イラコレクション（以下gcc）をベースとしたコンパイラが用いられてきた。 +しかしgccにはバグや当初の期待ほど速度がでないという問題があり、また研 +究段階であるCbC言語自体にも仕様の変更などがあった。 + +%しかしgccは実用的なプログラムを動かすにはまだバグが多く、当初の期待ほ +%ど速度もでないという問題がある。また、研究段階であるCbC言語自体にも仕 +%様の変更などがあった。 + +本論文ではGCCベースのCbCコンパイラの問題の洗い出しとその問題の改善を行 +い、実用レベルのCbCプログラムの動作を目指す。また、CbCを用いたプログラ +ムの例として現在開発中のCbCベースTaskManager の紹介を行う。 +最後に実装したgccベースコンパイラの評価としてmicro-cベースコンパイラと +の速度比較を行い、 同じくTaskManager開発を通してのCbCによるプログラミ +ングの記述性についても評価・考察を行う。 + +%また、CbCを用いた応用例として現在開発中のCbCベース TaskManagerを紹介 +%し、 micro-cとの速度比較による評価を行う。さらにCbC の使用例として現 +%在開発中のCbCによる TaskManagerを紹介し、CbCによるプログラミングの記 +%述性についても論じる。 + + + + + + + +%我々はこれまで、様々な視点から軽量継続を用いた言語、Continuation based +%Cの有用性について研究してきた。このContinuation based C(以下CbC)はCか +%らサブルーチンやループ構造を除いたCの下位言語であり、ハードウェアとソ +%フトウェアの記述、また記述したプログラムの検証を目的として本研究室が提 +%案している言語である。 + +%\section{先行研究とCbC開発の動機} + +%\subsection{プログラムの検証} +%計算機科学の進歩により、ソフトウェアは大規模かつ複雑なものになっている。しかしそれに応じて、設計段階において誤りが生じる可能性も高くなってきており、設計されたシステムに誤りがないことを保証するための論理設計や検証手法及びデバッグ手法の確立が重要な課題となっている。 + +%どんなプログラムでも状態と状態遷移が存在し、その全てを網羅的に探索することでデッドロックなどの望ましくない状態を検出することができる。探索にはさまざまな手法が考えられるが、プログラムを直接状態遷移として記述できればこの探索に有利となる。 + +%本研究室の下地らはこの特徴を持つCbCを用いて線形時相論理による検証を提案し、その有用性を示した。\cite{bib:shimoji} + + +%\subsection{ゲームプログラミングにおけるデモンストレーション} +%我々は家庭用ゲーム機で動作するゲームプログラムのオープンな開発フレームワークに関する研究も行ってきた。 +%家庭用ゲーム機の多くは特殊なアーキテクチャをもち、そのためゲームプログラムには汎用性や冗長性が極めて小さく、移植が困難という問題がある。 + +%その問題の解決に、ゲームプログラム全体を小規模なプログラムの集合である``デモンストレーション''に分割するという手法を本研究室の金城らが提案した。\cite{bib:kinjo},\cite{bib:chiaki} + +%このデモンストレーション手法はプログラムを細かく分割するため、ゲーム機や組み込みなどの資源が制約された環境ではサブルーチンによるスタック操作がネックとなる。 +%そのためこの手法ではプログラム分割の実現にCbCを用いており、CからCbCへの機械的な変換方法について述べている。 + + +%\subsection{ハードウェア記述、ソフトウェアプログラミング} + +%\subsection{軽量継続を用いたプログラミング} +%以上の研究はそれぞれ軽量継続というCbC言語の特徴を利用して進められている。 + + +\section{論文構成} +%\ref{chp:cbc}にてContinuation based Cの要求仕様と詳細について説明する。 +%\ref{chp:impl}章ではgccへの実装方法を説明する。 + + +次章以降、本稿は\ref{chp:cbc}章にてCbCについて説明する。 +\ref{chp:impl}章にてgccへの実装について説明、 +\ref{chp:task}章ではCbCを用いたプログラムの実例としてTaskManagerを挙げ、 +\ref{chp:impl}章,\ref{chp:task}の評価を\ref{chp:eval}章で行う。 +最後に\ref{chp:concl}章をもってまとめとする。 + diff -r e9ecd5b5f29a -r aa09c34b90d3 master_paper.tex --- a/master_paper.tex Fri Jan 29 15:45:41 2010 +0900 +++ b/master_paper.tex Mon Feb 01 20:37:36 2010 +0900 @@ -5,10 +5,10 @@ \usepackage{listings, jlisting} \usepackage{multirow} \usepackage{slashbox} +\usepackage{color} \lstset{basicstyle=\footnotesize, frame=trbl, framesep=5pt} % dvipdfm を使って PDF ファイルに日本語の栞をつける -%\usepackage[dvipdfm]{color} \usepackage[dvipdfm,bookmarks=true, bookmarksnumbered=true, bookmarkstype=toc]{hyperref} @@ -19,15 +19,20 @@ % lstlistingsパッケージの設定 %\renewcommand{\lstlistingname}{リスト} +\lstdefinelanguage{cbc}[]{C} + {morekeywords={code,\_\_return}} \lstset{ - language=C,% - stringstyle=\ttfamily,% + language=cbc,% + %stringstyle=\ttfamily,% + stringstyle=,% basicstyle=\small\ttfamily,% - commentstyle=\itshape,% - classoffset=1,% + commentstyle=\itshape\rmfamily,% + %identifierstyle=\color{blue}\bfseries,% keywordstyle=\bfseries,% framesep=5pt,% showstringspaces=false,% + frameround=ftft,% + emphstyle=\underbar, %frame=tRBl, %numbers=left,stepnumber=1,numberstyle=\footnotesize% }% @@ -55,7 +60,7 @@ \end{minipage}} \markleftfoot{% 左下に挿入 \begin{minipage}{.8\textwidth} - Continuation based Cの高速化とその応用 + 組み込み向け言語Continuation based CのGCC上の実装 \end{minipage}} @@ -77,7 +82,7 @@ \listoftables %\pagenumbering{arabic} -\input{purposes.tex} +\input{introduction.tex} \input{cbc.tex} \input{implementation.tex} \input{taskmanager.tex} diff -r e9ecd5b5f29a -r aa09c34b90d3 memo.txt --- a/memo.txt Fri Jan 29 15:45:41 2010 +0900 +++ b/memo.txt Mon Feb 01 20:37:36 2010 +0900 @@ -181,5 +181,13 @@ +TODO: + o 用語の統一 + - gcc, GCC + - ppc, PowerPC + - mc, micro-c + - 末尾呼び出し最適化, tailcall + - 継続制御, 軽量継続 + diff -r e9ecd5b5f29a -r aa09c34b90d3 purposes.tex --- a/purposes.tex Fri Jan 29 15:45:41 2010 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,124 +0,0 @@ -\chapter{序論} -\label{chp:first} -\pagenumbering{arabic} - -%% 問題提起 -%% 解決案の提示 -%% 研究目標 -%% 本論文の各章の概要 - - -\section{背景と目的} - - -企業システムの多様化、IT導入の加速により、ソフトウェアは大規模化・複雑 -化する傾向にある。また家電製品のデジタル化も進み、組み込みシステムの需 -要も増大している。 - -それにともないハードウェアはムーアの法則よろしく驚異的な進歩を遂げ、近 -年はCPUのマルチコア化が進み、また新たな段階を築こうとしている。 - -ハードウェアの進歩に対し、ソフトウェアの開発に用いられる記述言語は、オ -ブジェクト指向プログラミングの発明・導入やデザインパターンに見られる技 -術の集約などが行われ、注目されてきた。 -%しかしながら90年代以降、言語その物に対する大きな変化は見られない。 -オブジェクト指向を主としたJavaはその有用性が認められ多くのシステム開発 -に取り入られている。 -しかしその反面、Cなどの低レベルな言語による記述に比べてこれらの技術は -余分な条件判断やメモリアクセスを増やしてしまう。そのため軽量かつ高速な -応答が要求される Real-time処理や組み込み用途には適さない。 - -またCellに見られるような複雑なアーキテクチャをもつマシンではプログラミ -ング自体も複雑になる。Cで記述されたプログラムからアーキテクチャに直接 -関わる命令 (DMAやシグナル)を使用するのでは、高級言語の設計思想と矛盾す -るともみられる。 - -大規模システムにおけるバグの存在も深刻な問題である。 -テストファーストな開発スタイルなどで工学的なアプローチからバグの抑制が -試みられているが、完全な排除は難しい。数学的なアプローチから無矛盾を証 -明する技術の研究も進んでいるが、現在のスタックベースのプログラミングは -状態数が膨大になり、実用化された例は少ない。しかしマルチコアの台頭によ -り並列プログラミングの必要性も高まっており、これからより検証の必要性が -増すと考えられる。 - -ハードウェアの進化、数学的検証にソフトウェアが対応するためにはこれまで -とは違う新たな視点を持ったプログラミング言語が望ましい。 -しかし既存のソフトウェアやシステムは膨大な数に上り、これらを新しい言語 -に書き換えるのは無理がある。新しい言語は古い言語との互換性が必須である。 - - -我々はこれらの問題に取り組むため、Continuation based Cという言語を提案 -している。Continuation based C(以下CbC)はCからサブルーチンやループ構造 -を除いたCの下位言語であり、ハードウェアの記述、また記述したプログラム -の検証などを目的としている。 - -これまでCbCのコンパイルにはmicro-cをベースとしたコンパイラとGNUコンパ -イラコレクション（以下gcc）をベースとしたコンパイラが用いられてきた。 -しかしgccにはバグや当初の期待ほど速度がでないという問題があり、また研 -究段階であるCbC言語自体にも仕様の変更などがあった。 - -%しかしgccは実用的なプログラムを動かすにはまだバグが多く、当初の期待ほ -%ど速度もでないという問題がある。また、研究段階であるCbC言語自体にも仕 -%様の変更などがあった。 - -本論文ではGCCベースのCbCコンパイラの問題の洗い出しとその問題の改善を行 -い、実用レベルのCbCプログラムの動作を目指す。また、CbCを用いたプログラ -ムの例として現在開発中のCbCベースTaskManager の紹介を行う。 -最後に実装したgccベースコンパイラの評価としてmicro-cベースコンパイラと -の速度比較を行い、 同じくTaskManager開発を通してのCbCによるプログラミ -ングの記述性についても評価・考察を行う。 - -%また、CbCを用いた応用例として現在開発中のCbCベース TaskManagerを紹介 -%し、 micro-cとの速度比較による評価を行う。さらにCbC の使用例として現 -%在開発中のCbCによる TaskManagerを紹介し、CbCによるプログラミングの記 -%述性についても論じる。 - - - - - - - -%我々はこれまで、様々な視点から軽量継続を用いた言語、Continuation based -%Cの有用性について研究してきた。このContinuation based C(以下CbC)はCか -%らサブルーチンやループ構造を除いたCの下位言語であり、ハードウェアとソ -%フトウェアの記述、また記述したプログラムの検証を目的として本研究室が提 -%案している言語である。 - -%\section{先行研究とCbC開発の動機} - -%\subsection{プログラムの検証} -%計算機科学の進歩により、ソフトウェアは大規模かつ複雑なものになっている。しかしそれに応じて、設計段階において誤りが生じる可能性も高くなってきており、設計されたシステムに誤りがないことを保証するための論理設計や検証手法及びデバッグ手法の確立が重要な課題となっている。 - -%どんなプログラムでも状態と状態遷移が存在し、その全てを網羅的に探索することでデッドロックなどの望ましくない状態を検出することができる。探索にはさまざまな手法が考えられるが、プログラムを直接状態遷移として記述できればこの探索に有利となる。 - -%本研究室の下地らはこの特徴を持つCbCを用いて線形時相論理による検証を提案し、その有用性を示した。\cite{bib:shimoji} - - -%\subsection{ゲームプログラミングにおけるデモンストレーション} -%我々は家庭用ゲーム機で動作するゲームプログラムのオープンな開発フレームワークに関する研究も行ってきた。 -%家庭用ゲーム機の多くは特殊なアーキテクチャをもち、そのためゲームプログラムには汎用性や冗長性が極めて小さく、移植が困難という問題がある。 - -%その問題の解決に、ゲームプログラム全体を小規模なプログラムの集合である``デモンストレーション''に分割するという手法を本研究室の金城らが提案した。\cite{bib:kinjo},\cite{bib:chiaki} - -%このデモンストレーション手法はプログラムを細かく分割するため、ゲーム機や組み込みなどの資源が制約された環境ではサブルーチンによるスタック操作がネックとなる。 -%そのためこの手法ではプログラム分割の実現にCbCを用いており、CからCbCへの機械的な変換方法について述べている。 - - -%\subsection{ハードウェア記述、ソフトウェアプログラミング} - -%\subsection{軽量継続を用いたプログラミング} -%以上の研究はそれぞれ軽量継続というCbC言語の特徴を利用して進められている。 - - -\section{論文構成} -%\ref{chp:cbc}にてContinuation based Cの要求仕様と詳細について説明する。 -%\ref{chp:impl}章ではgccへの実装方法を説明する。 - - -次章以降、本稿は\ref{chp:cbc}章にてCbCについて説明する。 -\ref{chp:impl}章にてgccへの実装について説明、 -\ref{chp:task}章ではCbCを用いたプログラムの実例としてTaskManagerを挙げ、 -\ref{chp:impl}章,\ref{chp:task}の評価を\ref{chp:eval}章で行う。 -最後に\ref{chp:concl}章をもってまとめとする。 - diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/Makefile Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,38 @@ + +CbCC=/usr/local/cbc/bin/cbc-gcc + +#CC=gcc +CC=/usr/local/cbc/bin/cbc-gcc + +HEADERMAKER=../../CbC-scripts/make_headers.py2 + +# fastcall版では-O0,-O2は動作確認、-O3以上はだめ +CFLAGS=-g -O2 -fomit-frame-pointer +#CFLAGS=-g -O2 +#CFLAGS=-g -O0 +#CFLAGS=-g -Os # an error occurred. + +.SUFFIXES: .cbc .o + +all: quicksort_cbc quicksort_c quicksort_cbc2 + +.cbc.o: + $(CbCC) $(CFLAGS) -c -o $@ $< +.cbc.h: + $(HEADERMAKER) $^ > $@ + +quicksort_cbc.o: quicksort_cbc.h +quicksort_cbc2.o: quicksort_cbc2.h +quicksort_test.o: quicksort_test.h + +quicksort_cbc: quicksort_cbc.o quicksort_test.o quicksort_cbc_inter.o + $(CC) $(CFLAGS) -o $@ $^ +quicksort_cbc2: quicksort_cbc2.o quicksort_test.o + $(CC) $(CFLAGS) -o $@ $^ + +quicksort_c: quicksort_c.o + $(CC) $(CFLAGS) -o $@ $^ + + +clean: + rm -rf *.o *.s quicksort_c quicksort_cbc quicksort_cbc2 diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/README --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/README Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,7 @@ + +micro-cがppc/linuxにおいてバグがあるため +それ専用に作り直したベンチマーク + +オリジナルは~one/hg/CbC/GCC/CbC-exmamples/quicksort + + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/benchmark.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/benchmark.sh Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,44 @@ +#!/usr/bin/env zsh + +time=/usr/bin/time +QS=./quicksort_c +size=10000000 +seed=123456789 +num=10 + + +max=0 +min=99999 +count=0 +amount=0 + +echo "size of array = $size" +while [[ $count -lt $num ]]; do + usertime=$( $time -p $QS -n $size -s $seed 2>&1 >& - |grep '^user'|tr -s " "|cut -f2 -d" ") + #usertime=$(printf "%d" $usertime) + echo $usertime + + amount=$(($usertime+$amount)) + if [[ $usertime -lt $min ]]; then + min=$usertime + fi + if [[ $usertime -gt $max ]]; then + max=$usertime + fi + #seed=$seed[1,-2] + seed=$(($seed+10)) + count=$(($count+1)) +done + +echo "amount time = $amount" +echo "maxtime = $max" +echo "mintime = $min" + +amount=$(($amount - $max - $min)) +echo "amount time - mintime - maxtime = $amount" +count=$(($count-2)) +echo "count = $count" +averagetime=$(($amount/($count))) +echo "average time = $averagetime" + + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/Makefile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/Makefile Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,39 @@ + +CbCC=~/WorkSpace/Mercurial/device/mc + +#CC=gcc +CC=gcc + +HEADERMAKER=~/WorkSpace/Mercurial/GCC/CbC-scripts/make_headers.py2 + +CFLAGS=-g -Wall + +.SUFFIXES: .cbc .o .s .c + +all: quicksort_cbc quicksort_c quicksort_cbc2 + +quicksort_c.c quicksort_cbc.cbc quicksort_cbc2.cbc quicksort_test.cbc benchmark.sh: + ln -s ../$@ + +.s.o: + $(CC) -c -o $@ $< +.cbc.s: + $(CbCC) $< +.cbc.h: + $(HEADERMAKER) $^ > $@ + +quicksort_cbc.o: quicksort_cbc.h +quicksort_cbc2.o: quicksort_cbc2.h +quicksort_test.o: quicksort_test.h + +quicksort_cbc: quicksort_cbc.o quicksort_test.o quicksort_cbc_inter.o + $(CC) $(CFLAGS) -o $@ $^ +quicksort_cbc2: quicksort_cbc2.o quicksort_test.o + $(CC) $(CFLAGS) -o $@ $^ + +quicksort_c: quicksort_c.o + $(CC) $(CFLAGS) -o $@ $^ + + +clean: + rm -rf *.o *.s quicksort_c quicksort_cbc quicksort_cbc2 diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/benchmark.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/benchmark.sh Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,44 @@ +#!/usr/bin/env zsh + +time=/usr/bin/time +QS=./quicksort_cbc +size=10000000 +seed=123456789 +num=10 + + +max=0 +min=99999 +count=0 +amount=0 + +echo "size of array = $size" +while [[ $count -lt $num ]]; do + usertime=$( $time -p $QS -n $size -s $seed 2>&1 >& - |grep '^user'|tr -s " "|cut -f2 -d" ") + #usertime=$(printf "%d" $usertime) + echo $usertime + + amount=$(($usertime+$amount)) + if [[ $usertime -lt $min ]]; then + min=$usertime + fi + if [[ $usertime -gt $max ]]; then + max=$usertime + fi + #seed=$seed[1,-2] + seed=$(($seed+10)) + count=$(($count+1)) +done + +echo "amount time = $amount" +echo "maxtime = $max" +echo "mintime = $min" + +amount=$(($amount - $max - $min)) +echo "amount time - mintime - maxtime = $amount" +count=$(($count-2)) +echo "count = $count" +averagetime=$(($amount/($count))) +echo "average time = $averagetime" + + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_c.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_c.c Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,183 @@ +#include +#include +#include +#include + +static inline void +SWAP (int *a, int *b) +{ + int tmp; + tmp = *a; + *a = *b; + *b = tmp; +} + +static inline int +mid_point(int a, int b, int c) +{ + if (a < b) { + if (b < c) + return b; + else if (a < c) + return c; + else + return a; + } else { + if (a < c) + return a; + else if (b < c) + return c; + else + return b; + } +} + +void +selectsort(int *v, int s0, int e0) +{ + int i,j; + int m; + int size = e0-s0+1; + v += s0; + for (i=0; i v[j]) + m = j; + } + if (m!=i) + SWAP(&v[i],&v[m]); + } + return; +} + +void +quicksort(int *v, int s0, int e0) +{ + int p; + int s=s0, e=e0; +#if 0 + if (e<=s) return; + if (e-s<5) { + selectsort(v,s0,e0); + return; + } +#else + if (e<=s) return; +#endif + + //p = (v[s]+v[(s+e)/2]+v[e])/3; + p = mid_point(v[s],v[e],v[(s+e)/2]); + + while (1) { + while (v[s] v[i+1]) + return 0; + } + return 1; +} + +void +random_initialize(int *v, int size, int min, int max) +{ + int i; + int diff = max-min+1; + + for (i=0; i +#include +#include + +typedef void *stack; +typedef struct { + int size; + void *interface; + __code (*ret)(void*, stack) ; +} frame, *framep; + +/* quickstart main routine. */ +typedef struct { + int *v; + int s; + int e; +} QS_IF ; +typedef __code (*RET)(void*); + +#include"quicksort_cbc.h" + +/* for check. */ +void *mustbefreed; + +__code returner(stack sp) +{ + framep fp = (framep)sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +__code quicksort_start(void *arg, stack sp) +{ + QS_IF *recvif = arg; + int a,b,c,p; + a = recvif->v[recvif->s]; + b = recvif->v[recvif->e]; + c = recvif->v[(recvif->s+recvif->e)/2]; + + //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e); + if (recvif->e <= recvif->s) goto returner(sp); + + if (a < b) { + if (b < c) + p = b; + else if (a < c) + p = c; + else + p = a; + } else { + if (a < c) + p = a; + else if (b < c) + p = c; + else + p = b; + } + + goto quicksort_divider (recvif, recvif->s, recvif->e, p, sp); +} +/* main routine end. */ + +/* divide routine. */ +__code quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp) +{ + goto quicksort_divider_s(recvif, s, e, p, sp); +} +__code quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp) +{ + if (recvif->v[s]v[e]) { + e--; + goto quicksort_divider_e(recvif, s, e, p, sp); + } else + goto quicksort_swapper(recvif, s, e, p, sp); +} +__code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp) +{ + if (sv[s]; + recvif->v[s] = recvif->v[e]; + recvif->v[e] = tmp; + goto quicksort_divider(recvif, s+1, e-1, p, sp); + } else { + goto quicksort_treecall(recvif, s, e, sp); + } +} +/* divide routin end. */ + + +/* recursive call routine. */ +__code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp) +{ + framep fp; + QS_IF *outif; + + /* interface for first quicksort_start this segment directly jump to. */ + outif = (sp-=sizeof(QS_IF)); + outif->v = recvif->v; + outif->s = recvif->s; + outif->e = e; + fp = (sp-=sizeof(frame)); + fp->ret = quicksort_start; + fp->interface = recvif; + fp->size = sizeof(frame)+sizeof(QS_IF); + + /* recvif is used by second quicksort_start. */ + recvif->s = e+1; + goto quicksort_start(outif, sp); +} +/* recursive call routine end. */ + +#define STACK_SIZE 10240 + +typedef struct { + __code (*ret)(void*); + void *ret_arg; + stack *sp; +} QS_FINISH; +__code +quicksort(int *v, int s, int e, RET ret, void *arg ) +{ + framep fp; + stack sp0, sp; + sp0 = mustbefreed = malloc(STACK_SIZE); + sp = sp0 + STACK_SIZE; + QS_FINISH *finish_if; + QS_IF *outif; + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(QS_FINISH)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + outif = (sp -= sizeof(QS_IF)); + outif->v = v; + outif->s = s; + outif->e = e; + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish; + fp->interface = finish_if; + fp->size = sizeof(frame)+sizeof(QS_IF); + + goto quicksort_start(outif, sp); +} +__code +quicksort_finish(void *arg, stack sp) +{ + QS_FINISH interface; + interface = *(QS_FINISH*)arg; + //assert((void*)interface.sp==(void*)mustbefreed); + free(interface.sp); + goto interface.ret(interface.ret_arg); +} + + + +#if 0 +void +quicksort_c(int *v, int s0, int e0, stack sp) +{ + int p; + int s=s0, e=e0; + if (e<=s) return; + + //p = (v[s]+v[(s+e)/2]+v[e])/3; + p = mid_point(v[s],v[e],v[(s+e)/2]); + + while (1) { + while (v[s]ret = caller_finish; + fp->interface = NULL; + fp->size = sizeof(*outif)+sizeof(frame); + + goto quicksort_start(outif, sp); +} +__code caller_finish0(void *arg, stack sp) +{ +} + +__code __returner0(void *arg , stack sp) +{ + framep fp = sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +#endif + + + + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_cbc.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_cbc.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,26 @@ +/* defined in file quicksort_cbc.cbc at offset 354 */ +__code returner (stack sp); + +/* defined in file quicksort_cbc.cbc at offset 462 */ +__code quicksort_start (void *arg, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1031 */ +__code quicksort_divider (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1155 */ +__code quicksort_divider_s (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1364 */ +__code quicksort_divider_e (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1576 */ +__code quicksort_swapper (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1916 */ +__code quicksort_treecall (QS_IF *recvif, int s, int e, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 2547 */ +__code quicksort (int *v, int s, int e, RET ret, void *arg ); + +/* defined in file quicksort_cbc.cbc at offset 3213 */ +__code quicksort_finish (void *arg, stack sp); diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_cbc2.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_cbc2.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,159 @@ +#include +#include +#include + +typedef struct { + int *v; + int s; + int e; +} QS_IF; + +typedef void *stack; +typedef __code (*RET)(QS_IF, stack); +typedef struct { + int size; + QS_IF interface; + RET ret; +} frame, *framep; + +typedef __code (*RETTYPE)(void*); +typedef struct { + RETTYPE ret; + void *ret_arg; + stack *sp; +} QS_FINISH; +#define STACK_SIZE 10240 + +#include"quicksort_cbc2.h" + +__code returner(stack sp) +{ + framep fp = (framep)sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +__code quicksort_start(QS_IF recvif, stack sp) +{ + int a,b,c,p; + a = recvif.v[recvif.s]; + b = recvif.v[recvif.e]; + c = recvif.v[(recvif.s+recvif.e)/2]; + + //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e); + if (recvif.e <= recvif.s) goto returner(sp); + + if (a < b) { + if (b < c) + p = b; + else if (a < c) + p = c; + else + p = a; + } else { + if (a < c) + p = a; + else if (b < c) + p = c; + else + p = b; + } + + goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp); +} +/* main routine end. */ + +/* divide routine. */ +__code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp) +{ + goto quicksort_divider_s(recvif, s, e, p, sp); +} +__code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp) +{ + if (recvif.v[s]ret = quicksort_start; + fp->size = sizeof(frame); + fp->interface.v = recvif.v; + fp->interface.s = e+1; + fp->interface.e = recvif.e; + + /* recvif is used by second quicksort_start. */ + recvif.e = e; + goto quicksort_start(recvif, sp); +} +/* recursive call routine end. */ + +__code +quicksort(int *v, int s, int e, RETTYPE ret, void *arg ) +{ + framep fp; + stack sp0, sp; + sp0 = malloc(STACK_SIZE); + printf("allocate a stack %p\n", sp0); + sp = sp0 + STACK_SIZE; + QS_FINISH *finish_if; + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(*finish_if)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish; + fp->size = sizeof(frame); + fp->interface.v = v; + fp->interface.s = s; + fp->interface.e = e; + + goto quicksort_start(fp->interface, sp); +} +__code +quicksort_finish(QS_IF recvif, stack sp) +{ + QS_FINISH *interface = (QS_FINISH*)sp; + free(interface->sp); + printf("free the stack %p\n", interface->sp); + goto interface->ret(interface->ret_arg); +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_cbc2.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_cbc2.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,27 @@ +/* defined in file quicksort_cbc2.cbc at offset 402 */ +__code returner (stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 509 */ +__code quicksort_start (QS_IF recvif, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1047 */ +__code quicksort_divider (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1169 */ +__code quicksort_divider_s (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1380 */ +__code quicksort_divider_e (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1589 */ +__code quicksort_swapper (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1961 */ +__code quicksort_treecall (QS_IF recvif, int s, int e, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 2417 */ +__code quicksort (int *v, int s, int e, RETTYPE ret, void *arg ); + +/* defined in file quicksort_cbc2.cbc at offset 3052 */ +__code quicksort_finish (QS_IF recvif, stack sp); + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_cbc_inter.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_cbc_inter.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,102 @@ + +#include +typedef void *stack; +typedef struct { + int size; + void *interface; + __code (*ret)(void*, stack) ; +} frame, *framep; + +/* quickstart main routine. */ +typedef struct { + int *v; + int s; + int e; +} QS_IF ; +typedef __code (*RET)(void*); + +#include"quicksort_cbc.h" + + +typedef struct { + __code (*ret)(void*); + void *ret_arg; + stack *sp; +} QS_FINISH; + +extern int *IFv; +extern int IFs; +extern int IFe; +extern RET IFret; +extern void *IFarg; +extern stack IFsp; +extern int IFsize; + +static void(*exitfunc)(void*); +__code exitter(void *arg) { + exitfunc(arg); +} + +__code quicksort_finish_IF(void *arg, stack sp); + +void +quicksort_IF() +{ + printf("v=%p\n", IFv); + printf("s=%d\n", IFs); + printf("e=%d\n", IFe); + printf("ret=%p\n", IFret); + printf("arg=%p\n", IFarg); + printf("sp=%p\n", IFsp); + printf("size=%d\n", IFsize); + exitfunc = IFret; + + goto quicksort_IF0(IFv, IFs, IFe, exitter, IFarg, IFsp, IFsize); +} + +__code +quicksort_IF0(int *v, int s, int e, RET ret, void *arg, stack sp0,int size) +{ + framep fp; + stack sp; + sp = sp0 + size; + QS_FINISH *finish_if; + QS_IF *outif; + + printf("v=%p\n", v); + printf("s=%d\n", s); + printf("e=%d\n", e); + printf("ret=%p\n", ret); + printf("arg=%p\n", arg); + printf("sp=%p\n", sp0); + printf("size=%d\n", size); + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(QS_FINISH)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + outif = (sp -= sizeof(QS_IF)); + outif->v = v; + outif->s = s; + outif->e = e; + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish_IF; + fp->interface = finish_if; + fp->size = sizeof(frame)+sizeof(QS_IF); + + goto quicksort_start(outif, sp); +} + +__code +quicksort_finish_IF(void *arg, stack sp) +{ + QS_FINISH interface; + interface = *(QS_FINISH*)arg; + //assert((void*)interface.sp==(void*)mustbefreed); + goto interface.ret(interface.ret_arg); +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_test.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_test.c Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,129 @@ +#include +#include +#include +#include + +#include"quicksort_test.h" + +#define STACK_SIZE 10240 + +extern void quicksort_IF(); + + +void +random_initialize(int *v, int size, int min, int max) +{ + int i; + int diff = max-min+1; + + for (i=0; i v[i+1]) + return 0; + } + return 1; +} + +void +exit0(void *arg) +{ + int b; + //print_array(arg, size); + b = check_sort(arg, size); + if (b) { + printf("sorting successful!\n"); + exit(EXIT_SUCCESS); + } else { + printf("sorting failure! \n"); + exit(EXIT_FAILURE); + } +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_test.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_test.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,129 @@ +#include +#include +#include +#include + +#include"quicksort_test.h" + +#define STACK_SIZE 10240 + +extern void quicksort_IF(); + + +void +random_initialize(int *v, int size, int min, int max) +{ + int i; + int diff = max-min+1; + + for (i=0; i v[i+1]) + return 0; + } + return 1; +} + +void +exit0(void *arg) +{ + int b; + //print_array(arg, size); + b = check_sort(arg, size); + if (b) { + printf("sorting successful!\n"); + exit(EXIT_SUCCESS); + } else { + printf("sorting failure! \n"); + exit(EXIT_FAILURE); + } +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/mc/quicksort_test.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/mc/quicksort_test.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,18 @@ +/* defined in file quicksort_test.cbc at offset 160 */ +void random_initialize (int *v, int size, int min, int max); + +/* defined in file quicksort_test.cbc at offset 322 */ +static void print_array (int *v, int size); + +/* defined in file quicksort_test.cbc at offset 564 */ +void starter (int size); + +/* defined in file quicksort_test.cbc at offset 1095 */ +int main (int argc, char **argv); + +/* defined in file quicksort_test.cbc at offset 1491 */ +static int check_sort (int *v, int size); + +/* defined in file quicksort_test.cbc at offset 1620 */ +void exit0 (void *arg); + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_c.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_c.c Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,183 @@ +#include +#include +#include +#include + +static inline void +SWAP (int *a, int *b) +{ + int tmp; + tmp = *a; + *a = *b; + *b = tmp; +} + +static inline int +mid_point(int a, int b, int c) +{ + if (a < b) { + if (b < c) + return b; + else if (a < c) + return c; + else + return a; + } else { + if (a < c) + return a; + else if (b < c) + return c; + else + return b; + } +} + +void +selectsort(int *v, int s0, int e0) +{ + int i,j; + int m; + int size = e0-s0+1; + v += s0; + for (i=0; i v[j]) + m = j; + } + if (m!=i) + SWAP(&v[i],&v[m]); + } + return; +} + +void +quicksort(int *v, int s0, int e0) +{ + int p; + int s=s0, e=e0; +#if 0 + if (e<=s) return; + if (e-s<5) { + selectsort(v,s0,e0); + return; + } +#else + if (e<=s) return; +#endif + + //p = (v[s]+v[(s+e)/2]+v[e])/3; + p = mid_point(v[s],v[e],v[(s+e)/2]); + + while (1) { + while (v[s] v[i+1]) + return 0; + } + return 1; +} + +void +random_initialize(int *v, int size, int min, int max) +{ + int i; + int diff = max-min+1; + + for (i=0; i +#include +#include + +typedef void *stack; +typedef struct { + int size; + void *interface; + __code (*ret)(void*, stack) ; +} frame, *framep; + +/* quickstart main routine. */ +typedef struct { + int *v; + int s; + int e; +} QS_IF ; +typedef __code (*RET)(void*); + +#include"quicksort_cbc.h" + +/* for check. */ +void *mustbefreed; + +__code returner(stack sp) +{ + framep fp = (framep)sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +__code quicksort_start(void *arg, stack sp) +{ + QS_IF *recvif = arg; + int a,b,c,p; + a = recvif->v[recvif->s]; + b = recvif->v[recvif->e]; + c = recvif->v[(recvif->s+recvif->e)/2]; + + //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e); + if (recvif->e <= recvif->s) goto returner(sp); + + if (a < b) { + if (b < c) + p = b; + else if (a < c) + p = c; + else + p = a; + } else { + if (a < c) + p = a; + else if (b < c) + p = c; + else + p = b; + } + + goto quicksort_divider (recvif, recvif->s, recvif->e, p, sp); +} +/* main routine end. */ + +/* divide routine. */ +__code quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp) +{ + goto quicksort_divider_s(recvif, s, e, p, sp); +} +__code quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp) +{ + if (recvif->v[s]v[e]) { + e--; + goto quicksort_divider_e(recvif, s, e, p, sp); + } else + goto quicksort_swapper(recvif, s, e, p, sp); +} +__code quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp) +{ + if (sv[s]; + recvif->v[s] = recvif->v[e]; + recvif->v[e] = tmp; + goto quicksort_divider(recvif, s+1, e-1, p, sp); + } else { + goto quicksort_treecall(recvif, s, e, sp); + } +} +/* divide routin end. */ + + +/* recursive call routine. */ +__code quicksort_treecall(QS_IF *recvif, int s, int e, stack sp) +{ + framep fp; + QS_IF *outif; + + /* interface for first quicksort_start this segment directly jump to. */ + outif = (sp-=sizeof(QS_IF)); + outif->v = recvif->v; + outif->s = recvif->s; + outif->e = e; + fp = (sp-=sizeof(frame)); + fp->ret = quicksort_start; + fp->interface = recvif; + fp->size = sizeof(frame)+sizeof(QS_IF); + + /* recvif is used by second quicksort_start. */ + recvif->s = e+1; + goto quicksort_start(outif, sp); +} +/* recursive call routine end. */ + +#define STACK_SIZE 10240 + +typedef struct { + __code (*ret)(void*); + void *ret_arg; + stack *sp; +} QS_FINISH; +__code +quicksort(int *v, int s, int e, RET ret, void *arg ) +{ + framep fp; + stack sp0, sp; + sp0 = mustbefreed = malloc(STACK_SIZE); + sp = sp0 + STACK_SIZE; + QS_FINISH *finish_if; + QS_IF *outif; + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(QS_FINISH)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + outif = (sp -= sizeof(QS_IF)); + outif->v = v; + outif->s = s; + outif->e = e; + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish; + fp->interface = finish_if; + fp->size = sizeof(frame)+sizeof(QS_IF); + + goto quicksort_start(outif, sp); +} +__code +quicksort_finish(void *arg, stack sp) +{ + QS_FINISH interface; + interface = *(QS_FINISH*)arg; + //assert((void*)interface.sp==(void*)mustbefreed); + free(interface.sp); + goto interface.ret(interface.ret_arg); +} + + + +#if 0 +void +quicksort_c(int *v, int s0, int e0, stack sp) +{ + int p; + int s=s0, e=e0; + if (e<=s) return; + + //p = (v[s]+v[(s+e)/2]+v[e])/3; + p = mid_point(v[s],v[e],v[(s+e)/2]); + + while (1) { + while (v[s]ret = caller_finish; + fp->interface = NULL; + fp->size = sizeof(*outif)+sizeof(frame); + + goto quicksort_start(outif, sp); +} +__code caller_finish0(void *arg, stack sp) +{ +} + +__code __returner0(void *arg , stack sp) +{ + framep fp = sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +#endif + + + + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_cbc.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_cbc.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,26 @@ +/* defined in file quicksort_cbc.cbc at offset 354 */ +__code returner (stack sp); + +/* defined in file quicksort_cbc.cbc at offset 462 */ +__code quicksort_start (void *arg, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1031 */ +__code quicksort_divider (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1155 */ +__code quicksort_divider_s (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1364 */ +__code quicksort_divider_e (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1576 */ +__code quicksort_swapper (QS_IF *recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 1916 */ +__code quicksort_treecall (QS_IF *recvif, int s, int e, stack sp); + +/* defined in file quicksort_cbc.cbc at offset 2547 */ +__code quicksort (int *v, int s, int e, RET ret, void *arg ); + +/* defined in file quicksort_cbc.cbc at offset 3213 */ +__code quicksort_finish (void *arg, stack sp); diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_cbc2.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_cbc2.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,159 @@ +#include +#include +#include + +typedef struct { + int *v; + int s; + int e; +} QS_IF; + +typedef void *stack; +typedef __code (*RET)(QS_IF, stack); +typedef struct { + int size; + QS_IF interface; + RET ret; +} frame, *framep; + +typedef __code (*RETTYPE)(void*); +typedef struct { + RETTYPE ret; + void *ret_arg; + stack *sp; +} QS_FINISH; +#define STACK_SIZE 10240 + +#include"quicksort_cbc2.h" + +__code returner(stack sp) +{ + framep fp = (framep)sp; + sp += fp->size; + goto fp->ret(fp->interface, sp); +} + +__code quicksort_start(QS_IF recvif, stack sp) +{ + int a,b,c,p; + a = recvif.v[recvif.s]; + b = recvif.v[recvif.e]; + c = recvif.v[(recvif.s+recvif.e)/2]; + + //printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e); + if (recvif.e <= recvif.s) goto returner(sp); + + if (a < b) { + if (b < c) + p = b; + else if (a < c) + p = c; + else + p = a; + } else { + if (a < c) + p = a; + else if (b < c) + p = c; + else + p = b; + } + + goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp); +} +/* main routine end. */ + +/* divide routine. */ +__code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp) +{ + goto quicksort_divider_s(recvif, s, e, p, sp); +} +__code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp) +{ + if (recvif.v[s]ret = quicksort_start; + fp->size = sizeof(frame); + fp->interface.v = recvif.v; + fp->interface.s = e+1; + fp->interface.e = recvif.e; + + /* recvif is used by second quicksort_start. */ + recvif.e = e; + goto quicksort_start(recvif, sp); +} +/* recursive call routine end. */ + +__code +quicksort(int *v, int s, int e, RETTYPE ret, void *arg ) +{ + framep fp; + stack sp0, sp; + sp0 = malloc(STACK_SIZE); + printf("allocate a stack %p\n", sp0); + sp = sp0 + STACK_SIZE; + QS_FINISH *finish_if; + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(*finish_if)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish; + fp->size = sizeof(frame); + fp->interface.v = v; + fp->interface.s = s; + fp->interface.e = e; + + goto quicksort_start(fp->interface, sp); +} +__code +quicksort_finish(QS_IF recvif, stack sp) +{ + QS_FINISH *interface = (QS_FINISH*)sp; + free(interface->sp); + printf("free the stack %p\n", interface->sp); + goto interface->ret(interface->ret_arg); +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_cbc2.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_cbc2.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,27 @@ +/* defined in file quicksort_cbc2.cbc at offset 402 */ +__code returner (stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 509 */ +__code quicksort_start (QS_IF recvif, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1047 */ +__code quicksort_divider (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1169 */ +__code quicksort_divider_s (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1380 */ +__code quicksort_divider_e (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1589 */ +__code quicksort_swapper (QS_IF recvif, int s, int e, int p, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 1961 */ +__code quicksort_treecall (QS_IF recvif, int s, int e, stack sp); + +/* defined in file quicksort_cbc2.cbc at offset 2417 */ +__code quicksort (int *v, int s, int e, RETTYPE ret, void *arg ); + +/* defined in file quicksort_cbc2.cbc at offset 3052 */ +__code quicksort_finish (QS_IF recvif, stack sp); + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_cbc_inter.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_cbc_inter.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,102 @@ + +#include +typedef void *stack; +typedef struct { + int size; + void *interface; + __code (*ret)(void*, stack) ; +} frame, *framep; + +/* quickstart main routine. */ +typedef struct { + int *v; + int s; + int e; +} QS_IF ; +typedef __code (*RET)(void*); + +#include"quicksort_cbc.h" + + +typedef struct { + __code (*ret)(void*); + void *ret_arg; + stack *sp; +} QS_FINISH; + +extern int *IFv; +extern int IFs; +extern int IFe; +extern RET IFret; +extern void *IFarg; +extern stack IFsp; +extern int IFsize; + +static void(*exitfunc)(void*); +__code exitter(void *arg) { + exitfunc(arg); +} + +__code quicksort_finish_IF(void *arg, stack sp); + +void +quicksort_IF() +{ + printf("v=%p\n", IFv); + printf("s=%d\n", IFs); + printf("e=%d\n", IFe); + printf("ret=%p\n", IFret); + printf("arg=%p\n", IFarg); + printf("sp=%p\n", IFsp); + printf("size=%d\n", IFsize); + exitfunc = IFret; + + goto quicksort_IF0(IFv, IFs, IFe, exitter, IFarg, IFsp, IFsize); +} + +__code +quicksort_IF0(int *v, int s, int e, RET ret, void *arg, stack sp0,int size) +{ + framep fp; + stack sp; + sp = sp0 + size; + QS_FINISH *finish_if; + QS_IF *outif; + + printf("v=%p\n", v); + printf("s=%d\n", s); + printf("e=%d\n", e); + printf("ret=%p\n", ret); + printf("arg=%p\n", arg); + printf("sp=%p\n", sp0); + printf("size=%d\n", size); + + /* interface for quicksort_finish. */ + finish_if = (sp -= sizeof(QS_FINISH)); + finish_if->ret = ret; + finish_if->ret_arg = arg; + finish_if->sp = sp0; + + /* interface for quicksort_start. */ + outif = (sp -= sizeof(QS_IF)); + outif->v = v; + outif->s = s; + outif->e = e; + /* frame for quicksort_finish. */ + fp = (sp -= sizeof(frame)); + fp->ret = quicksort_finish_IF; + fp->interface = finish_if; + fp->size = sizeof(frame)+sizeof(QS_IF); + + goto quicksort_start(outif, sp); +} + +__code +quicksort_finish_IF(void *arg, stack sp) +{ + QS_FINISH interface; + interface = *(QS_FINISH*)arg; + //assert((void*)interface.sp==(void*)mustbefreed); + goto interface.ret(interface.ret_arg); +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_test.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_test.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,129 @@ +#include +#include +#include +#include + +#include"quicksort_test.h" + +#define STACK_SIZE 10240 + +extern void quicksort_IF(); + + +void +random_initialize(int *v, int size, int min, int max) +{ + int i; + int diff = max-min+1; + + for (i=0; i v[i+1]) + return 0; + } + return 1; +} + +void +exit0(void *arg) +{ + int b; + //print_array(arg, size); + b = check_sort(arg, size); + if (b) { + printf("sorting successful!\n"); + exit(EXIT_SUCCESS); + } else { + printf("sorting failure! \n"); + exit(EXIT_FAILURE); + } +} + diff -r e9ecd5b5f29a -r aa09c34b90d3 quicksort_for_ppc/quicksort_test.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/quicksort_for_ppc/quicksort_test.h Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,18 @@ +/* defined in file quicksort_test.cbc at offset 160 */ +void random_initialize (int *v, int size, int min, int max); + +/* defined in file quicksort_test.cbc at offset 322 */ +static void print_array (int *v, int size); + +/* defined in file quicksort_test.cbc at offset 564 */ +void starter (int size); + +/* defined in file quicksort_test.cbc at offset 1095 */ +int main (int argc, char **argv); + +/* defined in file quicksort_test.cbc at offset 1491 */ +static int check_sort (int *v, int size); + +/* defined in file quicksort_test.cbc at offset 1620 */ +void exit0 (void *arg); + diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/build-code-segment.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/build-code-segment.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,6 @@ +if (is_code_segment) + t1 = build_code_segment_type (valtype, TYPE_ARG_TYPES (t2)); +else + t1 = build_function_type (valtype, TYPE_ARG_TYPES (t2)); +t1 = build_type_attribute_variant (t1, attributes); +return qualify_type (t1, t2); diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/c_parser_postfix_expression.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/c_parser_postfix_expression.c Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,26 @@ +case RID_CbC_RET: + + stmt = c_begin_stmt_expr (); + + /* create label declaration. */ + label = get_identifier ("_cbc_exit0"); + tlab = declare_label (label); + add_stmt (build_stmt (DECL_EXPR, tlab)); + + /* declare retval. (int retval;) */ + tree decl_cond = + build_decl(VAR_DECL,get_identifier ("retval"), + TREE_TYPE(current_function_decl)); + pushdecl (decl_cond); + + /* define nested function. */ + decl = cbc_define_nested_code(label, decl_cond); + + /* define if-ed goto label and return statement. */ + cbc_define_if_closed_goto (label, decl_cond); + + /* get pointer to nested function. */ + value = build_addr (decl , current_function_decl); + add_stmt (value); + + expr.value = c_finish_stmt_expr (stmt); diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/cbcreturn.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/cbcreturn.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,23 @@ +__code cs(RET_FUNC ret) +{ + goto ret(2); +} + +int funcB() +{ + /* do something. */ + goto cs(__return); + + /* never reached. */ + return -1; +} + +void funcA() +{ + int t; + + t = funcB(); + + printf("t=%d\n", t); + /* t should not be -1 but 2. */ +} diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/goto-expression.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/goto-expression.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,8 @@ +code somesegment( ... ) { + if (.. ) { + /* */ + goto nextsegment( ... ); + } else { + goto nextsegment( ... ); + } +} diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/md-example.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/md-example.md Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,22 @@ + +(define_insn "*sibcall_indirect_nonlocal_sysv" + [(call (mem:SI (match_operand:P 0 "register_operand" "c,*l,c,*l")) + (match_operand 1 "" "g,g,g,g")) + (use (match_operand:SI 2 "immediate_operand" "O,O,n,n")) + (use (reg:SI LR_REGNO)) + (return)] + "DEFAULT_ABI == ABI_V4 + || DEFAULT_ABI == ABI_DARWIN" +{ + /* + if (INTVAL (operands[2]) & CALL_V4_SET_FP_ARGS) + output_asm_insn ("crxor 6,6,6", operands); + + else if (INTVAL (operands[2]) & CALL_V4_CLEAR_FP_ARGS) + output_asm_insn ("creqv 6,6,6", operands); + */ + + return "b%T0"; +} + [(set_attr "type" "jmpreg,jmpreg,jmpreg,jmpreg") + (set_attr "length" "4,4,8,8")]) diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/nestedcode.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/nestedcode.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,23 @@ +int funcB() +{ + /* do something. */ + + int __retval; + code __unnamed_code(int __retval0){ + __retval = __retval0; + goto __unnamed_label; + } + if (0) { + __unnamed_label: + return __retval; + } + __return = __unnamed_code; + + goto cs(__return); + + /* never reached. */ + return -1; +} + + + diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/ret-call.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/ret-call.cbc Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,10 @@ +code somesegment( ... ) { + if (.. ) { + /* */ + nextsegment( ... ); + return ; + } else { + nextsegment( ... ); + return ; + } +} diff -r e9ecd5b5f29a -r aa09c34b90d3 sources/rtl-example.rtl --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/rtl-example.rtl Mon Feb 01 20:37:36 2010 +0900 @@ -0,0 +1,13 @@ +(call_insn/j 25 24 0 (parallel [ + (call (mem:SI (reg/f:SI 129) [0 S4 A8]) + (const_int 256 [0x100])) + (use (const_int 0 [0x0])) + (use (reg:SI 130)) + (return) + ]) -1 (nil) + (nil) + (expr_list:REG_DEP_TRUE (use (reg:SI 6 r6)) + (expr_list:REG_DEP_TRUE (use (reg:SI 5 r5)) + (expr_list:REG_DEP_TRUE (use (reg:SI 4 r4)) + (expr_list:REG_DEP_TRUE (use (reg:SI 3 r3)) + (nil))))))