[發明專利]在數據處理系統中對計算機指令執行排序的方法和裝置

無效

• 申請號: 97104233.0
• 申請日: 1997-05-09
• 公開（公告）號: CN1176426A
• 公開（公告）日: 1998-03-18
• 發明（設計）人: 小毛里西奧·布雷特尼茲;羅杰·A·史密斯
• 申請（專利權）人: 摩托羅拉公司
• 主分類號: G06F9/40
• 分類號: G06F9/40;G06F9/30
• 代理公司: 中原信達知識產權代理有限責任公司
• 代理人: 余朦

本發明涉及用于微處理器的編譯程序和簡化程序技術，特別是涉及對最佳數據處理器執行的指令排序。

圖1說明用于計算機程序的控制流程圖。在圖1的控制流程圖中，有十個計算機指令或十個代碼段(也稱為計算機代碼的基本程序塊)在有向圖中表示為節點″a″-″j″。圖1的十個節點標為″a″至″j″并對應于計算機代碼的十個不同基本程序塊。在圖1的控制流程圖中，在計算機程序的執行路徑中首先按時執行基本程序塊a中的計算機指令。由于基本程序塊″a″是從基本程序塊″j″回到基本程序塊″a″的反饋路徑或循環徑路的端點，基本程序塊a可以包含，例如一個while型循環指令、一個for型循環指令、一個重復指令、一個do循環指令、或類似的循環結構，或基本程序塊″j″可包含具有作為起始端的基本程序塊″a″的目的地址的轉移指令。

執行完基本程序塊″a″后，按序執行使得每當執行基本程序塊″a″后執行基本程序塊″b″，如圖1的控制流程圖所示。依據軟件條件，執行基本程序塊″b″之后，執行流程將分裂到兩個方向之一。因此，基本程序塊″b″包含一個“如果-則-否則”指令或一個包括向下轉移到兩個相異和不同執行流程路徑的類似流程結構。如果在基本程序塊″b″中檢測到一個條件或限定集合，則執行基本程序塊c。如果確定基本程序塊″b″中存在另一個條件或限定集合，則執行基本程序塊d。在任何一種情況下，如圖1所示，每當執行完″b″之后執行″c″或″d″之一?；境绦驂K″c″和″d″以與如果-則-否則流程控制相似的方式匯合回到基本程序塊″e″。換句話說，執行完″c″或″d″之一后，將執行基本程序塊″e″中包含的代碼。

執行流程從圖1的有向圖中的基本程序塊″e″或節點″e″繼續，以便執行基本程序塊″f″。圖1的基本程序塊″f″、″g″、″h″和″i″與上面討論的基本程序塊″b″、″c″、″d″和″e″的結構非常相似，并因此以相似或相同的執行流程方式執行這兩組基本程序塊。一旦作為如上所討論的循環結束點的基本程序塊″j″通過圖1的節點確定不再需要進行循環，計算機程序的執行流程則從節點″j″經出口路徑退出圖1的結構。

可分析圖1計算機程序的執行流程以確定計算機基本程序塊在存儲器中的有效重排，以便以有效方式執行軟件。為此，圖2說明執行一執行跟蹤程序以收集來自圖1中圖示說明的計算機程序執行的數據。該跟蹤處理在存儲器中生成一個跟蹤數據文件。圖2所示的跟蹤數據文件記錄圖示說明的計算機程序按時間順序的執行流程作為如圖1中代碼的基本程序塊。跟蹤數據按時間順序方式存儲程序塊執行次序。在圖2中使用空格(“”)以便將循環a-j的不同執行通路相互分開。

因此，為生成圖2中的跟蹤文件，首先生成一個空跟蹤數據文件并開始執行基本程序塊a-j。在自基本程序塊a至j的第一循環中按時間順序的次序執行的基本程序塊為abcefgij。因此，在第一循環中，圖2左手側記錄的是采用圖1中的b-c通路和采用圖1中的f-g通路，從而形成按時間順序的次序執行程序塊abcefgij?；境绦驂K″j″將執行流程指回到基本程序塊″a″，圖2中的第二循環順序為abcefgij。因此，經從基本程序塊″j″到基本程序塊″a″的循環按時間順序連續將從左到右為abcefgij的同一指令順序執行兩次。該按時間順序的執行流程被連續記錄一個周期的時間并存儲在跟蹤數據文件中，以便以后的時間進一步分析。

然后計算機通過分析圖2的跟蹤數據能夠圖解地模擬如圖3所示的計算機軟件。指出在首先執行包含程序塊a-j的計算機程序以生成圖2中的跟蹤數據文件時，計算機不知道如圖1所示軟件的執行流程是很重要的。分析圖2的跟蹤文件以獲得與圖1包含相同信息的圖3的執行流程結構。