(57)【特許請求の範囲】
【請求項１】
コンピュータのメモリデバイスに記憶された実行可能なプログラムに関連付けられた時間計算量を検出する方法であって、
（１）前記記憶されたプログラムをコンピュータプロセッサで自動的に解析して、そのコード内のループに基づいて前記プログラムの時間計算量を検出することと、
（２）前記記憶されたプログラムを前記コンピュータプロセッサで自動的に解析して、前記プログラム内の前記コードのフローと分岐命令の分岐先とに基づいて前記プログラムの時間計算量を検出することと、
（１）で検出される時間計算量と（２）で検出される時間計算量との最小時間計算量を前記プログラムの時間計算量として自動的に決定することとを備える、方法。
【請求項２】
実行可能なマシンコードプログラムの各命令行に関連付けられた時間計算量を検出する方法であって、各命令行はそれに対応する時間計算量に従って視覚的にマーク付けされ、
前記マシンコードプログラムの個別の行に対応するノードが前記プログラムの制御フローに基づいて接続されるようにコードのフローグラフを作成することと、
閉路を形成する、前記コードのフローグラフ内の複数のノードのあらゆるグループに対応する複数の強連結部分グラフを識別することと、
前記複数の強連結部分グラフを、１つの集合の各強連結部分グラフが同じ根ノードを共有するように複数の集合にグループ分けすることと、
前記複数の集合のうちの１つの集合に含まれる根ノードが他の集合に含まれるか否かに基づいて前記複数の集合の有向グラフを構築することによって、集合グラフを作成することと、
親を持たないノードに到達するまで前記各集合の各ノードをノードを繰り返すことなく後向きにノード走査したときの最長の数を求めることによって、前記集合グラフにおける最長の経路を解析することと、
前記最長の経路の解析におけるノード走査の数を用いて、数が小さい方から大きい方への複数の集合のソート済みリストを作成することによって、複数の集合をソートすることと、
ノード走査の値に基づいて、ｐ＝０，１，２，・・・である時間計算量値ｐをコードの各命令行に割り当てることと、
前記マシンコードプログラムの各行について時間計算量の尺度Ｏ（ｎｐ）を割り当てることとを備える、方法。
【請求項３】
コードを記憶する非一時的なメモリデバイスにアクセスするコンピュータプロセッサによって実行され、コードを動的に実行する必要なしにコードの時間計算量を推定するコンピュータの動作方法であって、
前記コードの複数の分岐を決定する決定ステップと、
前記複数の分岐のうち第１の決定された分岐が、前記複数の分岐のうちの、前記第１の分岐よりもスキップする命令の数が多い他の決定された分岐内に完全に含まれるか否かを確認する確認ステップと、
前記確認ステップにおいて前記第１の分岐が完全に含まれると確認された場合、前記第１の分岐に関連付けられた増加した時間計算量を示す時間計算量ステップと、
前記コードの最大時間計算量を推定するために、前記コード内の前記複数の分岐のうち複数のさらに決定された分岐について、前記決定ステップ、前記確認ステップ、および、前記時間計算量ステップの少なくとも一部を再帰的に実行する実行ステップとを前記コンピュータプロセッサが実行する、方法。
【請求項４】
前記コード内の各決定された分岐について、前記実行ステップが再帰的に実行される、請求項３に記載の方法。
【請求項５】
前記複数の分岐は複数の命令を含み、前記実行ステップは、前記複数の命令に関連付けられた、前に割り当てられた時間計算量の値と、前記複数の分岐に関連付けられた前記示された時間計算量とを比較して、前記複数の命令のそれぞれについて時間計算量を割り当てる、請求項３に記載の方法。
【請求項６】
前記決定ステップは、前記コードの順序付き静的リストにおいて、前記複数の決定された分岐が前記順序付きリストの複数の前の部分に分岐するか否かを判定することを備える、請求項３に記載の方法。
【請求項７】
前記決定ステップは、所定の方向に分岐する前記コード内の複数の分岐を決定する、請求項３に記載の方法。
【請求項８】
前記所定の方向は、命令を実行順に上から下へ並べた場合における上向きを含む、請求項７に記載の方法。
【請求項９】
人間によって知覚可能な表示を提供するために、前記推定される最大時間計算量を表示装置上に表示することをさらに含む、請求項３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、２０１０年１月２９日に出願された米国出願第６１／２９９，４７７号の優先権を主張するものであり、その全内容は参照によって本明細書に組み込まれる。
【０００２】
本明細書の技術は、コードにおける大まかな時間計算量を自動的に解析し、コンピュータのアセンブリコードおよび／またはマシンコードの書式を設定して、コードを読むユーザによる基礎的なフローの理解を高める方法および装置に関する。さらに詳細には、本明細書の技術は、矢印、字下げ、テキストの記号を用いるなどしてアセンブリコードおよび／またはマシンコードの書式を設定しグラフィカルに提示して、コードを読むプログラマによるプログラムのフローひいてはプログラムがどのように動作するかの理解を高める、視覚的手段を用いた手法に関する。
【背景技術】
【０００３】
（背景技術および概要）
デジタルコンピュータが最初に発明された頃、プログラマはコンピュータのＣＰＵが直接実行可能な２進数（１と０）または１６進数（０〜Ｆ）でプログラムを書いていた。１９６０年代以降ずっと、多くのコンピュータのフロントパネルには、プログラマがコンピュータに２進数の命令を直接プログラムする際に使用できるスイッチが並んでいた。しかしながら、２進数でコードを書くのは大変な作業であり間違いも起こりやすかった。その結果、１９５０年代からプログラマはいわゆる「アセンブリ言語」で書き始めた。アセンブリ言語では２進数のマシンコード命令と人間が書いたアセンブリ言語命令とが１対１で対応していたが、機械語のオペレーションコード（オペコード）の代わりにニーモニック（覚えやすい短い記号列）が用いられ、マシンアドレスの代わりには記号が使用された。アセンブリ言語で書く場合でも、依然としてプログラマには自分がプログラムを書いている対象のハードウェアを深く理解する必要があったが、プログラマの作業は単純化され、間違いのもともなくなった。
【０００４】
アセンブリコードはハードウェアの機能性と密接に絡み合っているため、優れたアセンブリ言語のプログラマであれば実行効率、信頼性、速度、プログラムの大きさを最適化できた。このことは、プログラマがリソースに制約のあるコンピューティングプラットフォームのパフォーマンスを余すところなく引き出したい場合に特に重要であった。
【０００５】
半世紀余り経って、現代のコンピュータはプロセッサ速度、メモリの記憶容量、その他の性能特性の点で比較的膨大なリソースを有するようになっている。また、現在では様々な異なる種類のプロセッサや命令セットを有する膨大な数のコンピューティングプラットフォームが存在する。その結果、現代の大部分のコンピュータプログラムが主にＪａｖａ、Ｃ＋＋等の高水準言語で書かれている。このような高水準言語は、多数のコンピューティングプラットフォーム間での移植性や、特定のコンピューティングデバイスに対する人間のプログラマの細かい操作が不要であることなど、多くの利点を有する。典型的なコンピューティングプラットフォームは高水準言語を直接実行する。逆に、まず高水準命令がコンパイルまたは解釈されて、これらの命令を実行する特定のプロセッサが実行可能な、低水準の「マシンコード」を作成する。業界全体が、高水準言語から種々のプラットフォームにおけるマシンコードに最適な変換を行うコンパイラ、リンカ、その他のツールの開発を専門としているところもある。
【０００６】
一般的に言って、もしプログラマが今でもすべてのコードをアセンブラで書いていたら、今日我々が当然だと考える豊かなクロスプラットフォームのソフトウェアの機能性を提供することは非現実的または不可能であろう。実際、アセンブリを使いこなせる現代のプログラマは比較的珍しい。しかしながら、アセンブリ言語命令やマシンコード命令によって彼らの存在が今でも重要となる事例もある。
【０００７】
例えば、あるゲームをプログラムする際に極度の最適化が要求される状況がある。一例として、毎秒何百回、何千回と繰り返し実行されうるゲームプログラム内のプロセッサ集約型アルゴリズムにおける内側のループを、極限まで最適化することが必要な場合がある。現代の最適化コンパイラならばいかなる人間のプログラマよりも上手く最適化できるという意見がある一方、これには異論もあり、対象のハードウェアを十分に理解し、ある機能の遂行に必要な命令数を最小化することに創造力を傾けることができる人間に代わるものはないとも考える人々もいる。
【０００８】
また、元々アセンブリで書かれた古いゲームコードを現在になって理解および／または変更しなければならないことがある。他に起こる興味深い状況としては、プログラマが特定のゲームのソースコードにアクセスできないにもかかわらず、ゲームコードの特定の箇所がどのように実行するかを理解しなければならないような場合がある。マシンコードを逆アセンブルしてニーモニックを用いたアセンブリ言語を得ることはできるが、このようなコードを理解することは、特に高水準言語で書くのに慣れているプログラマには困難となりうる。
【０００９】
通常、プログラマがマシンコードを直接扱うことはない。しかしながら、これらの命令を人の手でコーディングしたり、コンパイラで生成されたマシンコードを確認する必要が時として生じる。
【００１０】
よって、このような場合には、人間がより容易に理解できるようにマシンコードを視覚化できれば有益となる。本明細書に記載する技術は、協働してマシンコードを向上および変換させることにより、関数またはプログラムにおける制御のフローを人間がより容易に理解できるようにする特定の手法に向けられている。
【００１１】
どのようなコードを読む場合でも、プログラムのフローは全体的な理解をする上で非常に重要である。通常、フローはある機械命令から次の機械命令へと進む。しかしながら、条件分岐や無条件分岐は実行を条件付きまたは無条件で任意の命令へとスキップさせるため、フローが複雑になる。フローは、前に実行された命令に分岐することにより、命令のシーケンスが任意の回数実行される可能性のある「ループ」として知られる状態にもなりうる。
【００１２】
数学、計算機科学、および関連分野においては、ビッグＯ記法（ビッグオー記法、ランダウ記法、バッハマン・ランダウ記法、漸近記法としても知られる）によって、引数が特定の値または無限大に向かうときの関数の漸近挙動を、大抵はより簡単な関数に置き換えて記述する。ビッグＯ記法によって、ユーザは関数を単純化してこれらの増加率のみを扱うことができ、異なる関数でも増加率が同じであれば同じＯ記法で表すことも可能となる。この記法は純粋数学の一部として発展してきたが、現在では、アルゴリズムの解析にこれを用いてアルゴリズムによる計算リソースの使用状況を記述することがよくあり、アルゴリズムの最悪実行時間または平均実行時間、あるいはメモリ使用量をその入力の長さの関数としてビッグＯ記法を用いて表すことが多い。これによりアルゴリズム設計者は、コンピュータアーキテクチャやクロック速度とは関係のない方法でアルゴリズムの挙動を予測し、多数のアルゴリズムの中でどれを使用するかを判断できる。ビッグＯ記法は実行時間における乗法定数を切り捨て、入力サイズを小さくするような効率も無視するため、実際上の最速のアルゴリズムや実用的なサイズのデータセットに関する最速のアルゴリズムを必ずしも示すものではない。それでもこのアプローチは、入力サイズが大きくなる場合に種々のアルゴリズムのスケーラビリティを比較する上で依然として非常に有効である。ビッグＯ記法に置き換えて関数を記述した場合、大抵は関数の増加率における上界が得られるだけである。漸近的増加率における他の種類の有界性を記述するために、関連するいくつかの記法がｏ、Ω、ω、Θ等の記号を用いてビッグＯ記法に関連付けられる。また、ビッグＯ記法は多くの他の分野でも同様の推定を目的として用いられる。ウィキペディア「Ｂｉｇ  Ｏ  Ｎｏｔａｔｉｏｎ」を参照のこと。
【００１３】
プログラムのフローおよび計算量を解析する別の手法も存在する。例示を目的とする非限定の手法の一例は、分岐状態を表す「字下げレベル」に基づくものである。一般的に言って、コンピュータプログラムにおける分岐状態やループ状態は、その分岐やループ内のコード部分を字下げして示すことが多い。したがって、ループ状態の４つのレベルは４レベルの字下げで示すことができる。例示を目的とする非限定の実施の一例は、このような文字配列の体裁を利用して、字下げレベルに基づいてプログラムの計算量を解析する。ある字下げレベルから他のレベルに移行することで計算量の変化を示すことができる。一般的に言って、字下げレベルが大きいほどプログラム構造はより複雑となる。このように、字下げレベルに基づく自動プログラム解析はプログラムの計算量の有用な尺度の一つとなりうる。
【００１４】
例示を目的とする非限定の実施の一例では、前向き／下向きか後向き／上向きかいずれかの分岐矢印を自動的に生成し、これらを用いて、マシンコードが実行するプログラムのフローを視覚的に示す。こうして提示することで各マシンコード命令の分岐先が強調され、これにより、例えばプログラマ等のそれを読む人間がプログラムのフローをより容易かつ速やかに把握できる。
【００１５】
例示を目的とする非限定の実施の他の例では、種々のマシンコード命令行の字下げを自動的に生成し、これらを用いて、マシンコードが特定のマシンコード命令から他の命令に分岐してブロックへ自然に分割する様子を視覚的に示す。一部の実施では、分岐コマンドの分岐先にマシンコードの分岐命令において視覚的に注釈付けし、視覚的なマークを有するマシンコード命令に遭遇するまで字下げを継続する。
【００１６】
例示を目的とする非限定の実施のさらに他の例では、マシンコードのフローおよび計算量が、各マシンコードのブロックまたは各マシンコード命令に関連付けられた時間計算量を計算し、それに従ってマシンコードの種々のコンポーネントにマーク付けすることによって、自動的に解析され視覚的に注釈付けされる。
【００１７】
プログラムの計算量を解析する別の方法は「強連結部分グラフ法」と称することができ、これを用いてプログラムアセンブリ命令の最悪のケースにおける大まかな時間計算量を検出できる。例示を目的とする非限定の実施の一例では、時間計算量はプログラムの構造的計算量とは異なる場合がある。このような手法はコードのフローと分岐命令の分岐先とに基づくことができ、時間計算量を入れ子のレベルに置き換えて検出してもよい。このような手法では、例えばコードのフローグラフを作成し、複数の強連結部分グラフを識別し、複数の強連結部分グラフの複数の集合を作成し、集合グラフを作成し、集合グラフにおける最長の経路を解析し、複数の集合をソートし、解釈、表示等のための時間計算量を割り当てる。
【００１８】
強連結部分グラフ法では、行単位の命令のシーケンスの内容を網羅的に調べ、閉路の様々な推移を識別する（各強連結部分グラフを表す）ことによって、プログラムの動的なフローの内容を調べる。このように入れ子のレベルを検出することにより、プログラムの実際の使用状況をその種々の部分から検出できる。
【００１９】
時間計算量を計算する字下げレベルまたは「アップブランチ法」と、時間計算量を計算する強連結部分グラフ法とは相違点およびそれぞれの長所と短所を有する。例えばアップブランチ法では、アルゴリズムが行番号に基づいてグループ分けを行う性質上、実際にはコードの行が閉路の一部ではない可能性がある場合に、この行の時間計算量が誤って大きく判断されることがある。アップブランチ法は控えめなものであり、コードの最初か最後の行が複数の閉路間で共有される場合には閉路を含むとは認識せず、ある閉路が行番号に関して他の閉路と部分的に重複する場合にも閉路を含むとは認識しない。一方、強連結部分グラフ法は、ソースコードまたはアセンブリコードが実際には結果としてこの時間計算量とならない可能性がある場合でも、閉路を含むと積極的に認識する傾向がある。これは、例えば分岐を行うコードの各行の実際の計算が解析されないことによる。強連結部分グラフ法では、コードの行の時間計算量が誤って理論的に可能な時間計算量よりも小さく判断されることは決してないため、計算されるすべての時間計算量が最大値となる。
【００２０】
アップブランチ法による時間計算量アルゴリズムおよび強連結部分グラフ法による時間計算量アルゴリズムの長所と短所を踏まえて、これらを組み合わせた方策を採用できる。例えば、強連結部分グラフ法を用いて、理論的に可能な（例えばナイーブなコードのフローおよび分岐フローに基づいた）最悪時間計算量を決定してもよい。そして、コードの各行の最小時間計算量は、アップブランチと強連結部分グラフ法とのいずれかから選択して、時間計算量を控えめに推定しつつ、アップブランチ法に存在する実際よりも大きい誤った時間計算量を除外できる。
【００２１】
これらおよび他の特徴、効果は、例示を目的とする非限定の実施例の以下の詳細な説明を以下の内容の図面と照合して参照することにより、一層良く、一層十分理解されるであろう。
【図面の簡単な説明】
【００２２】
【図１】図１は、非限定のコンピュータシステムの一例の内部構成を概略的に示す。
【００２３】
【図２】図２は、本発明によるコンピュータシステムの非限定の実施例を概略的に示す。
【００２４】
【図３】図３は、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。
【００２５】
【図４】図４は、分岐先矢印を有するマシンコードのブロックの表現の非限定の実施例を概略的に示す。
【００２６】
【図５】図５は、字下げした分岐を有するマシンコードのブロックの表現の非限定の実施例を概略的に示す。
【００２７】
【図６】図６は、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。
【００２８】
【図７】図７は、時間計算量を区別するマークを有するマシンコードのブロックの表現の非限定の実施例を概略的に示す。
【００２９】
【図８】図８は、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。
【００３０】
【図９】図９は、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。
【００３１】
【図１０】図１０は、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。
【００３２】
【図１１】図１１は、コードシーケンスとアップブランチ法を用いて得られたこのコードシーケンスの時間計算量との一例を示す。
【００３３】
【図１２】図１２は、図１１のコードシーケンスと強連結部分グラフ法を用いて得られたこのコードシーケンスの時間計算量とを示す。
【００３４】
【図１３】図１３は、図１１のコードシーケンスとアップブランチ法および強連結部分グラフ法の組み合わせを用いて得られたこのコードシーケンスの時間計算量とを示す。
【発明を実施するための形態】
【００３５】
本明細書に記載する手法は、コンピュータプラットフォーム、パーソナルコンピュータ、ネットワークサーバ、据置型または携帯型ビデオゲーム機、計算能力を有するその他のあらゆる種類の装置または構成を含む、あらゆる種類のコンピュータまたはゲームシステムにおいて実行可能である。以下に、例示を目的とする非限定の実施の一例を説明するが、その他の実施も可能である。
【００３６】
図１は、本明細書に提示する本実施例が実装されたハードウェアプラットフォームの非限定の一例を示す。プラットフォーム１００は、中央処理装置（ＣＰＵ）１０１、ハードディスクドライブ（ＨＤＤ）１０２等の不揮発性記憶装置またはフラッシュメモリデバイス、ランダムアクセスメモリ（ＲＡＭ）１０３、グラフィックスプロセッサ１０４、入力装置インターフェイス１０５、通信インターフェイス１０６を含む。ＣＰＵ１０１は、共通バス１０７を介して他の構成要素とやり取りしながらプラットフォームを制御する。ＲＡＭ１０３は、ＣＰＵ１０１が実行するオペレーティングシステムプログラムおよびアプリケーションプログラムの少なくとも一部を一時的に記憶する。記憶装置１０２は、ソフトウェアツールに加えて、（もしあれば）オペレーティングシステム（ＯＳ）およびアプリケーションプログラムも記憶する。図１では１つのコンピュータプラットフォームを示しているが、他の複数のコンピュータがネットワーク４０に接続され、各コンピュータが本明細書に提示する本実施例で構成されてもよい。
【００３７】
グラフィックスプロセッサ１０４は、ＣＰＵ１０１からのコマンドに応じて映像を作成し画面１０に表示する。入力装置インターフェイス１０５は、例えばキーボード２０、マウス３０、ゲームコントローラ３２、３４等の外部入力装置から信号を受け取る。これらの入力信号はバス１０７を介してＣＰＵ１０１に供給される。通信インターフェイス１０６によって、ＣＰＵ１０１はネットワーク４０上で他のコンピュータとデータ交換が可能になる。
【００３８】
図２は、本明細書に提示する本実施例で構成される、プラットフォーム１００で実行される処理機能を示すブロック図である。より具体的には、プラットフォーム１００は、エディタ２００、複数のソースファイル２１０、２１１、２１２等、コンパイラまたはアセンブラ２０１、複数のオブジェクトファイル２２１、２２２、２２３等、マシンコードエディタ２０２、複数の変更オブジェクトファイル２３１、２３２、２３３等、リンカ２０３、複数の実行ファイル２４１、２４２、２４３等、逆アセンブラ２０４、通信プロセッサ２０５等の演算要素を含む。
【００３９】
ソースファイル２１０、２１１、２１２は、プログラミング言語で書かれたソースコードの形式で処理を表す。オブジェクトファイル２２１、２２２、２２３は、コンピュータ１００が直接実行可能な特定のマシンコードの形式で処理を表す。変更オブジェクトファイル２３１、２３２、２３３は、後述するように、ユーザがオブジェクトファイル２２１、２２２、２２３に対して行った変更を表す。実行ファイル２４１、２４２、２４３は、１つ以上の変更オブジェクトファイルを１つのファイルに結合することでそれぞれが作成された変更マシンコードファイルである。上記のファイルはすべて記憶装置１０２および／またはＲＡＭ１０３に記憶される。
【００４０】
逆アセンブラ２０４は、実行ファイル２４１、２４２、２４３をアセンブリ言語の「ソース」ファイル２４５、２４７、２４９に変換し、これらの「ソース」ファイルは一実施では、２進数（１６進数）の機械命令とそれに１対１で対応するアセンブリ言語の「ソース」命令との両方を含んでおり、これらの「ソース」命令はオペコードのニーモニック、アドレスラベル、関数呼び出しラベルで構成される。
【００４１】
ユーザはエディタ２００を用いてソースコードを書いたり編集したりできる。例えばプログラマ等のユーザは、例えばＣ＋＋言語等の適切なプログラミング言語で命令のセットを入力する。そして、彼／彼女はエディタ２００に保存コマンドを与え、エディタ２００はその結果得られたソースファイルを記憶装置１０２に書きこむ。
【００４２】
コンパイラ２０１は、ソースファイルを受け取りマシンコードを生成する。これは記憶装置１０２にアクセスして、プログラマが書いたソースファイルを読み出し、ファイル内のソースコードの各行をパースし、ソースコードをコンピュータ１００が理解可能なマシンコードに変換して行われる。この処理はコンパイルとして知られ、コンパイルの出力はオブジェクトコードと呼ばれる。コンパイラ２０１は、コンパイルされたオブジェクトコードをオブジェクトファイルとして記憶装置１０２に保存する。
【００４３】
続いて、本明細書に提示する本実施例によれば、プログラマ等のユーザには、コンパイラ２０１が作成したマシンコードを確認し、場合によってはマシンコードや対応する高水準のソースコードの変更も行うという選択肢があり、これにより変更オブジェクトファイル２３１、２３２、２３３等のマシンコードの変更バージョンが、将来の確認、想定されるデバッグ、および／または想定される修正のためにより見やすく提示されることになる。本明細書に提示するこれらの変更手法は、コンパイラから出力されるマシンコードをユーザがその計算量だけでなくそのフローに関してもより良く理解することを助け、さらに、最適化コンパイラ２０１がソースコードをどのようにコンパイルするかをユーザが理解することも助ける。
【００４４】
リンカ２０３は、記憶装置１０２にアクセスし、ユーザが作成した１つ以上の変更オブジェクトコードファイルを読み出す。そして、リンカ２０３は、これらの変更オブジェクトコードファイルを単一のロードモジュールへ結合しながら、いくつかの部分を編集して解決済みの絶対アドレスおよび相対アドレスとともに命令の一貫したセットとして整理する。この処理はリンクとして知られる。リンカ２０３は、これらの実行ファイル２４１、２４２、２４３を記憶装置１０２に保存する。
【００４５】
通信プロセッサ２０５は、ネットワーク４０内の他のコンピュータに加えて、ソースファイル、オブジェクトファイル、変更オブジェクトファイル、実行ファイル、アセンブリ言語ファイルのいずれとも通信している。
【００４６】
上記のように、マシンコードはコンピュータの中央処理装置（ＣＰＵ）が直接実行する命令のセットである。一般に、マシンコードはほとんどの人々にとっては読んで理解するのが非常に困難である。これらのコンピュータの命令は、コンパイルされたコンピュータプログラムおよび／またはアセンブリコンピュータプログラムが最低水準で表現されたものと考えてもよく、ＣＰＵの実行対象と１対１で対応してもよい。各プロセッサファミリには固有のマシンコードの命令セットがある。これらの命令はマシンに対する異なるコマンドと対応している。
【００４７】
マシンコードの命令セットは、すべての命令の長さが同じであってもよく、また命令の長さが可変であってもよい。大部分の命令は１つ以上のフィールドを有し、これらによって実際の演算（例えば加算または比較）、アドレッシングモード、アドレス指定オフセット、または実際の値そのものに加えて、基本的な命令の種類（例えば算術、論理、ジャンプ等）も特定される。
【００４８】
図３は、本明細書に提示する本実施例による、マシンコードを変更して人間による理解を高める方法の、例示を目的とする非限定のソフトウェアのフローチャートの一例を示す。まずステップＳ１において、コンピュータ１００は、ユーザが書いて入力した、例えばＣ言語のソースコードを受け取る。続いてステップＳ２において、コンピュータ１００のコンパイラ２０１は、受け取ったソースコードをマシンコードにコンパイルする（あるいはコンパイラ２０１は、中間のアセンブリ言語コードを作成し、その後これを図示しないアセンブラがマシンコードに変換してもよい）。ユーザはマシンコードを受け取り（ステップＳ３）、それを調べ、後述する手法の１つを用いてそのプログラムを適宜変更する（ステップＳ４）。そして、コンピュータ１００は、変更されたコードを受け取り、リンカ２０３を介して実行ファイルを生成し（ステップＳ５）、ステップＳ６において、これが出力コードとして出力される。
【００４９】
一実施例によれば、命令フローの理解を結果的に要するコードの見直しや変更は、以下の３つの主な方法で支援される。
【００５０】
（マシンコードにおける矢印注釈付き分岐）
マシンコードの分岐命令は、大抵は分岐先のオフセットまたはアドレスを特定するだけである。分岐先の追跡はとりわけ精神的な労力を要するため、分岐から分岐先の命令まで矢印を描くことでマシンコードを単純化してもよい。一部の分岐が前の機械命令に関連付けられ、一部が後続の機械命令に関連付けられることを考慮すると、これらの矢印は規則的に整理できる。
【００５１】
一実施例では、前向き／下向きの分岐矢印はすべてコードの左側に現れ、後向き／上向きの分岐矢印はすべてコードの右に現れる。こうして提示することで、矢印は図４に示すように反時計回りの規則的なフローを有する。例えば図４で分かるように、コードの左側には４本の前向き／下向きの分岐矢印が存在し、コードの右側には２本の後向き／上向きの分岐矢印が存在する。
【００５２】
また、分岐先が同一の矢印同士を縦方向の進行で合体させて、混雑や矢印の数を減らしてもよい。例えば、これらの矢印は共通の縦方向セクションを有するように描かれてもよい。
【００５３】
規則的なコードの提示を保つためには、分岐先が近い分岐を分岐先が遠い矢印よりもコードの近くに配置するべきである。例えば図４で分かるように、コードの左側において、分岐先が「ｃｍｐｌｗ  ｒ９，  ｒ５」の分岐は分岐先が「ｃｍｐｌｗ  ｒ８，  ｒ４」の分岐よりも長いため、後者の分岐がコードにより近く描かれている。
【００５４】
本実施例では、コード内の他の関数に戻ったり結合したりする分岐は、単一の横方向の矢印または両矢印で表されるのが最も望ましい。例えば、コード内の他の関数に結合する分岐は、命令の右に向かう単一の横方向の両矢印で表され、戻り分岐は、命令の右に向かう単一の横方向の右向き矢印で表される（図４のコードの最後の命令行の右に向かう矢印を参照）。
【００５５】
（マシンコードにおける字下げ注釈付き分岐）
典型的には、マシンコードは字下げを含まない（しかし、高水準言語は字下げを含むことが多い）。言い換えれば、すべての命令行が縦方向に揃っている。この書式では、プログラムのフローを追跡する際に視覚的な洞察ができない。よって、外見的に理解するために、コードの論理ブロックに基づいてこれを可能にすることが望ましい。好ましい実施例では、すべての機械命令が順次反復される。
【００５６】
一実施例では、関数内の下向きの分岐に遭遇すると、その分岐先に字下げフリーズシンボルでマーク付けする（なお、この行はさらに字下げするべきではない）。例えば図５で分かるように、３番目の行で関数内の下向きの分岐に遭遇し、分岐先である行２８に「＊」等の字下げフリーズシンボルでマーク付けする。同様に、下向きの分岐の分岐先に対応する行１５、１７、２５にもそれぞれ字下げフリーズシンボルでマーク付けする。
【００５７】
本実施例では、関数内の上向きまたは下向きの分岐に遭遇すると、字下げフリーズシンボルに遭遇するか関数の終わりに到達するまですべての後続の行が字下げされる。そして、分岐に続く行で処理が再開される。例えば図５のコード表現の場合、行２で分岐に遭遇するため、後続の行３は字下げされ、以降の各行が、行２８で字下げフリーズシンボルに遭遇するまで字下げされる。この字下げの効果により、分岐命令に続くコードの重要性が強調される。
【００５８】
図６は、字下げアルゴリズムの一例を示すものであり、これに従って、各機械命令の字下げレベルをそれが分岐命令の分岐先でない限りタブ１つインクリメントする。
【００５９】
まず、すべての機械命令を字下げレベルがゼロとなるように初期化する（ステップＳ１０）。続いてアルゴリズムはコード内のすべての機械命令のリストを最初から最後までたどる。例えば図５に示すコードの場合、アルゴリズムは最初の「ｌｉ  ｒ１０，０」から最後の「ｂｌｒ」まですべての機械命令を検討する。次にアルゴリズムは、分岐機械命令に遭遇したか否かを判定する（ステップＳ１２）。答えが否定の場合、アルゴリズムは戻り、機械命令のリストをたどり続ける。一方、答えが肯定の場合、アルゴリズムは、遭遇した分岐が下向きの分岐であるか否かを判定する（ステップＳ１４）。判定に対する答えが否定の場合、アルゴリズムはステップＳ１５Ａ（後述する）へ進む。答えが肯定の場合、アルゴリズムは検討中の機械命令において、分岐の分岐先にフリーズトークンでマーク付けし（ステップＳ１５）、次のステップへ進む。
【００６０】
下向きの分岐の分岐先を指定する機械命令においてフリーズトークンでマーク付けした後、ステップＳ１５Ａにおいて、アルゴリズムは各行の字下げレベルをインクリメントしながら後続の一連の機械命令をたどる。各機械命令を終えるごとに、アルゴリズムは、フリーズトークンに遭遇したか否かを判定する（ステップＳ１７）。答えが否定の場合、アルゴリズムはステップＳ１６へ進む。一方、答えが肯定の場合、アルゴリズムはその機械命令行の字下げレベルをインクリメントせず、ステップＳ１２へ戻る（現在の行番号が最後の行番号ではないものとして、ステップＳ１２Ａ、Ｓ１２Ｂ参照）。最後にアルゴリズムは、機械命令がすべての機械命令のリストの最後であるか否かを判定する（ステップＳ１２Ａ）。そうであればアルゴリズムは終了し（ステップＳ２０）、そうでなければ、現在の行番号をインクリメントした後にステップＳ１２に戻る。
【００６１】
図６の字下げアルゴリズムの適用例が図５に示される。下向きの分岐に遭遇する最初の命令行は３番目の行である。したがって、その行が分岐する分岐先にフリーズトークンを用いてマーク付けし、そして、次の行（行３）はタブ１つ字下げされ、各後続の行は、行２８にフリーズトークンがあることから行２８まで字下げされる。行４に続く後続の行５〜１１は字下げされ、この処理は最後の行「ｂｌｒ」（命令の右に向かう単一の横方向の右向き矢印で表される戻り分岐）に到達するまで継続する。他の実施例では、フリーズシンボルの配置や字下げを行う場合には無条件分岐のみを検討する。これにより、外観が若干異なる／より分かりやすくなる。
【００６２】
（マシンコードにおけるアップブランチ法を用いた時間計算量注釈付きブロック）
他の実施例では、マシンコードの各行に、分岐の結果生じる時間計算量の推定を表す視覚的指標でマーク付けできる。これは、分岐の結果としての重要な特徴とプログラムのフローとを視覚的に判別するさらに他の方法である。典型的なマシンコードでは、コード内に多数のループが設けられていると、プログラマは行や複数の行によるブロックの計算量を速やかに読んで理解することができない。
【００６３】
例えば、いかなるループも含まないコードは実行時間が一定であると判断され、典型的にはビッグＯ記法でＯ（１）として表される。一方、単一のループで構成されるコードは時間計算量がオーダーｎまたはＯ（ｎ）であると判断され、このときｎはループの実行が可能な任意の回数である。さらに、コードのループが他のコードのループ内に存在する場合、つまりコードが入れ子のループを有する場合、内側のコードのループは時間計算量がオーダーｎ２またはＯ（ｎ２）であると判断される。このとき、外側のループはｎ回実行可能であり、内側のループは外側のループ１周につきｎ回実行可能であるため、結果として内側のループは合計ｎ×ｎ回反復される。同様に、コードのループ内のコードのループ内のコードのループから成る三重のループでは、最も内側のループの時間計算量がオーダーｎ３またはＯ（ｎ３）となる。
【００６４】
例えば図７に示すように、３番目の行と最後から２番目の行との間の命令行から成るブロックは単一のループで構成されるため、Ｏ（ｎ）で表される。一方、行４と行２６との間の行から成るブロックは他のループ内のループで構成されるため、Ｏ（ｎ２）で表される。
【００６５】
コードの各行の時間計算量を知らせることは、そのコードの構造およびフローを理解するのに役立つため、重要な時間計算量のセクションにはそれぞれ強調表示の色やその他の視覚的表示で視覚的にマーク付けしてもよい。この手法の一実施例としては、図７に示すように、例えば時間計算量がＯ（１）のコードのセクションは白で、時間計算量がＯ（ｎ）のコードのセクションは黄で、時間計算量がＯ（ｎ２）のコードのセクションはオレンジ色でそれぞれ色をつける（一般に特許はカラー印刷されないため、これらの異なる色を陰影で表現している）。他の実施例としては、時間計算量が悪化するコードには特定の色の単色グラデーションで色をつける。
【００６６】
例えば図７に示すように、計算量がレベルＯ（ｎ）のセクションは、例えば黄色（薄い陰影）で表現され、計算量がレベルＯ（ｎ２）のセクションは、例えばオレンジ色（中間の陰影）で表現される。
【００６７】
マシンコード命令の各ブロック全体の時間計算量を指定するだけでなく、一実施例では、個別のマシンコード命令の時間計算量も指定する。
【００６８】
マシンコードにおいてループは、前のマシンコード命令へ条件付きまたは無条件で分岐するマシンコード命令で決定できる。このループは、マシンコード分岐の分岐先とこのマシンコード分岐自体との間で表されるすべてのマシンコード命令のセットである。あるマシンコード命令の時間計算量は、ループが他のループ内に存在するには完全に含まれていなければならないという要件で、このマシンコード命令が内部に存在するループの最大数で決定できる。マシンコード命令がいかなるループの中にも存在しない場合、時間計算量はＯ（１）である。マシンコード命令が１つだけのループ内に存在する場合、時間計算量はＯ（ｎ）である。マシンコード命令が２つのループ（ループ内のループ）内に存在する場合、時間計算量はＯ（ｎ２）である。マシンコード命令が３つのループ（ループ内のループ内のループ）内に存在する場合、時間計算量はＯ（ｎ３）である。マシンコード命令の時間計算量のこの定義は一定のパターンに従って無限に続く。
【００６９】
本明細書に提示する非限定のアップブランチ法の一例は、コードが書かれたインラインの順序に基づいて時間計算量を推定するヒューリスティックな手法を提供する。人間のプログラマは入れ子を反映した順序でコードを書くことが多い。例えば、コードの一部分がエントリーポイントを含み、その後に多数のインオーダー命令が続き、その後にループが続いてエントリーポイントへ戻っている場合、この人間のプログラマがインオーダー命令をループの一部となるように意図したことが推測できる。この前提が必ず正しいとは限らないが、コードの他の部分からごくわずかにアクセスされるか、あるいは決してアクセスされない命令やコードの断片がコードのブロック内に存在することもあり、結果的にこれらはループの一部ではない。それにもかかわらず、プログラマがループ内の命令を定義するコードを書く際には、そのような命令もこのループの実行回数と同じだけ実行される可能性が高いため、本質的にはこのループに属している。このようにアップブランチ法は、ループに属する命令を、これらの命令をプログラマが書いたときの順序に基づいて推測するのに有用となりうるヒューリスティック解析を提供する。さらに、多くの場合、同じコードに対して異なるヒューリスティックな手法を実行して、アップブランチ法による時間計算量が正確でない状況を検出することで、アップブランチ法の精度を確認できる。
【００７０】
図８は、非限定のアルゴリズムの一例を示すものであり、これに従って、関数内のあるマシンコード命令の時間計算量が決定される（アップブランチ法と呼ぶ）。以下、種々の計算量レベルを、ゼロ＝Ｏ（１）、１＝Ｏ（ｎ）、２＝Ｏ（ｎ２）、３＝Ｏ（ｎ３）等で表す。
【００７１】
まずステップＳ３０において、アルゴリズムはすべてのマシンコード命令を時間計算量がゼロとなるように初期化する。次に、前の命令に分岐するすべての条件分岐または無条件分岐のリストを構築し（ステップＳ３１）、続いて、すべての上向きの分岐のリストを、スキップするマシンコード命令の数が小さい方から大きい方へソートする（ステップＳ３２）。そして、アルゴリズムはすべての上向きの分岐のリストをループし（ステップＳ３３）、各分岐について、分岐が１の時間計算量を表すとして分岐が表せる最大時間計算量を求める（ステップＳ３４）。分岐の最大時間計算量は図９のフローチャートによって決定される。続いてアルゴリズムは、分岐の分岐先から開始してマシンコード分岐自体で終了するまですべてのマシンコード命令をループし（ステップＳ３５）、この分岐が表す最大時間計算量がこのマシンコード命令に関する前に記憶された時間計算量よりも大きい場合、この分岐が表す最大時間計算量をこのマシンコード命令に関する新たな時間計算量として記憶し（ステップＳ３６）、終了する（ステップＳ３７）。
【００７２】
また、図９に示す以下のアルゴリズムは、初期的な計算量（明細書の最後に記載する疑似コード）を与えられると、ある分岐に関する最大時間計算量を決定できる。
【００７３】
当該分岐について、アルゴリズムはこの分岐よりもスキップする命令の数が多いすべての分岐をループし（ステップＳ４０）、ステップＳ４１において、当該分岐がこの反復で検討中の分岐内に完全に含まれる場合、計算量は、現在の計算量とこの反復で検討中の分岐の計算量とのうち量が大きい方に等しい（このアルゴリズムを現在の計算量とともに再帰的に呼び出すことで決定される）。最後にステップＳ４２において、アルゴリズムは計算量の値を返し、終了する（ステップＳ４３）。
【００７４】
（アセンブリコードにおける強連結部分グラフ法を用いた時間計算量注釈付きの行）
一実施例では、以下のアルゴリズム（強連結部分グラフ法と称する）によって、アセンブリコードの命令の最悪のケースにおける大まかな時間計算量が検出される。この方法はコードのフローと分岐命令の分岐先とに基づくものである。Ｏ（ｎｐ）に置き換えた時間計算量を検出できる。
【００７５】
図１０は、非限定のアルゴリズムの一例を示すものであり、これに従って、あるアセンブリコード命令の時間計算量が決定される。
【００７６】
（コードのフローグラフを作成）
まずステップＳ５０において、コードのフローグラフを作成する。より具体的には、アセンブリコードの各行をノードとしてこれらのノードがプログラムの制御フローに従って接続された有向グラフを作成する。例えば３行からなるアセンブリプログラムの場合、通常、コードのフローはある行から次の行へと進むため、これに対応するコードのフローグラフは｛１→２，２→３，３→ｎｕｌｌ｝となる。最初のコード命令が行３への条件ジャンプであれば、新たなグラフは｛１→２，１→３，２→３，３→ｎｕｌｌ｝となる。
【００７７】
（各強連結部分グラフを識別）
次にステップＳ５１において、アルゴリズムは各強連結部分グラフを識別する。深さ優先探索を開始ノードから行って、コードのフローグラフのすべての強連結部分グラフを識別する。強連結部分グラフは、閉路を形成するあらゆるノードまたはノードのあらゆるグループである。より正確に言えば、ＡからＢへの経路が存在しＢからＡへの経路が存在する場合（つまり、閉路が形成される場合）、ノードＡおよびＢは強連結部分グラフを形成する。強連結部分グラフが深さ優先探索中に識別されるのは、探索対象である次のノードが現在の走査に既に含まれるノードである場合である。こうして識別された強連結部分グラフは、現在の走査に含まれることが判明したノード（根ノードと呼ぶ）から開始して現在の探索走査の最終ノードまでが記録される。例えば深さ優先探索において経路｛１，２，３，４，５，２｝が探索される場合、強連結部分グラフ｛２，３，４，５｝が記録され、前の走査の最終ノードが葉（子を持たない終端ノード）であるかのように深さ優先探索を続行する。２つ以上の強連結部分グラフが同一である場合、これらの同一の強連結部分グラフのうち１つだけが保持される。
【００７８】
（強連結部分グラフの集合を作成）
各強連結部分グラフを識別した後、ステップＳ５２において、これらを同じ根ノードを共有する種々の集合に配置する。例えば強連結部分グラフ｛２，３，４｝および｛２，３，５｝は同じ根ノード２を有するため、同じ集合に含まれることになる。
【００７９】
強連結部分グラフを集合に追加する前に、この強連結部分グラフがこの集合内の他の強連結部分グラフの部分集合であるかが確認される。他のグラフの部分集合であるグラフは、他のグラフの連続部分と同一のグラフとして定義される。例えばグラフ｛２，３，４｝はグラフ｛２，３，４，５｝の部分集合である。この強連結部分グラフがこの集合内の他の強連結部分グラフの部分集合である場合、この集合には追加されず、逆に他の適切な集合に、同じ根ノードを有しかつその集合内のどの強連結部分グラフの部分集合でもないことを条件として追加される。強連結部分グラフをどの集合にも追加できない場合、この特定の強連結部分グラフが固有の集合を定義する。
【００８０】
（集合グラフを作成）
強連結部分グラフの種々の集合が作成された後、ステップＳ５３において、以下のアルゴリズムを用いてこれらの集合の新たな集合グラフを構築する。
【００８１】
ある集合Ｃ１が異なる集合Ｃ２内の他の強連結部分グラフ内に含まれる根ノードを有し、Ｃ２内のいずれの強連結部分グラフもＣ１内の強連結部分グラフの部分集合ではない場合（ノードのシーケンスの移動を考慮したとしても）、Ｃ１はＣ２の子として、例えばＣ２→Ｃ１のように定義される。例えば集合Ｃ１が｛３，４，５｝を含み、集合Ｃ２が｛２，３，４｝を含む場合、Ｃ１はＣ２の子である。さらなる例として、集合Ｃ３が｛２，３｝を含み、集合Ｃ４が｛３，２，４｝を含む場合、Ｃ３はＣ４の子であるが、Ｃ４はＣ３の子ではない（Ｃ３がＣ４の部分集合であるため）。一旦グラフが完成すると、Ｃ１がＣ２の子でＣ２がＣ１の子であるノードＣ１およびＣ２の各集合については、これらのノードをお互いに非連結にする。
【００８２】
（集合グラフにおける各ノードの最長の経路を解析）
次にステップＳ５４において、集合グラフにおける最長の経路を解析する。これらの集合の新たに作成された集合グラフを用いて、親を持たないノードへ到達するまで各ノードを後向きにノード走査したときの最長の数を求める。例えばＣ１→Ｃ２、Ｃ１→Ｃ３、Ｃ２→Ｃ３の場合、Ｃ１が親を持たない唯一のノードで走査コストはゼロであり、Ｃ２は走査コストが１であり（Ｃ１へ到達するのに１ノード走査する）、Ｃ３は走査コストが２である（Ｃ２を経由してＣ１へ到達するのに２ノード走査する）。
【００８３】
（集合をソート）
ステップＳ５４におけるノード走査による識別に続いて、ステップＳ５５において、ノード走査の数を基準として用いて、数が小さい方から大きい方へ集合のソート済みリストＬを作成する。
【００８４】
（時間計算量を割り当て）
次にステップＳ５６において、各ノード（つまり、コードの各行）に時間計算量（例えば自然数０、１、２、・・・ｐ）を割り当てる。まずコードの各行について、時間計算量をゼロに初期化する。そして、ソート済みリストＬの各集合について、（この集合の各強連結部分グラフ内の）コードの各個別の行の時間計算量をノード走査の値プラス１として割り当てる。
【００８５】
（時間計算量を置き換え）
最後にステップＳ５７において、各行に割り当てられた時間計算量に応じて、この行の計算量を以下のようにビッグＯ記法で表す。
０→Ｏ（ｎ０）＝Ｏ（１）
１→Ｏ（ｎ１）＝Ｏ（ｎ）
２→Ｏ（ｎ２）
３→Ｏ（ｎ３）
４→Ｏ（ｎ４）
・・・
ｐ→Ｏ（ｎｐ）
プログラムは終了（ステップＳ５８）
【００８６】
（例）
上記の強連結部分グラフ法を用いて、例えば以下のアセンブリコードプログラムの一例に関して時間計算量を検出できる。
Example assembly program（アセンブリプログラム例） #1
1: Do work（実行）
2: Do work（実行）
3: Do work（実行）
4: Conditionally branch to line 3（条件付きで行３に分岐）
5: Conditionally branch to line 7（条件付きで行７に分岐）
6: Do work（実行）
7: Conditionally branch to line 2（条件付きで行２に分岐）
8: Do work（実行）
Step 1: Create a code flow graph（コードのフローグラフを作成）
1 → 2
2 → 3
3 → 4
4 → 3, 4 → 5
5 → 6, 5 → 7
6 → 7
7 → 2, 7 → 8
8 → null
Step 2: Identify strongly connected subgraphs（各強連結部分グラフを識別）
1
1,2
1,2,3
1,2,3,4
1,2,3,4, (3)         Found
strongly connected subgraph（強連結部分グラフを発見）: 3,4
1,2,3,4,5
1,2,3,4,5,7
1,2,3,4,5,7, (2)     Found
strongly connected subgraph（強連結部分グラフを発見）: 2,3,4,5,7
1,2,3,4,5,7,8
1,2,3,4,5,6
1,2,3,4,5,6,7
1,2,3,4,5,6,7 (2)    Found
strongly connected subgraph（強連結部分グラフを発見）: 2,3,4,5,6,7
1,2,3,4,5,6,7,8
List of all strongly connected subgraphs（すべての強連結部分グラフのリスト）:
2,3,4,5,6,7
2,3,4,5,7
3,4
Step 3: Create collections of strongly connected
subgraphs（強連結部分グラフの集合を作成）
Collection（集合） A: 
3,4
Collection（集合） B:
2,3,4,5,6,7
2,3,4,5,7
Step 4: Create a collection graph（集合グラフを作成）
B → A
Step 5: Analyze the longest path in collection
graph（集合グラフにおける最長の経路を解析）
Collection（集合） A: 1
Collection（集合） B: 0
Step 6: Sort collections（集合をソート）
Collection（集合） B: 0
Collection（集合） A: 1
Step 7: Assign time complexity（時間計算量を割り当て）
1: 0
2: 1
3: 2
4: 2
5: 1
6: 1
7: 1
8: 0
Step 8: Interpret time complexity（時間計算量を置き換え）
1: O(1)
2: O(n)
3: O(n2)
4: O(n2)
5: O(n)
6: O(n)
7: O(n)
8: O(1)
Example assembly program（アセンブリプログラム例） #2
1: Do work（実行）
2: Conditionally branch to line 1（条件付きで行１に分岐）
3: Conditionally branch to line 1（条件付きで行１に分岐）
4: Do work（実行）
Step 1: Create a code flow graph（コードのフローグラフを作成）
1 → 2
2 → 3, 2 → 1
3 → 4, 3 → 1
4 → null
Step 2: Identify strongly connected subgraphs（各強連結部分グラフを識別）
1
1,2
1,2, (1)      Found
strongly connected subgraph（強連結部分グラフを発見）: 1,2
1,2,3
1,2,3, (1)    Found strongly
connected subgraph（強連結部分グラフを発見）: 1,2,3
1,2,3,4
List of all strongly connected subgraphs（すべての強連結部分グラフのリスト）:
1,2
1,2,3
Step 3: Create collections of strongly connected
subgraphs（強連結部分グラフの集合を作成）
Step 3a: Collection（集合） A: 
1,2
1,2,3
Step 3b: Collection（集合） A:
1,2,3
Collection（集合） B:
1,2              (was
a subset of {1,2,3} in collection A)（集合Ａの｛１，２，３｝の部分集合だった）
Step 4: Create a collection graph（集合グラフを作成）
A → B
Step 5: Analyze the longest path in collection
graph（集合グラフにおける最長の経路を解析）
Collection（集合） A: 0
Collection（集合） B: 1
Step 6: Sort collections（集合をソート）
Collection（集合） A: 0
Collection（集合） B: 1
Step 7: Assign time complexity（時間計算量を割り当て）
1: 2
2: 2
3: 1
4: 0
Step 8: Interpret time complexity（時間計算量を置き換え）
1: O(n2)
2: O(n2)
3: O(n)
4: O(1)
Example assembly program（アセンブリプログラム例） #3
1: Conditionally branch to line 3（条件付きで行３に分岐）
2: Conditionally branch to line 4（条件付きで行４に分岐）
3: Conditionally branch to line 2（条件付きで行２に分岐）
4: Conditionally branch to line 3（条件付きで行３に分岐）
Step 1: Create a code flow graph（コードのフローグラフを作成）
1 → 2, 1 → 3
2 → 3, 2 → 4
3 → 4, 3 → 2
4 → 3, 4 → null
Step 2: Identify strongly connected subgraphs（各強連結部分グラフを識別）
1
1,3
1,3,2
1,3,2,4
1,3,2,4, (3)          Found strongly connected subgraph（強連結部分グラフを発見）: 3,2,4
1,3,2,
(3)            Found strongly connected subgraph（強連結部分グラフを発見）: 3,2
1,3,4
1,3,4, (3)         
Found strongly connected
subgraph（強連結部分グラフを発見）: 3,4
1,2
1,2,4
1,2,4,3
1,2,4,3,
(2)          Found strongly connected subgraph（強連結部分グラフを発見）: 2,4,3
1,2,4,3,
(4)          Found strongly
connected subgraph（強連結部分グラフを発見）: 4,3
1,2,3
1,2,3,
(2)            Found
strongly connected subgraph（強連結部分グラフを発見）: 2,3
1,2,3,4
1,2,3,4, (3)          Found
strongly connected subgraph（強連結部分グラフを発見）: 3,4
List of all strongly connected subgraphs
(eliminating any duplicates)（すべての強連結部分グラフのリスト（いかなる重複も除外））:
3,2,4
3,2
3,4
2,4,3
4,3
2,3
Step 3: Create collections of strongly connected
subgraphs（強連結部分グラフの集合を作成）
Step 3a:
Collection（集合） A: 
2,3
2,4,3
Collection（集合） B:
3,2
3,2,4
3,4
Collection（集合） C:
4,3
Step 3b:
Collection（集合） A: 
2,4,3
2,3
Collection（集合） B:
3,2,4
3,4
Collection（集合） C:
4,3
Collection（集合） D:
3,2           (was
a subset of {3,2,4} in collection B)（集合Ｂの｛３，２，４｝の部分集合だった）
Step 4: Create a collection graph（集合グラフを作成）
Step 4a:
A → B
B → C
A → D
B → A
B → C
B → D
C → D
Step 4c:
A → B, B → A       Break
both connections between A and B（ＡＢ間の両連結を非連結にする）
A → C
A → D
B → C
B → D
C → D
Step 5: Analyze the longest path in collection
graph（集合グラフにおける最長の経路を解析）
Collection（集合） A: 0
Collection（集合） B: 0
Collection（集合） C: 1
Collection（集合） D: 2
Step 6: Sort collections（集合をソート）
Collection（集合） A: 0
Collection（集合） B: 0
Collection（集合） C: 1
Collection（集合） D: 2
Step 7: Assign time complexity（時間計算量を割り当て）
1: 0
2: 3
3: 3
4: 2
Step 8: Interpret time complexity（時間計算量を置き換え）
1: O(1)
2: O(n3)
3: O(n3)
4: O(n2)
【００８７】
（時間計算量検出アルゴリズムの組み合わせ）
本願では、時間計算量を計算する２つの方法として、アップブランチ法および強連結部分グラフ法を開示した。これらの相違点に加えて長所と短所を一覧にして以下に示す。
・アップブランチ法では、アルゴリズムが行番号に基づいてグループ分けを行う性質上、実際にはコードの行が閉路の一部ではない可能性がある場合に、このコードの行の時間計算量が誤って大きく判断されることがある（アセンブリプログラム例Ｎｏ．４を参照）。
・アップブランチ法は控えめなものであり、コードの最初か最後の行が複数の閉路間で共有される場合には閉路を含むとは認識せず、ある閉路が行番号に関して他の閉路と部分的に重複する場合にも閉路を含むとは認識しない（アセンブリプログラム例Ｎｏ．５を参照）。
・強連結部分グラフ法は、ソースコードまたはアセンブリコードが実際には結果としてこの時間計算量とならない可能性がある場合でも、閉路を含むと積極的に認識する。これは分岐を行うコードの各行の実際の計算が解析されないことによる。これによっても時間計算量の精度が下がることになるため、Ｏ（ｌｏｇ  ｎ）等の計算量は得られない。
・強連結部分グラフ法では、コードの行の時間計算量が理論的に可能な時間計算量よりも小さく判断されることは決してないため、計算されるすべての時間計算量が最大値となる。
【００８８】
アップブランチ法による時間計算量アルゴリズムおよび強連結部分グラフ法による時間計算量アルゴリズムの上記の長所と短所を踏まえて、以下の方策を取ることが有利である。
・強連結部分グラフ法を用いて、理論的に可能な最悪時間計算量を決定する。
・コードの各行の最小時間計算量は、アップブランチ法と強連結部分グラフ法とのいずれかから選択する（アセンブリプログラム例Ｎｏ．４およびＮｏ．５を参照）。これにより、時間計算量を控えめに推定しつつ、アップブランチ法に存在する実際よりも大きい誤った時間計算量をいずれも除外する。
【００８９】
（その他の例）
時間計算量を計算する上に開示する２つの方法を用い、その結果を以下の２つのアセンブリプログラム例のために比較した。
Example assembly program（アセンブリプログラム例） #4
1: Conditionally branch to line 3（条件付きで行３に分岐）
2: Unconditionally branch to line 4 (this code
line is not in a cycle)（無条件で行４に分岐（このコードの行は閉路内にはない））
3: Conditionally branch to line 1（条件付きで行１に分岐）
4: Do work（実行）
Up Branch Method of computing time complexity（時間計算量を計算するアップブランチ法）:
1: O(n)
2: O(n)
3: O(n)
4: O(1)
Strongly Connected Subgraph Method of computing
time complexity（時間計算量を計算する強連結部分グラフ法）:
1: O(n)
2: O(1)
3: O(n)
4: O(1)
Minimum between each time complexity method
(conservative with no errors)（各時間計算量方法のうち最小値（控えめで誤りがない））
1: Min ((O(n), O(n)) = O(n)
2: Min ((O(1), O(n)) = O(1)
3: Min ((O(n), O(n)) = O(n)
4: Min ((O(1), O(1)) = O(1)
Example assembly program（アセンブリプログラム例） #5
1: Conditionally branch to line 3（条件付きで行３に分岐）
2: Unconditionally branch to line 5 (this code
line is not in a cycle)（無条件で行５に分岐（このコードの行は閉路内にはない））
3: Conditionally branch to line 1（条件付きで行１に分岐）
4: Conditionally branch to line 1（条件付きで行１に分岐）
5: Do work（実行）
Up Branch Method of computing time complexity（時間計算量を計算するアップブランチ法）:
1: O(n)
2: O(n)
3: O(n)
4: O(n)
5: O(1)
Strongly Connected Subgraph Method of computing
time complexity（時間計算量を計算する強連結部分グラフ法）:
1: O(n2)
2: O(1)
3: O(n2)
4: O(n)
5: O(1)
Minimum between each time complexity method
(conservative with no errors)（各時間計算量方法のうち最小値（控えめで誤りがない））
1: Min ((O(n), O(n2)) = O(n)
2: Min ((O(1), O(n)) = O(1)
3: Min ((O(n), O(n2)) = O(n)
4: Min ((O(n), O(n)) = O(n)
4: Min ((O(1), O(1)) = O(1)
【００９０】
図１１および図１２は、複雑なコードシーケンスと、アップブランチ法および強連結部分グラフ法をそれぞれ用いて得られた対応する時間計算量の解析結果との一例を示す。より具体的には、図１１は、コードシーケンスと、アップブランチ法を用いて得られたこのコードシーケンスの時間計算量との一例を示す。図１２は、全く同じコードシーケンスと、強連結部分グラフ法を用いて得られた時間計算量の結果とを示す。図１１および図１２で分かるように、これらの２つの方法は性質や閉路検出のアプローチ等が異なるため、一部のコードの行の時間計算量の尺度についての値が異なる。したがって、上述のように、コードの各行の最小時間計算量の尺度をアップブランチ法と強連結部分グラフ法とのいずれかから選択することで、２つの方法を組み合わせればよい。これを図１３に示す。これにより、時間計算量を控えめに推定したものを表し、アップブランチ法に本質的に起因する実際よりも大きい誤った時間計算量をいずれも除外する。
【００９１】
以下に、例示を目的とする非限定のアルゴリズムの実施の一例を追加説明する。
【００９２】
分岐機械命令行から分岐先の機械命令行に伸びるグラフィカルな矢印であって、
ａ．複数の下向きの分岐がマシンコードの左側に現れ、
ｉ．分岐の元となる行における、ｉｉに接続する横線と、
ｉｉ．横線から分岐先の命令行まで下向きに進行する、ｉｉｉに接続する縦線と、
ｉｉｉ．分岐の分岐先における、分岐先の命令を指す右向き矢印を有する横線とから成り、
ｂ．複数の上向きの分岐がマシンコードの右側に現れ、
ｉ．分岐の元となる行における、ｉｉに接続する横線と、
ｉｉ．横線から分岐先の命令行まで上向きに進行する、ｉｉｉに接続する縦線と、
ｉｉｉ．分岐の分岐先における、分岐先の命令を指す左向き矢印を有する横線とから成り、
ｃ．互いの比較的近くに下向きおよび上向きに分岐する交互配置の機械命令が存在する場合に、下向きおよび上向きの分岐を組み合わせて反時計回りのフローを形成し、
ｄ．共通の分岐先を共有する分岐は、任意でそれらの縦線が互いに重なるように描かれ、
ｅ．共通の分岐先を共有しない分岐は、それらの縦線が互いに重ならないように描かれ、
ｆ．より近い分岐先を有する分岐は、より遠い分岐先を有する分岐よりもコードに近く位置する縦線を有するべきであり、
ｇ．他の関数に結合する分岐は、命令の右に向かう単一の横方向の両矢印で表され、
ｈ．戻り分岐は、命令の右に向かう単一の横方向の右向き矢印で表される、グラフィカルな矢印。
【００９３】
分岐機械命令に続く機械命令はそれらが分岐命令の分岐先でない限り、以下のアルゴリズムに従ってタブ１つ字下げされる。
ａ．すべての機械命令を字下げレベルがゼロとなるように初期化する。
ｂ．機械命令のリストを最初から最後までたどる。
ｃ．分岐機械命令に遭遇した場合、以下を実行する。
ｉ．分岐が下向きの場合、その分岐先にフリーズトークンでマーク付けする。
ｉｉ．各行の字下げレベルをインクリメントしながら一連の機械命令をたどる。
ｉｉｉ．フリーズトークンに遭遇した場合、その行の字下げレベルはインクリメントせず、ステップｃを停止し、ステップｂを続行する。
【００９４】
コンピュータの時間計算量はコードの重要な特性であり、コードのブロックをそれぞれ対応する時間計算量で視覚的に示すことで視覚化できる。関数内のすべてのマシンコード命令の時間計算量は、ゼロ＝Ｏ（１）、１＝Ｏ（ｎ）、２＝Ｏ（ｎ２）、３＝Ｏ（ｎ３）等として、以下のアップブランチアルゴリズムによって決定できる。
ａ．すべてのマシンコード命令を時間計算量がゼロとなるように初期化する。
ｂ．複数の前の命令に分岐するすべての条件分岐または無条件分岐のリストを構築する。
ｃ．すべての前への分岐のリストを、スキップするマシンコード命令の数が小さい方から大きい方へソートする。
ｄ．すべての前への分岐のリストをループする。
ｉ．この分岐について、分岐が１の時間計算量を表すとして分岐が表せる最大時間計算量を求める。
ｉｉ．分岐の分岐先から開始してマシンコード分岐自体で終了するまですべてのマシンコード命令をループする。
ａ．この分岐が表す最大時間計算量がこのマシンコード命令に関する前に記憶された時間計算量よりも大きい場合、この分岐が表す最大時間計算量をこのマシンコード命令に関する新たな時間計算量として記憶する。
【００９５】
以下のアルゴリズムは、初期的な計算量（明細書の後に記載する疑似コード）を与えられると、ある分岐に関する最大時間計算量を決定できる。
ａ．前の命令に分岐するすべての条件分岐または無条件分岐のリストが与えられると、スキップするマシンコード命令の数が小さい方から大きい方へソートする。
ｂ．当該分岐について、この分岐よりもスキップする命令の数が多いすべての分岐をループする。
ｉ．当該分岐がこの反復で検討中の分岐内に完全に含まれる場合、
ａ．計算量は、現在の計算量とこの反復で検討中の分岐の計算量とのうち量が大きい方に等しい（このアルゴリズムを現在の計算量とともに再帰的に呼び出すことで決定される）。
ｃ．計算量を返す。
【００９６】
アップブランチ法によるマーク付け時間計算量アルゴリズムのソースコードの一例を以下に示す。
【表１】
0005481571.tif 000002
【００９７】
上に開示する手法を用いてマシンコードまたはアセンブリコードを視覚的に変換することにより、例えばプログラマ等のユーザによる見直しや理解がより容易となり、場合によっては速度向上を目的として修正もできる。これらの方法はあらゆる種類のコンパイラが作成するマシンコードにおいて使用でき、開示する方法はコンピュータに限定されず、計算能力を有するあらゆる種類のマシンと連動して使用できる。
【００９８】
例示を目的とする非限定の実施の例に関して本明細書の技術を説明してきたが、本発明はこの開示に限定されるものではない。本発明は、特許請求の範囲によって定義され、本明細書が具体的に開示するか否かにかかわらずすべての対応する構成および等価な構成を対象とすることが意図される。
【図１】
0005481571.tif 000003
【図２】
0005481571.tif 000004
【図３】
0005481571.tif 000005
【図４】
0005481571.tif 000006
【図５】
0005481571.tif 000007
【図６】
0005481571.tif 000008
【図７】
0005481571.tif 000009
【図８】
0005481571.tif 000010
【図９】
0005481571.tif 000011
【図１０】
0005481571.tif 000012
【図１１】
0005481571.tif 000013
【図１２】
0005481571.tif 000014
【図１３】
0005481571.tif 000015