有限状態機械（FSM）とシンボリック状態探索を利用したコード生成手法

情報処理学会 Web Site 被引用文献5件 参考文献26件

書誌事項

タイトル別名
  • ユウゲン ジョウタイ キカイ FSM ト シンボリック ジョウタイ タンサク オ リヨウ シタ コード セイセイ シュホウ
  • Code Generation Using FSM and Symbolic State Traversal
  • 論理合成

この論文をさがす

抄録

高速処理が必要な組み込みシステム向けLSIとして，並列命令や特殊なデータパスユニット，レジスタ構成あるいはバス構成を持つ，アプリケーションに特化したプロセッサが数多く組み込み向け市場に出現している5）?10）．しかし従来のコンパイラ技術1）だけでは，このような特殊なプロセッサの性能を十分引き出すコードを生成できない．この問題を解決する1つの方法として論文2）、3）ではまず，コード生成対象のデータフローグラフ（DFG）と，対象とするアーキテクチャの命令セットから有限状態機械（FSM）を作り，そしてそのFSMの状態を1つずつ探索することによって最適コード生成を行う方法を提案している．本稿では論文2）、3）と同様のアプローチをとるが，それらの論文と異なりFSMからコード生成する際にFSMをシンボリックに解析することで，はるかに多くの状態を高速に探索したうえで，より最適な並列コードを生成する方法を提案する．論文21）?23）も本稿と同様にFSMのシンボリック状態探索によりマイクロコードを生成する手法を提案しているが，オペランドの寿命が判定できないため，必要以上に多くの状態を計算してしまう可能性がある．本稿では新たなFSM変数を導入してオペランドが保持する必要があるかどうかを決定するような条件を導き，不要な状態の削減を図る．さらに本稿ではRAMへのスピルおよびリロードも考慮し，コード生成のすべてのフェーズを同時に実行したうえでステップ数最小のコードを生成する．最後に提案手法の実験結果を示す．

As key components in high-speed embedded systems,a number of application specificprocessors with parallel instructions, special datapath units,registers or bus architecture are coming into the embedded market5)縲鰀10).However, it is difficult to generate code that fully utilize hardware units in these processors only by traditionalcompiler techniques1). To resolve this problem,Roemer et al.2),3) builtFSM from given DFG (Data Flow Graph) and instruction set.Then they traversed the states of the FSM explicitly to generate code.In this paper, we basically use the same approachwith the paper2),3).Differently from the approach, our approach analyzes the FSM symbolically andtraverses much more states so that it can possibly generate parallel codewith smaller number of steps in less time. Monahan etal.21)縲鰀23)also proposed the use of symbolic state traversal to generatemicrocode. However the approach cannot determine operand lifetime sothat it may produce many unnecessary states.Our approach uses a new FSM variable to build a condition whichdetermines if an operand must be kept or not so as to reduce theunnecessary states.In addition, our approach generate codes with the minimum number ofsteps in completely phase-coupled manner considering memory spillsand reloads.Finally, experimental results are shown.

収録刊行物

被引用文献 (5)*注記

もっと見る

参考文献 (26)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ