軟體事務性存儲器操作的優化的製作方法
2023-05-30 14:46:31
專利名稱：軟體事務性存儲器操作的優化的製作方法
軟體事務性存儲器操作的優化 相關申請的交叉引用
本申請要求2006年3月23日提交的美國專利申請第11/389,451號的優先 權，後者要求2005年12月7日提交的美國臨時申請第60/748,386號的優先權。
背景
多線程進程的多個線程在並發執行期間共享公共存儲器是常見的。因此， 多線程化進程的兩個不同線程必須讀取和更新可由程序訪問的同一存儲器位 置。然而，必須小心確保當一個線程正處於依賴於共享存儲器位置的值的操縱 序列中間時另 一個線程不會修改該值。
例如，假定一程序正在訪問兩個不同軟體對象的內容，其中每一對象表示 一不同銀行帳戶中的金錢數額。最初，第一帳戶的數額是$10，其存儲在存儲 器地址A1處，而第二帳戶的數額是$200，其存儲在存儲器地址A2處。銀行 程序的第一線程被編碼為將$100從A2轉移到Al,而第二線程被編碼為計算 兩個帳戶中的資金的總額。第一線程可通過向Al的內容增加$100而開始，從 而將其更新為$110，然後繼續從A2的內容中減去S100，從而將其更新為$100。 然而，如果第二線程在這兩個操作之間執行，則第二線程可對這兩個帳戶計算 出不正確的總額$310而非正確的總額$210。
軟體事務性存儲器提供了一編程抽象，通過該編程抽象，線程可安全地執 行一系列共享存儲器訪問，從而允許線程在沒有來自另一線程的幹擾的情況下 完成其事務。因此，事務性存儲器可在軟體中用於確保包括第一線程的示例性 加法和減法操作的事務關於存儲器位置Al和A2是"原子的"，且因此第二 線程將計算兩個帳戶的正確的總額。
然而，用於以軟體來實現事務性存儲器的現有方法遭受到性能問題。例如， 在一種現有方法中，當一線程在一事務內訪問一系列存儲器位置時，該線程維 護它希望在該事務期間讀取和更新(即，寫入)的存儲器位置和值的單獨列表，然後在該事務結束時，該線程更新實際共享存儲器位置處的所有這些值。如果 在該事務期間，該線程希望重新讀取或重新寫入其列表中的任何存儲器位置， 則該線程必須在列表中搜索該存儲器位置的條目以訪問該條目，這在程序上是 很慢的事情。因此，這一用軟體實現事務性存儲器的間接方法遭受較差的性能。 另外，用軟體實現事務性存儲器的現有方法引入了大量的開銷，包括對事 務性存儲器和記錄保持指令的不必要的調用，導致程序的執行受損，尤其是在 這些指令以低效的方式執行的情況下。另外，某些事務性存儲器方案中固有的 記錄保持活動不能有效地限制它們所創建的記錄的創建和維護，這會浪費存儲 器以及盤空間和其它系統資源。
概述
描述了一種軟體事務性存儲器系統("STM")。此處所描述的系統和技 術對軟體事務性存儲器指令執行優化以達到高效的性能。描述了一種編譯器， 它用軟體事務性存儲器指令來替換軟體事務性存儲器塊，並且進一步將這些指 令分解成分解的軟體事務性存儲器指令。該編譯器利用關於指令語義的知識來 執行在傳統的軟體事務性存儲器系統上不可得的優化。該編譯器另外對STM 代碼執行高級優化。執行這些優化中的某一些以便利用較低級優化。這些高級 優化包括不必要的讀一更新升級的移除、過程調用周圍的STM操作的移動、 以及對新分配的對象的不必要的操作的移除。另外，優化STM代碼以便為在 事務外部寫的存儲器訪問提供強原子性。
在一個示例中，在包括處理單元和用關於軟體事務性存儲器操作的知識來 配置的編譯器的計算機系統中描述了一種編譯包括軟體事務性存儲器塊的方 法。該方法包括優化程序以創建包含軟體事務性存儲器指令的經優化的程序， 以及編譯該經優化的程序。
提供本概述以便用簡化的形式介紹將在以下詳細描述中進一步描述的一 些概念。本概述並不旨在確定所要求保護的主題的關鍵特徵或必要特徵，也不 旨在用於幫助確定所要求保護的主題的範圍。
參考附圖，從以下各實施例的詳細描述中，將清楚其它特徵和優點。附圖簡述
圖1是用於編譯構成原子存儲器事務塊的原始碼的編譯器的框圖。 圖2是圖1的編譯器的組件的框圖。
圖3是示出使用事務性存儲器來編譯和執行程序的示例進程的流程圖。 圖4是示出由圖1的編譯器執行的用於用事務性存儲器來編譯程序的示例 進程的流程圖。
圖5是示出由圖1的編譯器執行的用於執行高級軟體事務性存儲器優化的
示例進程的流程圖。
圖6是示出由圖1的編譯器執行的用於在編譯期間優化分解的軟體事務性
存儲器指令的示例進程的流程圖。
圖7是示出由圖1的編譯器執行的用於引入實現強原子性的操作的示例進 程的流程圖。
圖8是示出由圖1的編譯器執行的用於移除讀一更新升級的示例過程的流 程圖。
圖9是示出由圖1的編譯器執行的用於移除讀一更新升級的另一示例進程 的流程圖。
圖IO是示出由圖1的編譯器執行的用於移動過程調用周圍的操作的示例 進程的流程圖。
圖11是示出由圖1的編譯器執行的用於移除對新分配的對象的日誌記錄
操作的示例進程的流程圖。
圖12是示出由圖1的編譯器執行的用於移除對新分配的對象的日誌記錄
操作的另一示例進程的流程圖。
圖13是包括在軟體事務性存儲器系統的運行時環境中在運行時期間使用
的軟體模塊的框圖。
圖14a和14b是示出使用多用途首部字的示例性對象的框圖。
圖15a和15b是示出具有改變的快照的示例性對象的框圖。
圖16是示出圖6的運行時環境的用於使用快照來確定對象的示例進程的
流程圖。
圖17是示出圖6的運行時環境的用於使用擴大的首部字來修改對象的快照的示例進程的流程圖。
圖18a和18b是示出事務執行的示例的框圖。 圖19a-19c是示出事務執行的其它示例的框圖。
圖20是示出在圖6的運行時環境中用於日誌過濾的示例結合表的框圖。
圖21是示出圖6的運行時環境的用於使用圖13的結合表來過濾日誌條目 的示例進程的流程圖。
圖22是示出圖6的運行時環境的用於使用圖13的結合表來過濾日誌條目 的另一示例進程的流程圖。
圖23是示出圖6的運行時環境所執行的用於在無用信息收集期間壓縮日 志的示例進程的流程圖。
圖24是示出圖6的運行時環境所執行的用於在無用信息收集期間壓縮日 志的另一示例進程的流程圖。
圖25是示出圖6的運行時環境所執行的用於在無用信息收集期間壓縮日 志的又一示例進程的流程圖。
圖26是用於實現此處的技術的合適的計算環境的框圖。
詳細描述
此處所示的示例描述了基於軟體和硬體的事務性存儲器系統，以及對這些 系統的性能改進。具體地，以下的實現示例描述了分解的軟體事務操作；使 用編譯器中間表示("IR")中的STM原語來允許代碼優化(其術語在以下 解釋)；用於改進這些原語的性能的編譯器改進；使用結合表的運行時日誌過 濾；以及高效的運行時按對象操作。儘管此處所提供的描述是作為對特定軟體 事務性存儲器操作實現的優化來提供的，但是可以認識到，此處所描述的技術 和系統可對各種實現操作，並且不一定暗示對此處所描述的技術的實現、性能 或要求的任何限制。
1.軟體事務性存儲器系統的示例
原子塊提供了對編寫並發程序的問題的有希望的簡化。在此處所描述的系 統中， 一代碼塊被標記為原子的，並且編譯器和運行時系統在該塊內提供那些表現為原子的操作，包括函數調用。程式設計師不再需要擔心手動鎖定、低級競爭 條件或死鎖。原子塊也可提供異常恢復，由此如果異常終止一個塊，則該塊的 副作用被回退。這甚至在單線程化應用中也是有價值的出錯處理代碼通常難 以編寫和測試。原子塊的實現縮放到大型多處理器機器，因為它們是並行性保 留的原子塊可並發地執行，只要一個塊中正被更新的位置不在任何其它塊中 被訪問。這保留了在常規的數據高速緩存中所允許的共享的種類。
此處所描述的技術參考了與編譯器和運行時系統緊密集成的STM實現。 該實現的一個特徵是它是直接更新STM。這允許直接在堆中更新對象而不是
在對象的私有陰影副本(shadow copy)上工作，或經由對象引用和當前對象內 容之間的額外的間接層次來更新。這對於成功提交的事務而言更高效。
此處所描述的系統和技術利用了該實現的提供分解的STM接口這一特 徵。例如，事務存儲obj.field = 42被拆分成以下步驟(a)記錄obj正被當前 線程更新，(b)將fidd所保持的舊的值記入日誌，以及(c)將新值42儲存到field 中。這一新設計允許向事務操作提供經典的優化。例如，本示例中的三個步驟 由編譯器單獨處理，並且(a)和(b)通常可以從循環中提升。在此處所描述的技術 中，通過使用具有關於STM接口和語義的知識並能夠執行被配置為在該接口 上起特別的作用的編譯器來使得分解的STM接口更高效。
在另一示例中，此處所描述的系統和技術示出了通過利用集成的事務性版 本化的高效的按對象操作而在所描述的STM實現中所獲得的效率。這些實現 使用了事務性版本化與現有的對象首部字的集成。這不同於其它STM系統， 因為這些系統或者使用版本化記錄的外部表、附加的首部字、或者使用對象引 用和當前對象內容之間的間接層次。這些方法導致不良的高速緩存局部性或增 加了空間使用。此處所描述的實現利用了擴大的首部字，以及允許在事務提交 期間對對象修改進行快速驗證的高效的快照指令。
此外，描述了運行時日誌過濾。該過濾是有用的，因為並非所有不必要的 STM操作都可在編譯時被靜態地標識。
在一個實現中，此處所描述的示例是在Bartok中實現的，Bartok是一種 用於公共中間語言(CIL)程序的優化提前研究編譯器和運行時系統，其具有 可與Microsoft .Net平臺相比的性能。該運行時系統可用包括無用信息收集器和該新STM的CIL來實現。 1.1語義
此處所描述的技術集中於原子塊的執行。各種實現可在確切的語義上有所 不同，包括原子塊與鎖定代碼的交互，以及在繼續利用這些技術的同時將I/O 操作與原子塊組合。
1.2設計假設
在此處所描述的示例中，關於如何使用原子塊作出了一些假設。這些並不 一定表示關於此處所描述的實現的限制，而是用於便於描述。
一個假設是大多數事務都是成功提交的。這是一個合理的假設，因為首先， 對並行化保留STM的使用意味著事務不會"自發"地或由於程式設計師不能理解 的衝突而異常中止(在替換實現中，衝突是基於散列值來檢測的，而散列值可 能會意外地衝突)。作為此一部分，假設由於高速緩存之間的過多數據移動的 成本程式設計師已經具有強烈的動機來避免競爭。諸如將高競爭操作移交給由單個 線程管理的工作隊列等技術保持有價值。
第二個假設是在原子塊中讀取比更新多。該假設是通過對當前程序的觀察
來證實的，並且試圖形成其事務性版本。這強調了將事務性讀取的開銷保持得 特別低的好處讀取僅涉及將正被讀取的對象的地址以及其首部字的內容記入 日誌。
最後一個假設是事務大小不應當被限定。這在建議STM實現需要隨著事 務長度的增長而良好地縮放的同時保留了複合性。在這一設計中，空間開銷隨 著事務中訪問的對象的數量而非隨著所作出的訪問數而增長。在此處所描述的 示例中，事務被非正式地稱為"短"或"長"。短事務可能在不需要STM的 任何存儲器分配的情況下運行。長事務是其執行可能會橫跨GC周期的那些事 務(例如，評估已被轉換成C弁的SEPC95基準xlisp版本的LSIP基準之一)。
1.3基於字的STM示例
用於基於字的STM的一種常規接口提供了以下兩組操作void TMStartO
void TMAbortO
bool TMCommitO
bool TMisvalidO
word TMRead(addr addr)
void TMwHte(addr addr， word value)
第一組用於管理事務TMStart啟動當前線程中的一個事務。TMAbort異 常中止當前線程的事務。TMCommit試圖提交當前線程的事務。如果事務不能 提交(例如，在一個實現中，由於一併發事務己經更新了其所訪問的位置之一)， 則TMCommit返回假，並且丟棄當前事務。否則，TMCommit返回真，並且 在該事務期間所作出的任何更新被原子地傳播到共享堆。TMIsValid若且唯若 當前線程的事務可在調用的時候提交時才返回真。第二組操作執行數據訪問 TMRead返回所指定的位置的當前值，或由TWWrite在當前事務中寫入的最新 近的值。
在此處所描述的技術的一個實現中，直接用STM來編程的過程通過使得 編譯器重寫原子塊中的存儲器訪問來使用STM操作，並使其生成所調用方法 的專門版本來確保TMRead和TMWrite被用於對在原子塊中作出的所有存儲 器訪問來自動化。
上述設計遭受限制其適用性的多個問題。以下代碼示例說明了這一點。以 下示出的示例la迭代通過標記節點this.Head和this.Tail之間的鍊表的各元素。 它將節點的Value欄位相加，並將結果存儲在this.Sum中。示例lb示出了自 動發出對所有存儲器訪問的TMRead和TMWrite的調用的一個示例。
然而，對於這一基於字的系統會出現若干性能問題。首先，TMRead和 TMWrite的許多實現使用在每一 TMRead和TMWrtie操作上搜索的事務曰志。 TMRead必須看見同一事務的更早期的存儲，因此它搜索保持試探更新的事務 日誌。這一搜索可能無法縮放以支持大型事務。性能取決於事務日誌的長度以 及輔助索引結構的有效性。其次，對STM庫的不透明調用阻礙了優化(例如， 不再可能從循環中提升讀取this.Tail，因為TMRead的行為對於編譯器是未知 的)。最後，單塊TM操作導致重複的工作。例如，在循環中訪問一欄位時的 重複搜索。1.4分解的直接訪問STM
在此處提供的示例中使用的分解的直接訪問STM實現解決了這些問題。 第一個問題是通過將系統設計成使得事務可直接對堆執行讀和寫操作來解決 的，從而使讀自然地看見前一事務存儲而無需任何搜索。仍需要日誌來回退異 常中止的事務並跟蹤關於所訪問的位置的版本化信息。對於短事務，這些曰志 是只能被追加的。由此，不論事務的大小如何，都不需要搜索。
第二個問題是通過在編譯的早期引入TM操作並擴展後續分析和優化階 段以使其知曉其語義來解決的。最後，第三個問題是通過將單塊TM操作分解 成分離的步驟以避免重複工作來解決的。例如，對事務日誌的管理與實際數據
訪問分開，這通常允許從循環中提升日誌管理。
該接口將事務性存儲器操作分解成四個組 tm一mgr DTMGetTMMgx
void DTMStaa:t (tm—mgr tx) void DTMAbort(tm一mgr tx) bool DTMCommit(tm一mgr tx) bool DTM工sValid(tm一mg2: tx》
void DTMOpeiaFor;Read(ttn一mg:r tx, object obj 〉 void DTMOpenForUpdate (tm—mgr tx, object ob j ) object DTMAddrToSurarogate (tm—mgr tx, addr addr)
void DTMLogFieldStore (tm—mgr tx,- object ob j , int offset) void DTM:L0gAdd2:St03:e(tmJSgr tx, acidr ob j )
前兩個組是直接的，提供了獲取當前線程的事務管理器的
DTMGetTMMgr，然後提供了普通的事務性管理操作。第三組提供了競爭檢測 DTMOpenForRead和DTMOpenForUpdate指示所指定的對象將以只讀模式訪 問，或者它隨後可被更新。對靜態欄位的訪問由代表靜態欄位來保持版本化信 息的代理對象調解DTMAddrToSurrogate將地址映射到其代理。最後一組維 護一撤消日誌，需要在異常中止時回退更新。DTMLogFieldStore處理對對象字 段的存儲，而DTMLogAddrStore處理對任何地址的存儲。
對這些操作的調用必須被正確定序以提供原子性。有三個規則(a)當讀 取一位置時，該位置必須被打開以供讀取，(b)當更新一位置或對該位置將存 儲記入日誌時必須打開該位置以供更新，(c)在更新一位置之前必須將該位置 的舊值記入日誌。在實踐中，這意味著對於一對象的欄位的TMRead的調用被 拆分成DTMGetTMMgr、 DTMOpenForRead的序列，然後是欄位讀取。對TMWrite的調用則被拆分成DTMGetTMMge 、 DTMOpenForUpdate 、 DTMLogAddrStore的序列，然後是欄位寫入。對靜態欄位的TMRead的調用 被拆分成DTMGetTMMgr、 DTMAddrToSurrogate、 DTMOpenForRead的序歹U， 然後是靜態欄位讀取。對TMWrite的調用則被拆分成DTMGetTMMgr、 DTMAddrToSurrogate、 DTMOpenForUpdate、 DTMLogAddrStore的序列，然後 是靜態欄位寫入。
以下示例展示了使用分解的直接訪問STM的一個示例。示例1中的代碼 迭代通過標誌節點this.Head和this.Tail之間的鍊表的各元素。它對節點的Value 欄位求和，並將結果儲存在this.Sum中。示例2示出了如何使用分解的直接訪 問STM來實現Sum (求和)。
示例la
public int Sum {
Node n = this.Head,, int t = 0; do {
t += n.Value;
if (n--this.Tail)
this. Sum = t,' return t,'
} while (true)
示例lb
public int Sum {
Node ii - TMRead (&this. Head),. int t =_ 0 do {
t += TMRead(&n.Value)
if (n==TMRead(&this.Tail))
TMWrite (&this.Sum, t) return t;
rx - TMRead(&ruNext); } while (true》
示例2public int Sum {
tm—mgr tx - DTMGetT剛gr DTOOpenForRead(tx, this)j Node n - this.head,* int t = 0; do {
DTMOpenForRead(tx, n》； t += n .Value DTMOpenForRead(tx, this) if (n-=this.Tail) {
DTMOpenForUpciate (tx, this);
DTML)OgFieldStore(tx, this, of f setof (List Sum)); this.Sum -return t,-
DTMOpenForReaLd(tx, n〉,'
} while (true》
2.編譯器優化
第2節描述了利用採用STM操作的知識來配置的編譯器對分解的STM操 作的優化。應當注意，如在本申請中所使用的，術語"優化"、"經優化的" 等是本領域中一般指在不參考任何特定改進程度的改進的術語。由此，在各種 情形中，儘管"優化"可以改進系統或技術的性能的一個或多個方面，但是它 並不一定要求該系統或技術的每一方面都被改進。另外，在各種情形中，"優 化"不一定意味著對任一方面的達到任何特定的最小或最大程度的改進。此外， 儘管"經優化的"系統或技術可能在一個或多個領域中顯示出性能改進，但是 它也可能在其它領域中顯示出性能降低。最後，儘管"優化"在某些情形中可 改進系統或技術的性能，它也可能在其它情形中降低性能。在以下描述的特定 環境中，儘管優化將導致冗餘的或多於的STM指令或日誌寫的移除，這可能 提供提高的性能，但是這些優化不應意味著將移除每一可能的冗餘或多於的指 令。
圖1是示出用於利用軟體事務性存儲器來創建經優化的程序120的編譯器 100的一個示例的框圖。在所示的示例中，編碼器100取原始碼110作為輸入。 如圖所示，原始碼110包含一個或多個原子塊115。如上所述，在一個實現中， 這些原子塊的包括避免了希望利用STM的程式設計師的額外編程；這些塊由編譯 器修改以包括分解的STM指令，這些指令然後被優化。儘管圖l示出了單一的一段原始碼，但是應當認識到，這僅僅是出於簡化說明的目的；此處所描述
的技術和系統也適用於一起編譯的多個原始碼文件，以及使用己經編譯好的代
碼的原始碼。另外，在各種實現中，使用不同的代碼語言，包括C++、 C#、 Java、 C以及其它語言；並且，在各種實現中，也可優化已解釋的語言。在所示的示 例中，這一優化是由被集成在編譯器中的STM優化150來提供的；該集成的 額外細節將在以下討論。在編譯和優化之後，產生利用軟體事務性存儲器的經 優化的程序120。這一經優化的程序的運行時操作的額外細節將在以下更詳細 討論。另外，儘管所示的實現示出在執行之前編譯成可執行文件，但是此處所 描述的技術的替換實現可剛好在執行之前或與執行並發地編譯和優化程序。
圖2是示出圖1的編譯器100的示例組件的框圖。圖2示出了通過編譯器 的示例操作路徑。儘管圖2單獨示出了特定的模塊，但是應當認識到，在各種 實現中，模塊可用各種組合來合併或劃分。該路徑始於第一編譯器模塊220， 該模塊接受原始碼110並從中創建中間表示230。在一個實現中，該IR取控制 流圖("CFG")的形式，這允許通過此處所描述的優化技術來容易地操縱它。
接著，優化模塊240修改IR 230以創建經優化的IR 250。在優化模塊240 的操作中，用低級和高級STM專用的優化來擴展傳統的編譯器優化。這種優 化的示例將在以下更詳細描述。最後，該經優化的IR 250由第二編譯器模塊 260優化成可執行代碼，諸如圖1的經優化的程序120。
圖3是用於使用STM來編譯和執行程序的示例進程300的流程圖。在各 種實現中，所示的進程框可被合併、劃分成子框、或省略。該進程始於框320， 在那裡接收包含事務性存儲器塊(諸如圖1的原子塊)的原始碼。在一個替換 實現中，原始碼可能不包含事務性存儲器塊，而是將包括單獨的軟體事務性存 儲器指令，諸如上述基於字的或分解的指令。接著，在框340處，將該原始碼 編譯成可執行程序。編譯的具體示例將在以下更詳細描述。最後，在框360處， 執行該可執行程序。
圖4是用於編譯結合了事務性存儲器塊的原始碼的示例進程400的流程 圖。進程400對應於圖3的框340。在各種實現中，所示的進程框可被合併、 劃分成子框、或省略。該進程始於框420處，在那裡編譯器100將軟體事務性 存儲器指令插入到每一原子塊中。在一個實現中，該插入是通過在該塊內的讀或寫的每一實例周圍插入正確的基於字的讀和寫STM指令來執行的。在另一
實現中，如果程式設計師決定插入其自己的STM指令，則框420的進程可被省略。 接著，在框440處，編譯器100用分解的指令來替換基於字的STM指令。 在一個實現中，如果編譯器接收到的原始碼包含已經分解的指令，則省略框440 的進程。另外，在某些實現中，特別是框420和440的進程可被組合以響應於 接收到原子塊來插入分解的STM指令。以上示例2示出了在框440的進程的 操作之後一段代碼看上去會像什麼。
在框440的進程的另一實現中，編譯器還通過分解日誌操作來減少日誌管 理成本，從而允許將日誌管理工作的成本分攤到多個操作上。特別地，在一個 實現中，DTMOpeW和DTMLog^^操作以對當前數組中存在空間的檢查開始。 對於DTMOpenForRead,這是在該代碼的快速路徑版本中必須執行的唯一檢 査。為分攤這些檢查的成本，編譯器利用了一個新的操作EnsureLogMemory, 該操作取指示在給定日誌中保留多少槽的整數。DTMOpeW和DTMLog^^的專 門分解的版本因此可假設存在空間。為減少運行時的簿記，在一個實現中， EnsureLogMemory操作不是相加的兩個連續的操作保留所請求的最大值而非 總數。為簡明起見， 一個實現沒有進行在調用或返回邊沿之後需要保留的空間 的專門操作。在另一實現中，對每一基本塊內的調用之間的所有操作組合保留。 在另一實現中，使用後向分析來儘可能早地急切地保留空間，從而被迫在所有 的調用和循環首部處停止。這具有組合更多保留的優點，但是可能會在不需要 保留操作的路徑上引入保留操作。
在框460處，編譯器執行高級STM優化，包括對強原子性的操作的引入、 不必要的STM操作的移動和移除、以及對新分配的對象的日誌操作的移除。 該進程將在以下更詳細描述。最後，在框480處，優化該程序，包括STM指 令。儘管圖4的進程示出了高級優化之後的框460和480中的其它優化，並且 沒有示出優化的重複，但是在某些實現中，框460和480的進程或其子進程可 按與所示的不同的次序來執行，並且可被重複。重複的一個原因是某些優化可 能展示出對於其它優化的機會。由此，可能希望重複地執行優化以便利用它們 可能引發的機會。
圖5是用於對STM指令執行高級優化的示例進程500的流程圖。進程500對應於圖4的框460。在各種實現中，所示的進程框可被合併、劃分成子框、
或省略。在一個實現中，進程500在以下描述的進程600的編譯器優化之前執 行，以使高級優化所增加的操作可被編譯器進一步優化。該進程在框520處開 始，其中編譯器引入對強原子性的操作。接著，在框540處，用打開來更新
(open-for-update)操作替換打開對象以供讀取的操作及其後的打開同一對象 以供更新的操作，以便允許稍後在後續優化期間移除打開操作。在一個實現中， 這些打開來讀取操作及其後的打開來更新操作被稱為讀取一更新
(read-to-update)升級；框540的進程移除了這些升級。接著，在框560處， 移動過程調用周圍的分解的STM操作，以提供圖6的進程中的更大優化。最 後，在框580處，移除對於在將對象記入日誌的事務中新分配的對象的日誌記 錄操作以防止不必要的日誌操作調用。這些進程的每一個的具體示例將在以下 參考圖7-12來更詳細描述。
2.1對分解的代碼的編譯器優化
圖6是用於對STM執行執行優化的示例進程600的流程圖。進程600對 應於圖4的框480。在各種實現中，所示的進程框可被合併、劃分成子框、或 省略。另外，儘管所示的實現給出了其中每一動作被執行一次的示例，但是在 替換實現中，動作可被重複。由此，例如，以下描述的公共子表達式消除動作 可以在執行了代碼運動優化之後被執行第二次。儘管圖6未示出非STM指令 的優化，但是這是出於簡化說明而這樣做的，並非展示對此處所描述的進程的 任何限制。
該進程在框620處開始，在那裡對STM指令的修改創建約束。在一個實 現中，這些約束至少是對原子性的約束，這是基於調用序列的。由此，有三個 規則(a)當讀取一位置時該位置必須被打開以供讀取，(b)當更新一位置或對 其將一存儲記入日誌時必須打開該位置以供更新，(c)在一位置被更新之前該 位置的舊值必須被記入日誌。
這些規則可使用多種方法來實現。在一種方法中，編譯器通過各種家務管 理(housekeeping)措施在編譯期間跟蹤約束。由於這會迅速使編譯進程變復 雜，因此在另一實現中，可修改CFG以防止違反約束。 一種這樣的方法是使用STM指令之間的啞變量來引入數據依賴性，該STM指令通過形成用於指令
的觀輸出變量(變為用於後續指令的輸入變量)來強制實施調用次序。由此，
看上去像以下的IR (使用類屬指令) open一for一update (loc >; log—f or一update (loc) write (locf val》；
變為
dununyl = open—for—update (loc); dummy2 -r.log—for—updater (loc, dummyl》 write (loc, val, dummy2)
接著，在框640處，對STM指令執行公共子表達式消除("CSE")， 之後在框660處對指令執行冗餘加載一存儲消除，並在框680處執行代碼移動 優化。
在一個示例中，這些優化可對DTMGetTMMgr操作執行，因為它是恆定 的，且因此為CSE提供了機會。類似地，由於DTMOpenForRead 、 DTMOpenForUpdate 、 DTMAddrTo Surrogate和DTMLog承操作在事務內是冪等 的，因此它們符合CSE或代碼運動的條件。對此優化的一個約束是在一個實 現中，代碼運動不能擴展超過事務邊界。在另一實現中，擴展CSE以提供對 在DTMOpenForUpdate之後發生的DTMOpenForRead的消除。該優化可被執 行是因為更新訪問包含了讀訪問。
在其它實現中，可對嵌套事務之間的操作執行CSE。由此，在一個示例中， 嵌套事務中的DTMOpenForRead被外部事務內DTMOpenForRead或 DTMOpenForUpdate包含，且由此可被消除。在另一示例中，嵌套事務中的 DTMOpenForUpdate被外部事務中的DTMOpenForUpdate包含，且被消除。
在另一實現中，DTMGetTMMge操作可通過從每一線程的Thread對象中 取出用於線程的當前事務管理器(並在必要時創建事務管理器)來實現。Bartok 編譯器因此可將GetCurrentThread指令作為服從代碼運動的常數操作來處理。
作為一個示例，在上述進程執行之後，示例2的代碼被簡化為以下更高效 的代碼
示例3public int Sum {
tm一mgi: - DTMGetTMMgr DTMOpenForRead(tx, this) 7 Node n - this,head; int t = do { -
DTMOpenForReaci(tx, n)
t += n. Value,'
if (n--this.Tail) {
DTMOpenForUpdate(tx DTMIiogFieldStore (t義 this.Sum = t/ return t,'
n = n, Next } while (true)
2.2高級STM優化
2.2.1實現強原子性
上述技術可用於構建"原子塊"，其中一個原子塊中的存儲器訪問相對於 第二原子塊中的訪問不可分割地發生。然而，由一個線程執行的"原子"塊在 第二個線程執行衝突的存儲器訪問而沒有使用"原子"塊時可能看上去並不是 不可分割地執行的。具有這一特徵的設計可被認為是提供了 "弱原子性"。
此處所描述的技術的一個實現涉及如何提供"強原子性"，其中原子塊看 上去相對於所有存儲器訪問都是不可分割地執行的，而非僅僅是那些在其它原 子塊中作出的存儲器訪問。
一個基本實現擴展了上述STM，其通過(a)標識發生在任何原子塊外部的 對共享存儲器的所有訪問，(b)將這些訪問重寫為短原子塊，而具有對強原子性 的支持。
例如，假定一程序從欄位"ol.x"的內容中讀取，並將結果儲存在欄位"02.x" 中。這最初由編譯器中間表示(IR)的兩個指令來表示
tl = getfield(ol) 1j2:
putfield(o2, tl)
基本實現將這些擴展為諸如以下的代碼
,this);
,this, offsetof(List.Sum));Ij1:
DTMStart(tm) DTMOpenForReaci (tin, ol) tl = getfield(ol) DTMCommit(tm》// CI L2:
DTMStart(tm)
DTMOpenForUpdate(tm, o2) logfield(o2) putf ield cx>《o2, tl) DTMCommit(tm) 〉/ C2
(在某些實現中，所編寫的實際代碼更複雜，因為如果在提交操作ci或
C2期間有競爭，則它還必須包括從L1到L2的重新執行事務的代碼路徑。該 代碼的確切細節將取決於如何在IR中表示STM操作而變化。)
該基本形式將提供強原子性，但是由於附加的事務啟動、事務提交、打開 來讀取、打開來更新、以及日誌操作的成本超過了原始欄位訪問的成本，因此 其執行不良。
為提高效率同時仍提供強原子性實現，此處所描述的技術的一個實現使用 了專門的IR操作來加速僅訪問單個存儲器位置的短事務的執行。
有兩種情況要考慮從單個位置讀取的事務，以及更新單個位置的事務(包 括對單個位置執行讀取一修改一寫入操作的事務)。這兩種情況都涉及對STM
字的檢查，這將在以下更詳細描述。第一種情況在擴展的IR中通過(a)為所涉 及的對象讀取STM字，(b)讀取欄位，(c)重新讀取STM字，並檢査所讀取 的值匹配(a)中的值並且該值不表明存在並發衝突訪問來表示。第二種情況在擴 展的IR中通過(a)更新事務更新，(b)更新欄位，(c)再次更新STM字，表明 它不再服從非事務性更新來表示。
由此， 一個示例IR看上去如下
LI: ,
sl = openoneobjforxead(ol)
tl = getfieldoc:> (ol)
if (!checkoneobj(ol, sl)) goto LI
L2 :
s2 - openoneobjforupdate(o2) putfield(o2, tl) commitoneobj(o2, s2)
該實現涉及與上述STM實現的兩個區別。第一個區別是，不像上述STM 實現，臨時存儲是在局部變量而非事務日誌中找到的。這意味著變量可以在處 理器寄存器中分配以使其訪問變得更快。第二個區別是在L2處開始的事務不 能異常中止，因此無需將在"o2.x"中蓋寫的值記入日誌。 23此無需在其周圍插入強原子性操作。
圖7是用於引入實現強原子性的操作的示例進程700的流程圖。進程700 對應於圖5的框520。在各種實現中，所述進程框可被合併、劃分成子框、或 省略。該進程在框720處開始，在那裡執行類型分析以確定在原子塊中可訪問 的欄位。如上所述，在一個實現中，執行這一步以避免針對不能引起衝突的存 儲器訪問的不必要的強原子性操作插入。接著，在框720處，使用在框710中 確定的欄位，來定位程序中可訪問包含在原子塊中的欄位的存儲器訪問。在一 個替換實現中，框710的進程可被省略，並且框720的進程可定位原子塊外部 的每一存儲器訪問來插入強原子性操作。
接著，該進程繼續到判定框725，在那裡編譯器確定在框720中定位的訪 問是讀取還是更新訪問。如果該訪問是讀取，則該進程繼續到框730，在那裡 在該訪問之前插入一打開來讀取指令。在一個實現中，該指令被配置成阻斷直 到它能夠接收STM字，且因此確保該存儲器訪問可正確地讀取所訪問的欄位。 在另一實現中，該操作不阻斷，但是如果存儲器訪問沒有檢驗出結束，則在存 儲器訪問之後創建一循環。接著，在框740處，在存儲器訪問之後插入一檢驗 指令，以確保在讀訪問的過程中STM字沒有表明對所讀取的欄位的改變。在 以上提供的實現中，這是通過在框730處接收STM字並在框740處將該STM 字傳遞到檢驗操作來完成的；這還創建了數據依賴性，它防止代碼優化對強原 子性操作的次序重新排序。
然而，如果框725確定訪問是更新，則該進程繼續到框750，在那裡在該 訪問之前插入打開來更新指令。在一個實現中，該指令被配置成修改來自所訪 問的對象的STM字，以防止其它訪問，由此提供強原子性。接著，在框760 處，在存儲器訪問之後插入提交指令以提交在存儲器訪問時執行的更新。在一 個實現中，改變所訪問對象的版本號。在另一實現中，不改變版本號。接著， 在判定框765處，編譯器確定是否有另外的非原子存儲器訪問。如果有，則該 進程重複。如果沒有，則該進程結束。STM編譯器的各種實現執行的另一高級優化是避免當DTMOpenForRead 操作之後有DTMOpenForUpdate操作時發生的不必要的日誌記錄。此處所描述 的技術固有的一個設計假設是讀比寫更常見，這就是這些技術使用分開的 DTMOpenForUpdate和DTMOpenForRead操作的原因；打開來讀取指令能夠更
快地完成。然而，有時候讀取對象然後寫入對象(規範的示例是"01^^1(1++")。
在這一情況中，帶有打開操作的IR看上去如下
DTMOpenForRead (obj》 t = pbj,field; t: - t+l;
DTMOpenForUpdate (obj)
DTMLogFieldStore (obj , of fsetof (obj . field) ) obj , field = t,'
如果程序到達打開來讀取點，則可以看到，它將到達打開來更新點，從而 忽略了此時的異常。由於對同一對象的打開來更新包含了打開來讀取，因此打 開來讀取操作被 浪費了。這在一個實現中被稱為讀取一更新升級。僅僅在較早
期執行打開來更新操作將是更高效的 DTMOpenForUpdate (obj),' t = obj.field; t = t+1,'
DTMIiogFieldStore (obj , off setof (obj . field) ) obj.field = t;
由此，在一個實現中，編譯器在找到讀取一更新升級時移除它們。 一般而 言，這可由基本塊內的編譯器通過直接的數據流分析來執行，從而如果
DTMOpenForRead操作後跟有DTMOpenForUpadate,則升級DTMOpenForRead
操作。在另一一般的情況下，DTMOpenForUpdate操作只需被插入到所有非異 常路徑從中執行相同的DTMOpenForUpdate的所有基本塊的開頭處(而無需介 入對所涉及變量的存儲)。CSE然後試圖消除同一對象上的額外的 DTMOpenForUpdate操作以及任何後續DTMOpenForRead操作。
圖8用於移除不必要的讀取一更新升級的示例進程800的流程圖。進程 800對應於圖5的框540。在各種實現中，所示進程框可被合併、劃分成子框、 或省略。該進程在框810處開始，在那裡編譯器標識後面總是跟有對同一引用 的打開來更新操作的打開來讀取操作。注意，儘管此處的示例利用了對象指針， 但是所描述的用於消除不必要的讀取一更新升級的技術還實現對內部指針和靜態欄位的移除。編譯器需要確定打開操作是針對同一對象的(或在靜態欄位 的一個實現中，是針對代理對象的)。
在一個實現中，分析要求對象引用或內部指針是同一局部變量並且該變量 沒有在操作之間更新。儘管該實現會遺漏對賦值上的升級的移除，但是其它實
現也分析賦值。在另一實現中，通過對代理對象的打開操作來控制靜態欄位(或 變量)，這允許當單個代理對象控制所有靜態欄位時在兩個不同靜態欄位之間 移除升級。框810的進程的一個示例進程將在以下參考圖9來更詳細描述。
接著，在框820處，用對同一引用的打開來更新操作替換在框810處標識 的打開來讀取操作。然後，在框820處，移除冗餘的打開來更新操作。在一個 實現中，這並不是緊接著框820的進程來執行的，而是由對圖6描述的編譯器 優化，諸如CSE來執行的。
讀取一更新移除分析的第一示例性實現移除基本塊內的升級。由此，編譯 器査看整個程序中的每一基本塊，並對每一掃描找出打開來讀取操作。當找到 第一個操作時，編譯器向前掃描以查找對指向被打開的對象的變量的打開來更 新操作或賦值。如果打開來更新操作首先出現，則編譯器將打開來讀取轉換成 打開來更新操作，並刪除原始的打開來更新。如果該變量被更新，則放棄搜索。 在一個替換實現中，編譯器可從打開來更新操作開始向後掃描以搜索打開來讀 取操作。
圖9是用於移除所標識的總是被打開來更新操作包含的打開來讀取操作 的第二示例進程900的流程圖。進程900對應於圖8的框810。在各種實現中， 所示進程框可被合併、劃分成子框、或省略。
圖9的進程利用了標準的後向數據流分析。在該分析中，編譯器在每一程 序點處計算將來肯定會被打開來更新的對象集。在各種實現中，圖9的進程是 對程序中的每一基本塊執行的，或對基本塊的子集執行。該進程在框910處開 始，在那裡在基本塊邊界處創建包含肯定會被更新的對象的指示的集合。在框 920處，將基本塊中的所有變量添加到該集合。然後，在框930處，對基本塊 中的指令的分析通過檢查該塊中的最後一條指令開始。在判定框935處，編譯 器考慮指令的形式。如果指令是賦值(例如，"x=...")，則在框940處，從該 集合中移除所賦值的變量。然而，如果指令是打開來更新指令，則在框950處，將由該指令打開的變量添加到該集合。
在任一情況下，或者如果指令是另一類型的，則編譯器移至判定框955， 在那裡它確定在基本塊內是否存在另外的指令。如果有，則在框960處，編譯 器在控制流圖上向後移動並找到該控制流圖中的下一指令且該進程重複。當編 譯器在判定框955處確定不再有指令時，到達了基本塊的開頭。當編譯器到達 該塊的開頭時，在框970處，它找出該塊的前導塊(即，可跳轉到當前塊的塊) 並將該集合與儲存在這些前導塊的每一個的末端的集合相交。在一個實現中， 重複圖9的進程，直到在給定每一塊的末端的當前集合時不再有任何東西改變。 編譯器可向後走查該塊，以用相同的方式更新該集合來獲得用於每一程序點的
隹A 朱PI o
此時，出於框810的目的，標識"必須在將來被打開來更新"集合中的變 量。然後，在一個實現中，對這些變量的每一個添加打開來更新操作，從而允 許CSE稍後移除額外的打開來更新操作。在另一實現中，使用局部冗餘性 ("PRE")來代替打開來更新指令及其後的CSE優化的漸進相加。這是更一 般的解決方案，並且可產生在相同路徑上具有更少打開指令的代碼。
在一個實現中，上述分析假設不會引發異常，因此忽略了異常邊，並在假 定沒有拋出異常的情況下計算將來肯定會被打開來更新的對象的集合。這是因 為異常不是常見的情況。這一精度損失不會影響正確性。然而，可擴展替換實 現以考慮異常邊，以便產生精確的結果。
另外，在替換實現中，以上分析可被修改成忽略其它代碼段。這可通過利 用表明忽略的代碼與被分析的代碼相比相對較不頻繁地執行的試探來完成。在 一個實現中，這些試探是靜態地確定的；在另一實現中，它們是從簡介信息確 定的。
作為一個示例，在執行了上述進程之後，示例3的代碼被簡化為以下更高 效的代碼 示例3.1public int Sum {
tm一mgr tx = DTMGetT醒gr DTMOpenForUpdate(tx, this),' Node n = this.head,' int t 0, do {
DT化OpenFo;rRead(t:x:, n)
t += ii .Value;
if (n--this.Tail) { .
DTMLo^FieldStore(tx, this, offsetof(List,Sum));
ttiis.Sum = t
return t;
} while (true》 -
2.2.3在存在過程調用的情況下移動操作
許多現有的編譯器優化只能比較、消除和移動函數內的代碼，因為這些技 術一般太過昂貴以至於無法應用於整個程序圖。然而，通過跨過程邊界移動 STM操作的高級STM優化，這些優化可更高效地執行。
作為一個示例，給定代碼
Foo(object obj) {
DTMOpenForU^date(obj ),
.} '.
Bar {
obj = .
DTMOpenForUpdate (obj ),' Foo (obj 〉
}
很清楚，Foo總是打開由其參數引用的對象來更新。Foo的調用者還可打 開該對象(如上所述)，或者它可在一循環(或多個其它東西)內調用Foo。 然而，該過程調用防止對具有調用者中的代碼的Foo的動作的分析/優化。該 優化跨調用界限移動打開操作以便為其它優化創建更多機會。CSE是一個明顯 的候選者，因為調用者可能已經完成了移動到它的操作。也可改進其它非事務 專用優化(例如，如果同一對象在一循環中被反覆傳遞給一函數，則可將打開 從該循環中提升出來)。
在一個示例中，該優化是對DTMGetTMMgr以及DTMOpenFo滻操作實現 的。在替換實現中，該優化可對如果調用一方法則必須被打開的其它操作執行 的。另外，在替換實現中，該優化可對在調用一方法時通常發生的其它操作執 行，這犧牲了非常見的情況下的精度和性能以換取常見情況下的更好性能，而
28非虛擬(也稱為"直接")調用執行 優化；這包括被"解除虛擬化"的虛擬調用(例如，確定僅單個調用目標存在 並用直接調用替換虛擬調用)。
圖10是用於通過跨方法邊界移動STM操作來優化STM操作的示例進程 1000的流程圖。進程1000對應於圖5的框560。在各種實現中，所示的進程 框可被合併、劃分成子框、或省略。該進程在框1010處開始，在那裡定位包 含可被移動到該方法之外的操作的方法。接著，在框1020處，克隆該方法以 創建該方法的允許該操作在該方法外部執行的版本。如果該操作給出結果，則 框1020的進程還向所克隆的方法添加自變量以使該結果可被傳遞到該方法。
接著，在框1030處，將該操作移動出所克隆的方法到用於該方法的一個 或多個調用地點。在替換實現中，在不移動操作的情況下創建所克隆的方法， 而非完全克隆該方法並移除操作。最後，在框1040處，用所克隆的方法來替 換對原始方法的調用。在所替換的調用的一個實現中，包括由所克隆的方法使 用的附加自變量。這些附加自變量的示例在以下示出。
在調用替換的另一實現中，編譯器維護它克隆的一組方法以及從這些方法 到其克隆(專門的)版本的映射。編譯器然後再次掃描程序中的所有方法來替 換調用。在某些情況下，該技術完全消除了原始版本的函數。然而，在某些情 況下，(例如，如果取該函數的地址)，則仍會有對非專門版本的調用並且該 調用不能被移除。
不同操作將導致方法以不同的方式來克隆。在一個示例中，如果一方法包 含GetTxMgr，則編譯器克隆該方法、添加一額外參數來接收事務管理器、並 用該參數來替換GetTxMgr的所有出現
FuncUsesMgr {
m = GetTxMgr(》；
} ….
-=> FuncUsesMgr^copy (TxMgr mgr) {
} …
在此示例中，對該方法的調用被改為對克隆的方法的調用，並具有包含事務管
理器的附加自變量Call
-=> mgr = GetTxMgr (》
FuncUsesMgr—copy (mgr)
在另一示例中，代替令單個特性跟蹤和創建基於(事務管理器)的專門克 隆，而是有許多(每一參數和每一靜態代理)。例如，
Foo(object objl, object obj2, object obj3) { DTMOpenForRead,(objl) DTMOpenForUpdSLte (obj 3) /
} …
在此示例中，編譯器可能希望創建期望調用者適當地打開objl和obj3(但 不必打開obj2)的專門版本。在一個實現中，這是通過執行上述作為框1010 的進程的一部分的"在將來某一點必須被打開來更新"分析來完成的。此處， 該分析僅跟蹤參數和靜態代理，但是還被擴展成完成"打開來讀取"以及"打 開來更新"操作。編譯器然後分析該函數的根處的集合。如果它們是非空的， 則編譯器如上所述克隆該方法，除了改為來回移動適當的打開操作之外。編譯 器在克隆的函數上儲存期望打開哪些參數(以及是用於讀取還是更新)以便使 其它優化能夠看見。
2.2.4減少對新分配的對象的日誌操作
最終的高級優化用於通過移除一事務中對在該事務內新分配的對象的日 志操作來減少日誌操作數量。具體地，不必為從來不用escape命令取消從中創 建它們的事務的對象維護撤消日誌信息。這是因為對於這一對象的撤消日誌中 的信息僅在該事務被異常中止時才使用，此時該對象無論如何都被刪除。
本質上，優化用於標識總是被綁定到自從事務開始以來分配的對象的變 量，然後刪除這些對象上的日誌操作。由此，圖11示出了用於移除對新分配 的對象的日誌操作的示例進程1100的流程圖。進程1100對應於圖5的框580。 在各種實現中，所示進程框可被合併、劃分成子框、或省略。
該進程在框1110處開始，在那裡編譯器標識總是被綁定到在其事務中新 分配的對象的變量。在各種實現中，執行框1110的進程以接收關於所編譯的 程序中的不同程序點集合處的變量的信息。由此，可執行框1110的分析以獲 知關於一特定點處的引用、 一小範圍的代碼、或通過事務內的整個變量生存期 的信息。在此分析後，在框1120處，編譯器移除通過這些變量操作的撤消日誌操 作，並且該進程結束。在一個實現中，編譯器通過用其分解不包括日誌操作的 特殊的擴展版本的操作替換訪問堆存儲器的STM操作來執行框1120的進程。 在另一實現中，編譯器在分解了 STM操作之後執行圖11的進程以明確地移除 分解的日誌操作。
框1110的進程的範圍從簡單到複雜，取決於所分析的代碼。在一個示例 中，諸如以下的代碼
atomic{
p - new _
} …
意味著P總是已知引用原子事務塊中的新分配的對象。由此，移除通過p來行 動的日誌操作是安全的。
然而，諸如以下的一段代碼 atomic{
if (...)
p = new _
P = q'.
} …
並不能夠容易地提供關於p是否總是引用新分配的對象的信息。由此，編譯器 必須執行分析來標識變量是否符合日誌移除的條件。
在一個實現中，編譯器使用在每一程序點處利用表明每一變量是否已知肯 定引用新分配的對象的向量的位向量。儘管該實現將正確地標識出對其可移除 日誌操作的引用，但是它一般較慢，並且涉及許多存儲器使用。在另一實現中， 位向量可提供關於一大段代碼，諸如基本塊的概要信息。該實現對於過程間分 析仍是較慢的。
作為替換，在一個實現中，編譯器使用了流敏感過程間分析來標識總是被
綁定到自從事務開始以來分配的對象的變量。圖12示出了這一示例進程1200 的流程圖。進程1200對應於圖11的框1110。在各種實現中，所示進程框可被 合併、劃分成子框、或省略。在所示的實現中，在事務中的每一基本塊上執行 進程1200。
圖12所示的進程是對整個程序的每一函數執行的，以便並發地構建並解析依賴性圖。對於每一函數，該進程在框1210處開始，在那裡創建從對象類
型化變量到依賴性圖中的點陣元素或節點的映射。該映射表示可被分配給塊中
的任一點處的變量的值的種類。在一個實現中，該點陣具有三個元素"舊"，
表示引用可能不是新分配的對象的變量；"新"，表示引用必須是新分配的對 象的變量；以及"未知"，用於對其沒有信息的變量。在框1220處，該映射 中的所有值被設為"未知"。接著，在框1230處，編譯器前向移動通過基本 塊以檢查該塊中的第一個操作。在判定框1235處，編譯器確定它正在檢查什 麼類型的操作。如果該操作是對象分配，則在框1240處，編譯器對於被分配 的變量向該映射添加"新"。如果該操作是賦值、強制類型轉換或過程調用， 則在框1250處，編譯器在變量之間傳播點陣值。由此，賦值和強制類型轉換 將其抽象值傳播到所分配到的變量。調用將抽象值傳播到調用形式並傳播來自 返回值的抽象值。然而，如果操作是除了以上情況之外的任何操作，則在框1260 處，修改該點陣以對於向其分配操作的變量表示"舊"。在一個實現中，該分 析還考慮在要新分配的當前事務的提交的子事務內分配的對象。
編譯器然後對從局部變量到點陣值或圖節點的映射前向傳播信息，並在函 數內迭代直到達到一固定點。由此，在判定框1265處，編譯器確定是否到達 諸如if語句的結束等連接點。如果已到達連接點，貝U在框1270處，將來自前 導塊的點陣值與用於當前塊的現有映射進行點級相交。出於分析的目的，函數 的開始被認為是從所有其調用地點開始的連接點。在任一情況下，該過程前進 到判定框1275，在那裡確定是否還有操作要檢查。如果有，則該進程在判定框 1235處重複。如果沒有，則該進程結束。該進程可導致傳播通過圖進入到來自 其它函數的變量。 一旦對事務中的每一基本塊執行了該進程，則已被標為"新" 的那些變量可將其日誌操作移除。在各種實現中，依賴性跟蹤意味著函數可以 按不同的順序來處理。它還意味著如果確定了一函數的新調用者或被調用者， 則無需第二次分析該函數。
3.運行時優化的示例
在本節中，描述分解的直接訪問STM的實現。總體上，事務使用嚴格的 兩階段鎖定來進行更新，並且記錄它讀取的對象的版本號以使其能檢測衝突的更新。對衝突或死鎖時的恢復使用回退日誌。 一種優化涉及擴展對象格式以支 持提交操作使用的版本號，以及用於基於該擴展來確定對一對象的改變的快速 技術。還描述了對事務性存儲器日誌的條目的運行時過濾。
3.1原子提交操作
對象結構的擴展可以在此處描述的STM實現中的原子提交操作的上下文 中理解。在原子提交的一個示例中，調用DTMStart，打開對象用於讀取和更 新，並且提交通過調用DTMCommit以試圖原子地執行這些訪問來結束。
內部地，提交操作通過試圖確認已被打開來讀取的對象來開始。這確保自 從這些對象被打開以來沒有其它操作對其作出了更新。如果確認失敗，則檢測 到衝突事務的更新被回退，並且關閉其打開來更新的對象，此時這些對象可 被其它事務打開。如果確認成功，則事務已在沒有衝突的情況下執行關閉它
打開來更新的對象，並保留更新。
確認進程檢查在從DTMOpenForRead命令的調用到確認的時間跨度期間 沒有對事務所讀取的對象的衝突更新。保持對象打開來更新防止在從 DTMOpenForUpdate命令的調用到STM日誌中對象的關閉的時間跨度期間的 衝突。結果，在這些時間跨度的交點沒有對任何打開的對象的衝突訪問；該事 務可被認為在確認開始之前是原子的。
3.2運行時環境
圖13是示出了可用於在運行時環境1300中在運行時期間優化STM性能 的對象和軟體模塊的示例的框圖。儘管圖13分開示出了特定的模塊，但是應 當認識到，在各種實現中，模塊可按各種組合來合併或劃分，或者可作為未示 出的其它運行時軟體結構的部分來操作。圖13示出了在運行時環境中操作的 對象1310，以及擴大的字首部1315。其字首部被擴大的對象的操作將在下一 節中描述。圖13還示出了讀確認模塊1320和對象更新關閉模塊1330，用於實 現如上所述的STM實現的確認和關閉過程。這些模塊對於運行時環境中的對 象的特定方面在此描述。圖13另外示出了過濾結合表1350，在某些實現中， 它過濾不必要的條目並防止其被記入到撤消日誌1360、更新對象日誌1370和讀對象日誌1380的各種組合中。這些過濾進程的具體實現將在以下更詳細描
述。最後，圖13示出了用於在對象在執行程序中不再可達到時解除其分配並 在無用信息收集期間壓縮STM日誌的無用信息收集模塊1390。該無用信息收 集模塊的具體實現在以下描述。
3.3對象結構
本節描述了用於支持只讀對象的確認以及對更新的對象的打開和關閉操 作的結構的示例。在一個實現中，STM出於對於對象的操作的目的而對每一 對象利用兩個抽象實體用於協調哪一事務已經打開了對象來更新的STM字， 以及在快速路徑代碼中用於檢測對事務所讀取的對象的衝突更新的STM快 照。使用這些數據結構的操作的示例如下
word GetSTMWor^(Object o)
:bool OpenSTMWord(Object o, word prev., word next) void CloseSTMWord(Object o, word next) snapshot GetSTMSnapshot(Object o) word SnapshotToWo:rd( snapshot s)
對象的STM字具有兩個欄位。 一個欄位是指示該對象當前是否被任何事 務打開來更新的單個比特。如果該比特被設置，則該字的其餘部分標識擁有的 事務。否則，該字的其餘部分保持一版本號。OpenSTMWord對STM字執行 原子比較並交換(compare-and-swap)(從prev (前 一 項)至(J next (下 一 項))。 CloseSTMWord將該字更新到一指定值。
圖14a和14b示出了實現對象中的STM字的示例。所示實現利用了Bartok 運行庫在存儲器中表示每一對象時將單個多用途首部字與該對象相關聯的事 實，用此來將同步鎖和散列碼(兩者都不是此處所描述的STM技術的組件) 與對象相關聯。在圖14a和14b中，該多用途首部字用一附加狀態來擴展，以 保持在事務中曾經被打開來更新的對象的STM字。由此，在圖14a中，對象 1400包括多用途首部字1410，它包括儲存在其中的值的類型的指示符1413， 之後是實際的STM字1418。對指示符1413的使用允許通過使用不同指示符 值來將多用途字用於散列碼和鎖。在一個實現中，假設如果用於一對象的指示 符指示該字中儲存了鎖或散列碼，則那時對於該對象尚沒有STM字。如圖14a 還示出的，STM字1418可以具有如上所述的兩種類型的值。在示例1420中， STM字包括指示對象1400沒有被打開來更新的比特，且因此該字的其餘部分保持一版本號。在示例1430中，STM字包括指示該對象被打開來更新的比特， 因此STM字標識了打開該對象來更新的事務。
在另一實現中，如果對於這些用途中的一個以上用途(例如，對於散列碼 和STM字)需要多用途字，則它被擴大，並且一外部結構保持該對象的鎖字、 散列碼和STM字。由此，在圖14b中，對象1450被示為使用擴大的首部字。 對象的多用途字的指示符1465包含了指示該首部字被擴大的值，而該多用途 字的其餘值1460包含被擴大的首部字結構的存儲器地址。由此，在圖14b中， 多用途字指向被擴大的首部字結構1470，這包括鎖字、散列碼和STM字。
與STM字形成對比，對象的STM快照提供了關於該對象的事務性狀態的 提示。在一個實現中，運行時環境確保只要在對象上調用CloseSTMWord—即， 只要一線程釋放對該對象的更新訪問一就改變快照。這提供了足以檢測衝突的
f曰息。
確保這一條件的一種方法是將STM快照實現為對象的多用途字的值。很 清楚，這一實現意味著當STM字被直接儲存在多用途字中時快照將改變。然 而，當使用擴大的首部字時它不一定要改變。在一個實現中，對於使用擴大的 首部字的對象的快照可以跟蹤並探査每一對象的擴大的首部字。然而，這是與 作出快速快照指令的目標不一致的低效的實現。由此，在另一實現中，如果多 用途字已被擴大，則CloseSTMWord創建新的擴大的結構，並將前一結構的內 容複製到該新的結構。這允許STM快照總是被實現為該對象的多用途字的值 同時保持快速。
圖15a和15b示出了 CloseSTMWord的這一實現的效果。在圖15a中，對 象1500被示為在CloseSTMWord的執行之前。對象1500使用擴大的首部字 1520，並將該擴大的首部字1520的地址儲存在其多用途首部字1510中。圖15b 示出了在執行CloseSTMWord之後對對象和運行時存儲器的改變。在執行之 後，創建了新的擴大的首部字數據結構1540，並且改變了儲存在多用途首部字 1510中的地址。這意味著包括多用途字1510的值的快照因關閉而改變。
圖16是用於使用對象快照來執行確認的示例進程1600的流程圖。在各種 實現中，所示的進程框可被合併、劃分成子框、或省略。該進程在框1620處 開始，在那裡對一對象記錄快照數據。在一個實現中，該記錄是在一對象被打開來讀取時執行的。接著，在框1640處，讀確認模塊1320在提交操作的確認 時刻記錄對該對象的第二快照。在判定框1660處，該模塊比較這兩個快照以 査看它們是否相同。如果它們匹配，則該進程繼續到框1670，在那裡允許事務 繼續提交/異常中止過程，這利用了快照未被改變來執行快速路徑測試的事實。 如果快照不匹配，則在框1680處，讀確認模塊1320執行不能利用匹配快照的 存在來確定事務是否能提交或異常中止的提交/異常中止過程，並且該進程結 束。在一個實現中，這兩組不同的過程被稱為快速路徑和慢速路徑過程。
框1670和1680的進程之間的關鍵差別是由於快照未被改變的知識，框 1670的進程可避免不必要的測試或存儲器訪問，並且可以比框1680的測試更 快地執行。在各種實現中，這些測試的確切特性可取決於底層的事務性存儲器 實現的特性。例如，在一個實現中，以下在代碼示例6中描述的執行兩個快照 匹配的確認的代碼只需檢査單個STM字來確定它是否被一事務擁有，並且該 事務是否與當前正在確認的事務相同。相反，當本示例中快照不匹配時，則必 須查找第二STM字，以及在某些情況下必須査找更新條目。在其上執行的這 些附加存儲器訪問以及附加比較意味著框1680的這一實現一般要比框1670的 對應實現慢。
圖17是用於修改使用擴大的首部字的對象的示例進程1700的流程圖。在 各種實現中，所示進程框可被合併、劃分成子框、或省略。該進程在框1720 處開始，在那裡修改對象。在一個實現中，這可能是由於STM更新指令而引 起的。在另一實現中，可修改對象的擴大的首部字本身，這可以或者是在鎖字 中，或者是在散列碼中。接著，在框1740處，對象更新關閉模塊1330響應於 關閉指令創建一新的擴大的首部字。該進程繼續到框1760，在那裡該模塊將信 息從舊的首部字複製到新的首部字。然後，在框1780處，對象更新關閉模塊 630修改該對象的多用途首部字以指向新的擴大的首部字。
最後，在框1790處，如果正發生無用信息收集，則將舊的擴大的首部字 留在原處，直到被無用信息收集器1390回收。對象更新關閉模塊完成這一步 以防止在一不同線程中對該對象作出第二改變並且第三擴大首部字被寫入到 從第一擴大首部字回收的存儲器中的情形。如果當一讀取該對象的事務打開時 發生這一情況，則該對象的快照可以看似為在提交時沒有改變，即使它被改變了兩次。這允許進行讀的事務在其應當由於對象的兩次修改而異常中止時能夠 提交。在一個實現中，框1790的進程是通過將對象留在原處直到回收對象是 安全的時候來執行的，在一個示例中這是在沒有事務打開了對象來讀取時完成 的。
4. STM日誌記錄和提交的示例 4.1 STM日誌結構的示例
每一線程具有帶三個日誌的單獨的事務管理器。讀對象日誌和更新對象日 志跟蹤該事務已打開來讀取或打開來更新的對象。撤消日誌跟蹤在異常中止時 必須被撤消的更新。所有日誌都是順序地寫入的，並且從不被搜索。使用單獨 的日誌是因為其中的條目具有不同的格式，並且因為在提交期間，系統需要輪 流在不同種類的條目上迭代。每一條目被組織成條目數組的列表，使得它們可 在不複製的情況下增長。
圖18a、 18b和19a-c使用示例2a的列表示例示出了日誌的結構。圖18a 示出了保持具有值10的單個節點的列表的初始狀態。假設對象的多用途字都 被用於保持STM字一在這一情況下對象在版本90和100下。在圖18a、 18b 和19a-c所示的示例中，STM字的右手邊的兩位值對應於圖14a、 14b、 15a和 15b的指示符。
示例3的一個操作打開this來更新，使用OpenSTMWord來用指向更新對 象日誌中的新條目的指針原子地替換版本號。偽代碼的一個示例如下示例4所 示
示例4
void DTMOpenPortJpdate (tm_mgr tx, object obj ) { word stm—word = GetSTMWord (obj )
if ( !IsOwnedSTMWord(stm—word) ) { entry - > obj = obj / entry -> stm—word = stin—word/ entry -> tx = tx,.
word new—stm—word = MakeOwnedSTMWord (entry) /
if (OpenSTMWord (obj , stm—word, new—stm一word) ) {
〃打開成功繼續到日誌中的卞一條目 —— entry ++, } else {
//打開失敗使得事務無效Becomelnvalid (tx)
} else if (GetOwnerFromSTMWord(stm_word) == tx) {
//已經由此事務打開來更新無需做其它、情 } else {
//己經由另一事務打開來更新
//變為無效 Becomelnvalid (tx)
圖18b示出了該結果。注意，在所示的實現中，"日誌組塊中的偏移量"欄位 在無用信息收集期間用作將進入日誌的內部指針(諸如來自圖18b中的List節 點的指針)映射到對保持它的日誌條目數組的引用的快速方法。
該列表相加示例繼而打開每一列表節點來讀取。DTM使得這一動作直接 對於每一對象，將對象引用及其當前STM快照記入日誌。示例5以偽代碼示 出了該動作的示例
示例5
void DTMOpenFo:rReaci(tm—mgr tx, object obj) { snapshot stm—snapshot = GetSTMSnapshot (obj ) entry -> obj - obj;
entry -> stm—snapshot = stm一snapshot ; entry ++;
}
圖19a示出了它所創建的日誌條目。在競爭較罕見的設計假設下，沒有試 圖檢測衝突，因此儘早發現衝突的好處不如檢査的成本重要。
在讀取了列表節點之後，最後一步是更新Sum欄位。DTMLogFieldStore 如圖19b所示用撤消日誌中的條目來記錄蓋寫的值。對此的偽代碼被省略一所 使用的具體記錄受到在一個實現中使用的Bartok系統中的無用信息收集支持 的影響；其它設計在其它系統中將是適當的。撤消日誌條目將被蓋寫的值的地 址記錄為(對象，偏移量)對。這避免了使用在某些無用信息收集器中進行處 理的較為昂貴的內部指針。條目也在標量或引用類型的存儲之間區分。這一類 型信息在某些無用信息收集器中是需要的。最後，它記錄蓋寫的值。在另一實 現中，可使用僅保持地址和被蓋寫的字的較短的兩字日誌條目，這是以無用信 息收集期間更多的工作為代價的。4.2提交過程的示例
在此處所描述的實現中對於DTMCommit有兩個階段第一個階段檢查對
於被打開來讀取的對象的衝突更新，第二個階段關閉被打開來更新的對象。無 需明確地關閉被打開來讀取的對象，因為該事實僅被記錄在線程專用事務曰志 中。
如下的示例6示出了 ValidateReadObject的結構。在該偽代碼中有大量情 況，但是如果被認為是按照DTM接口上的操作的條件情況的分離，則總體設 計更清楚。以下情況V1、 V2和V3指示沒有發生衝突
Vl —該對象在事務持續期間的任一點處未被打開來更新。
V2 —該對象在整個持續期間由當前事務打開來更新。
V3 —該對象最初沒有被打開來更新，並且當前事務是打開它來更新的
下一事務。
V4 —該對象在整個持續時間由另一事務打開來更新。
V5 —該對象最初沒有打開來更新，並且另一事務是打開它來更新的下
一事務。
這些情況在示例偽代碼中標出。 一些情況發生多次，因為在其中對由於實 際衝突而發生的STM快照失敗進行測試，以及其中在沒有衝突的情況下失敗 (例如，由於當對象的多用途字變為擴大時STM快照改變)的場合之間進行 區分是有用的。
示例6
void ValidateReadObject {tm—mgr tx, object obj, read—entry *entry) { snapshot old—snapshot = entry -> stm—snapshot snapshot cur—snapshot = GetSTMSnapshot (obj ) / word cur—stm—word = SnapshotToWord (cur—snapshot)
if (old—snapshot == curAsnapshot) { // '|￡照匹配沒有事務關閉該對象
if (!IsOwnedSTMWord(cur—stm—word) ) {
// VI: OK:快照未改變，—沒有>突 } else if (GetOwnerFromSTMWord(cur_stm—word) == tx) {
〃 V2: OK:在讀取前由當前tx打開_ —
//來更新 } else {
〃 V4 :由另一tx打開來更新BecomeInvalid(tx);
} else {
//快照失配STM字上的慢速路徑測試
word old—stm—word = SnapshotToWord (old—snapshot) if(!IsOwnedSTMWord (old—stm—word) ) { if (old—stin—word == cur—stm—word) {
〃 vl: ok! STM字在事務，月間一
//被擴大
} else if ( ! IsOwnedST麗ord(cur—stm—word) 〉 { 〃 V5 :另一tx的衝突更新—— Become Invalid (tx) } else if (GetOwnerFromSTMWorcl (cur—stm—word) == tx) { //當前tx打開該對象來更新... ——
update—entry *update—entry =
GetEntryFromSTMWord (cur—stm—word); if (update—entry -> stm—word !=
SnapshotToWord(old—snapshot) ) {
// V5 :...但是另一；x在當前tx打開該對象之前
//打開並關閉該對象來更新
〃
Becomelnvalid (tx),. } else {
〃 V3 : OK:沒有另一tx的介入的訪問
} else {
// V5 :該對象由另一事務打開 Becomelnvalid (tx)
}
} else if (GetOwnerTromSTMWord(cur—stm—was) == tx) {
〃 V2 : OK:在讀取之前由當前tx打開一來更薪 } else {
〃 V4 : STM字不變，但是先前由
//另一事務打開來更新 Becomelnvalid (tx)
示例7
-void CloseUpdatedObject (tm一mgr tx, object ob j , update—entry *entry) { 一 word old—stm—word - entry -> stm一word; word new—stm一word - GetNextVersion《old一stm—word) CloseST順ord(ot)j , new—word),'
} 一
圖19c示出了對該列表結構的所得的更新，其中新版本號91被放置在該 列表對象的首部。可以觀察到，隨著對版本號有29個比特可用，可以獲得大約500M的不 同版本。所示的設計對於版本號溢出是安全的，只要在一運行的事務打開對象 來讀取時一版本號在同一對象中不被重複使用一允許讀取事務成功提交而無 需檢測可能對該號碼有大約500M的更新的A-B-A問題。
對於正確性，在一個實現中，這是通過(a)至少每500M事務執行無用信 息收集一次，以及(b)在每次無用信息收集時確認運行的事務。讀取對象曰志 中的條目僅當所記入日誌的版本號匹配當前版本號時才有效結果是每次無用 信息收集"復位"500M事務的"時鐘"而無需訪問每一對象來更新其版本號。
5.運行時日誌過濾
本節描述了利用概率性散列方案來過濾來自讀取對象日誌和撤消日誌的 重複以便過濾重複的運行時技術。日誌過濾一般是有用的，這是因為a)日誌 可能佔據大量空間，從而耗盡系統資源，以及b) —旦將一特定存儲器位置記 入曰志為已被寫入或讀取，則無需進一步在日誌中記錄它。這是因為，在確認 期間，所需的來自讀取對象日誌的唯一信息是事務之前該對象的STM快照， 而所需的來自撤消日誌的唯一信息是在事務之前更新的存儲器位置的值。由於 這不在事務內改變，因此對每一事務一給定存儲器位置只需一個日誌條目。
在第4節的實現中，不必過濾更新對象日誌中的條目。這是因為 DTMOpenForUpdate不允許在同一事務內對同一更新的對象首部創建重複的日 志條目。在其它實現中，可能創建這種重複，並且因此可能過濾重複。
一般而言，過濾器支持兩個操作。第一個操作是"過濾"操作，它在指定 的字必須在過濾器中存在時返回真。如果指定的字可能在過濾器中不存在則返 回假，並在該字的確不存在時將該字添加到過濾器。這一過濾器因而擔當在搜 索時容許假否定的概率集(即，它可在字實際上在過濾器中存在時聲明該字不 在過濾器中，但是不能在字實際上不在過濾器中時聲明其在過濾器中)。第二 個操作是"清除"操作，它移除過濾器中所有的字。
在軟體事務性存儲器(STM)的上下文中，過濾器可用於減少相同字的內 容被寫入STM保持的事務日誌之一的次數。此處所描述的過濾方案使用結合表來概率性地檢測對讀取對象日誌和撤 消日誌的重複日誌記錄請求。儘管此處所描述的實現參考了散列表，但是可以 認識到，在替換實現中，過濾技術和系統可使用結合表的不同實現。 一種實現 使用了將地址的散列映射到與具有該散列的地址有關的最新近的日誌記錄操 作的細節的按線程表。
可以注意到，在一個實現中，只需一個結合表來同時過濾讀取對象日誌和 撤消日誌。對讀取對象日誌的存儲使用了該對象的首部字的地址，而對撤消日 志的存儲使用了所記入日誌的字的地址。由於這些地址集是不相交的，因此單 個表不會展示出讀取對象和更新訪問之間的衝突，且因此可用於兩個日誌。
圖20示出了該表的設計。圖20示出了被實現為散列表200的結合表。如 圖20所示，散列表2000中的每一條目包括存儲器地址2020和交易號2030。 條目是按照一系列槽號2010來組織的。
在一個實現中，標識用於一特定存儲器地址的槽號的散列碼通過將地址拆 分成散列索引和標籤來獲得。由此，在這一實現中，散列函數只需使用來自字 W的最低有效位中的幾位來選擇要在表中使用的槽S。字W中的位因此可被 認為被拆分成兩個部分最低有效位是散列碼，其用於標識要使用的槽，而其 餘的位用作唯一地標識地址的標籤。例如，字0x1000具有標籤l，槽0，而字 0x1001具有標籤1，槽1，字0x2000具有標籤2，槽0，字0x2001具有標籤2， 槽1等等。在替換實現中，使用不同的散列方案。
另外，儘管散列表2000將事務號示為與存儲器地址分離，但是在各種實 現中，事務號諸如使用異或(XOR)運算與存儲器地址組合。在一個實現中， 使用異或運算因為它是相對快速的運算，並且可以被連續的異或撤消。在替換 實現中，使用不同的記錄事務號的方法，諸如用事務號來替換存儲器地址中的 低序位，或使用加法運算而非異或運算。這些是有用的是因為它們各自共享了 這樣的性質對於散列成相同的散列碼的兩個地址a,和a2，以及兩個事務號^ 和t2，僅當ai=a2且t產t2時op(a!, t!)才等於op(a2， t2)。該性質提供了所插入的組 合值對於特定地址和從中創建它們的事務號是唯一的置信度。
使用對線程本地的事務號是要防止由較早的事務記錄的條目與涉及當前事務的條目混淆。事務號的標識允許僅當用於事務號序列的比特溢出時該表才 被清除。在一個實現中，該表在每次事務號序列溢出時被清除一次，這通過防 止從不同事務生成的兩個條目使用相同的事務號來避免了表中的衝突。在另一 實現中，對每一事務清除表中的一個槽；在某些實現中，對每一事務增加一小 的開銷相比增加一偶然的大開銷可能是較佳的。在其它實現中，較佳的是一次 執行所有的表清除。
圖21是用於過濾日誌條目的示例進程2100的流程圖。在各種實現中，所 示進程框可被合併、劃分成子框或省略。該進程在框2110處開始，在那裡在 當前事務的開頭更新事務計數。該計數提供了在散列表中使用的事務號。接著， 在判定框2115處，確定是否達到事務計數限制。在一個實現中，該限制是通 過分配給該計數的溢出比特數來確定的。在另一實現中，該限制可基於存儲器 限制或者可被選擇來細調散列表的性能。如果未達到限制，則在框2140處， 通過散列表來過濾要記入日誌的地址。相反，如果達到了該限制，則在框2120 處復位計數，並且在框2130處清除該表。然後，在框2140處，通過散列表來 過濾要記入日誌的地址。
圖22是用於過濾日誌條目的示例進程2200的流程圖。在各種實現中，所 示的進程框可被合併、劃分成子框、或省略。在各種實現中，進程2200對應 於進程2100的框2140的進程。進程2200在框2210處開始，在那裡對地址散 列以找出正確的散列表條目。接著，在框2220處，將要過濾的地址與當前事 務號(從事務計數中接收)進行異或。在一個實現中，如上所述地通過將地址 拆分成散列碼和標籤值來執行散列。
該進程然後前進到判定框2225，在那裡對照異或結果來檢査散列條目的 值。如果兩者匹配，則無需再次將存儲器訪問記入日誌，並且在框230處不向 日誌寫入。然而，如果兩者不匹配，則在框2240處將異或結果寫入散列表條 目，並且在框2250處將條目寫入日誌。
5.3對於新分配的對象的運行時日誌過濾
在一個實現中，此處所描述的STM系統和技術標識由當前事務分配的對 象來避免對其寫入任何撤消日誌條目。這在上述靜態編譯時分析遺漏或不能移除對於新分配的對象的特定日誌操作的情況下提供了備份。該運行時技術是安 全的，因為如果當前事務異常中止，則對象將死去。在一個實現中，這是使用
為新分配的對象上工作的專門化的版本的DTMOpenForUpdate，並通過使得該 操作寫入一指定的STM字值來將該對象標記為被事務性分配來完成的。
6.無用信息收集的示例
一般而言，無用信息收集("GC")提供了用於自動確定一存儲器對象 何時可因其不再被程序中的任何線程所需而被安全地解除分配的機制。無用信
息收集被結合到許多現代程式語言中，並形成了 Microsoft .NET框架的一部分。 本節描述了將GC集成到上述STM技術中的各種實現。然後，這一集成 並不是簡單的。為示出這一問題，考慮以下示例 stomic {
tl = new IjargeTemporaryObject , 〃計算E1
t2 = new LargeTemporaryObject / 〃計算E2
出於示例的目的，假設在El和E2處執行的計算都足夠複雜以使必須對 其完成GC而不耗盡存儲器。此外，假設綁定到tl的LargeTemporaryObject 僅在El中使用，類似地，綁定到t2的LargeTemporaryObject僅在E2中使用。 如果在沒有"原子"塊的情況下執行，則一旦E1完成，tl佔據的空間將被回 收。
本示例不能用現有的事務性存儲器系統和GC來執行。在這些系統中，將 發生以下兩個問題之一
1. 某些不知道TM的GC在發生GC時迫使所有存儲器事務異常中止。 在這些系統上，諸如El和E2等計算從不能在原子塊中執行。
2. 其它不知道TM的GC迫使對象保留比此處的知道TM的GC的對象 所保留的時間更長。在這些系統上，示例可成功執行，但是tl和t2將被保留 到原子塊的最後，即使GC在其間知道tl隨後不需要的E2期間發生。
在一個實現中，這些問題由知道TM的GC解決，該GC(a)允許GC在線 程正出於執行原子塊的中間的同時發生，以及(b)允許GC恢復可確保是程序不需要的對象，而不論原子塊是成功完成還是被重新執行。
在各種實現中，無用信息收集技術包括在用於標識在當前原子塊內分配的 對象的原子事務塊的實現中使用的技術。各實現還包括用於標識STM的數據
結構引用的哪些對象確保是程序不需要的技術。最後，GC實現包括用於標識 TM的數據結構中的哪些條目對於程序的將來執行是不需要的技術。
儘管以下描述特別地依賴於以上所描述的系統，但是此處描述的實現不限 於該設置；它們可用於其它形式的事務性存儲器，可能包括硬體事務性存儲器。
此處所描述的實現是參考令世界驚嘆的跟蹤無用信息收集器，例如標記一 清掃無用信息收集器或複製無用信息收集器來描述的。然而，這是出於展示簡 明的目的，並且各實現不限於該設置；可使用己知的方法來將STM與其它無 用信息收集技術，如世代無用信息收集、並發無用信息收集或並行無用信息收 集集成。在一個實現中，STM與世代無用信息收集集成。
在較高層次，在令世界驚嘆的跟蹤GC的操作可被概括為以下過程。首先， 停止應用程式中的所有應用程式線程(有時稱為"增變線程(mutatorthread)")。 接著，訪問增變線程最初用於訪問對象的每一個"根"，從而確保從這些根所 引用的對象在收集之後被保留。(根包括處理器的運行增變線程的保存寄存器 內容、線程的棧上的對象引用、以及這些線程可通過程序的靜態欄位來訪問的 對象引用)。因此，被保留的對象通常被稱為"灰色"，而其餘對象最初被稱 為"白色"。然後，對每一灰色對象，訪問它所包含的對象引用。這些引用所 標識的任何白色對象進而被標記為灰色，並且一旦訪問了灰色對象中的所有引 用，該對象被標記為黑色。重複此步驟，直到再沒有灰色對象。留下的任何白 色對象被認為是無用信息，並且可以使它們所佔據的空間可被增變線程用於重 新分配。最後，重啟增變線程。在以下示例中，灰色對象將被稱為"己訪問" 對象，而已知為白色的對象是"不可達的"。
在將STM與GC集成的一個實現中，當啟動GC時所有事務被異常中止。 這具有明顯的缺點。在另一實現中，GC將STM的數據結構認為是增變線程的 根的一部分，由此基於它們被日誌中的條目引用來訪問對象。在這一實現中， 從一些日誌中對對象的引用被認為是"強引用"，這需要GC保持存儲器可通 過它們達到。儘管此實現允許STM系統和GC之間的某種程度的集成，但是在另一實 現中，有較大程度的集成。圖23是示出由無用信息收集模塊1390執行的用於 在STM系統中執行無用信息收集的示例進程2300的流程圖。在各種實現中， 所示進程框可被合併、劃分成子框，或省略。在以下所示的過程中，GC能夠 使用STM的特殊知識來解除對象的分配並在不再可能使用它們時將條目記入 日誌，並且能夠通過移除冗餘條目來壓縮日誌。在一個實現中，圖23的進程 是代替以上訪問已訪問對象的每一對象引用的典型GC過程中的步驟來執行 的。在替換實現中，圖23的進程可以被集成到其它一般的GC過程中。
在某些實現中，圖23的進程識別STM系統中的日誌的兩種質量。第一種 質量是標識當前事務己在其上嘗試訪問的對象的日誌。這種日誌在各實現中包 括在PLDI論文中描述的實現中的對在讀取對象、更新對象和撤消日誌中訪問 的對象的引用。在一種術語中，從這些日誌對對象的某些引用被認為是"弱引 用"，意味著除了這些弱引用之外，GC將回收由不可達的對象使用的存儲器。 GC在執行該進程時識別的另一種質量是標識在提交或異常中止事務時將被恢 復到存儲器的對象引用的日誌。這種日誌包括撤消日誌中的舊值。從這些日誌 的這些引用在某些術語中被稱為"強引用"。如上所述，"強引用"要求GC 保持存儲器通過它們可達。
該進程在框2310處開始，在那裡GC模塊1390訪問由撤消日誌1360中 的每一條目的"先前值"欄位引用的對象，由此防止這些對象被認為是不可達 的，並且防止其在當前事務異常中止的情況下的回收。接著，在框2320處， 從日誌中移除某些特殊情況的條目。這一移除進程的一個示例在以下參考圖24 更詳細描述。
該進程繼續到框2325，在那裡GC模塊訪問每一已經訪問的對象包含的 對象引用，以訪問每一可達對象並得到最終的不可達對象集。然後，在框2330 處，GC模塊審閱讀取對象日誌13800中引用不可達對象的條目。在判定框2335 處，GC模塊對每一條目確定是否有對被該條目引用的對象的衝突並發訪問。 在一個實現中，GC通過對每一條目確定該條目中的版本號是否匹配對象的版 本號來完成這一步。如果是，則在框2350處只需從日誌中簡單地解除對該條 目的分配，因為該條目是最新的並且該對象是不可達的。然而，如果版本號不匹配，則當前事務無效。此時，GC模塊本身在框2340處使事務異常中止，從 而刪除關於該事務的所有日誌條目。在替換實現中，可省略框2335、 2340和 2350的特定檢査和處理，在不審閱的情況下從讀取對象日誌中解除己知為不可 達對象 的分配，並且依賴於STM的其它運行時系統來確定是否要使事務異常 中止。
接著，在框2360處，GC模塊審閱更新對象日誌1370中的條目，並解除 引用不可達對象的所有條目的分配。然後，在框2370處，對撤消日誌1360中 的條目執行相同的進程。最後，在框2380處，GC模塊進而解除所有剩餘的不 可達對象的分配。
擴展實現利用了從STM日誌中移除附加條目的特殊情況。圖24是示出由 無用信息收集模塊1390執行的用於移除特殊情況日誌條目的示例進程2400的 流程圖。圖24的進程對應於圖23的框2320。在各種實現中，所示的進程框可 被合併、劃分成子框、或省略。儘管此處的描述將這些擴展描述為作為進程2400 和框2320的進程的一部分的連續的步驟，但是將認識到，在某些環境中，圖 24的進程可彼此獨立地使用，並且在某些情況中，可獨立於基本實現(例如， 在除GC之外的其它時刻壓縮日誌)來使用，並且一快速實現可組合這些步驟 中的一個或多個的各部分來減少必須訪問日誌中的條目的次數。
進程2400在框2410處開始，在那裡如果僅有一個事務是活動的，則GC 模塊1390立即回退並從撤消日誌1360中移除引用不可達對象的條目。在框 2420處，GC模塊審閱讀取對象日誌1380和撤消日誌1360，並且如果條目引 用了在當前事務塊內創建的不可達對象則從這些日誌中移除條目。GC模塊 1390這樣做是因為如果對象是在事務開始之後分配的且現在是不可達的，則不 論事務是否提交該對象都會丟失。在一個實現中，關於在當前事務的子事務內 分配的不可達對象的日誌條目也被移除。
在框2430處，對於讀取對象日誌中的每一條目，檢查該條目所引用的對 象，並且如果該對象已經在更新對象日誌中，且對該對象讀取對象和更新對象 日誌的版本號匹配，則可移除讀取對象日誌條目。該進程可標識對象何時被首 次添加到讀取對象日誌中，以及對象何時被首次添加到更新對象日誌中。在任 一情況下，GC都用於移除包含的讀取對象日誌條目。在框2440處，GC模塊1390在允許重複條目的STM實現中從讀取對象 日誌移除重複條目。重複的讀取對象日誌條目移除的一個示例進程在以下參考 圖25來描述。然後，在框2450處，GC模塊1390審閱撤消日誌中的條目，並 將該日誌中的"先前值"與記入日誌的存儲器位置的當前值進行比較。如果這 些值匹配，則值未改變，並且沒有原因來維持該撤消日誌條目，因此GC模塊 1390移除這些條目。
圖25是示出由無用信息收集模塊1390執行的用於移除重複的讀取對象曰 志條目的一個這樣的示例進程2500的流程圖。圖25的進程對應於圖24的框 2440。在各種實現中，所示進程框可被合併、劃分成子框、或省略。圖25的 進程利用了讀取對象日誌條目僅記錄該對象在當前事務內已被打開來讀取的 這一事實。這使得對單個對象的多個條目是多餘的，並且因此在GC期間移除 這些條目是有益的。
圖25的進程利用了在無用信息收集期間為每一對象維護的單個讀比特標 志。在一個實現中，該標誌由運行時系統保持，這類似於如何保持STM字。 在另一實現中，GC模塊1390在GC時維護每一對象的標誌。該進程在框2510 處開始，在那裡GC模塊1390在日誌中的第一個條目處開始壓縮讀取對象日 志。接著，在框2520處，審閱由當前審閱的條目引用的對象。在框2525處， GC模塊1390確定該對象是否設置了其讀比特。如果沒有設置，則假設當前條 目是對該對象的第一個條目。由此，在框2530處，設置讀比特，並且單獨留 下該條目。然而，如果GC模塊1390確定讀比特先前已在框2540處設置，則 該模塊移除當前條目，因為它對於對象的前一條目是多餘的。在一個實現中， 該移除是通過將被保持的條目複製到被移除的條目的位置來原地完成的。在其 它實現中，不移動條目，而是僅僅在其所在之處解除其分配。該進程然後繼續 到判定框2545，在那裡該模塊確定在讀取對象日誌中是否存在其它條目。如果 是，則該進程繼續。如果不是，則該進程結束。
7.計算環境
以上軟體事務性存儲器技術可在各種計算設備的任一種上執行。該技術可 用硬體電路以及在如圖26所示的計算機或其它計算環境中執行的軟體來實現。圖26示出了其中可實現所描述的實施例的合適的計算環境(2600)的一 般化的示例。計算環境(2600)並不對本發明的使用範圍或功能提出任何局限， 因為本發明可在不同的通用或專用計算環境中實現。
參考圖26，計算環境(2600)包括至少一個處理單元(2610)和存儲器 (2620)。在圖26中，這一最基本的配置(2630)被包括在虛線內。處理單 元(2610)執行計算機可執行指令，並且可以是真實或虛擬處理器。在多處理 系統中，多個處理單元執行計算機可執行指令以提高處理能力。存儲器(2620) 可以是易失性存儲器(例如，寄存器、高速緩存、RAM)、非易失性存儲器(例 如，ROM、 EEPROM、快閃記憶體等)或兩者的某種組合。存儲器(2620)儲存實 現此處所描述的技術的軟體(2680)。
計算環境可具有附加特徵。例如，計算環境(2600)包括存儲(2640)、 一個或多個輸入設備(2650)、 一個或多個輸出設備(2660)以及一個或多個 通信連接(2670)。諸如總線、控制器或網絡等互連機制(未示出)將計算環 境(2600)的各組件互連。通常，作業系統軟體(未示出)為在計算環境(2600) 中執行的其它軟體提供了操作環境，並協調計算環境(2600)的各組件的活動。
存儲(2640)可以是可移動或不可移動的，並包括磁碟、磁帶或磁帶盒、 CD-ROM、 CD-RW、 DVD或可用於儲存信息並可在計算環境(2600)內訪問 的任何其它介質。存儲(2640)儲存用於實現此處所描述的技術的軟體(2680) 的指令。
輸入設備(2650)可以是諸如鍵盤、滑鼠、筆或跟蹤球等觸摸輸入設備、 語音輸入設備、掃描設備或向計算環境(2600)提供輸入的另一設備。對於音 頻，輸入設備(2650)可以是音效卡或接受模擬或數字形式的音頻輸入的類似設 備，或向計算環境提供音頻樣本的CD-ROM讀取器。輸出設備(2660)可以 是顯示器、印表機、CD刻錄機或提供來自計算環境(2600)的輸出的另一設 備。
通信連接(2670)允許在通信介質上與另一計算實體的通信。通信介質在 已調製數據信號中傳輸諸如計算機可執行指令、壓縮音頻或視頻信息或其它數 據等信息。已調製數據信號是其一個或多個特性以對信號中的信息編碼的方式 來設定或更改的信號。作為示例而非局限，通信介質包括用電、光、RF、紅外、線或無線技術。
此處所描述的技術可在計算機可讀介質的一般上下文中描述。計算機可讀 介質可以是可在計算環境內訪問的任何可用介質。作為示例而非局限，對於計
算環境(2600)，計算機可讀介質可包括存儲器(2620)、存儲(2640)、通 信介質和以上任一種的組合。
此處所描述的技術可在諸如程序模塊中所包括的在真實或虛擬目標處理 器上的計算環境中執行的計算機可執行指令的一般上下文中描述。 一般而言， 程序模塊包括執行特定任務或實現特定抽象數據類型的例程、程序、庫、對象、 類、組件、數據結構等。程序模塊的功能可如各種實施例中所需地被組合或在 程序模塊之間拆分。用於程序模塊的計算機可執行指令可在本地或分布式計算 環境中執行。
出於表示的目的，詳細描述使用了如"確定"、"生成"、"比較"和"寫 入"等術語來描述計算環境中的計算機操作。這些術語是對由計算機執行的操 作的高級抽象，並且不應與人類執行的動作混淆。對應於這些術語的實際計算 機操作可取決於實現而變化。
鑑於此處所描述的主題的許多可能的變型，要求保護落入所附權利要求書 及其等效技術方案的範圍和精神之內的所有這樣的實施例作為本發明。
權利要求
1.一種計算機系統中的方法，所述計算機系統包括處理單元和編譯器，所述編譯器是用關於軟體事務性存儲器操作的知識來配置的，所述方法被執行來編譯程序，所述程序包括軟體事務性存儲器塊，所述方法包括優化(460)所述程序以創建包含軟體事務性存儲器指令的經優化的程序；以及編譯(340)所述經優化的程序。
2. 如權利要求1所述的方法，其特徵在於，優化所述程序包括將直接訪問軟體事務性存儲器指令在所述軟體事務性存儲器塊處插入到所述程序中；以及對包括所述軟體事務性存儲器指令的所述程序執行優化，以創建一經優化的程序，使得所述優化的至少某一些被配置成特別地對所述直接訪問軟體事務性存儲器指令操作。
3. 如權利要求2所述的方法，其特徵在於，執行優化包括執行公共子表達式消除過程，該過程被修改為對分解的軟體事務性存儲器指令操作。
4. 如權利要求3所述的方法，其特徵在於，所述公共子表達式消除過程被修改成使得打開一對象來讀取的指令在所述同一事務內的打開一對象來更新的指令之後被消除。
5. 如權利要求3所述的方法，其特徵在於，所述公共子表達式消除過程被修改成使得一事務內對從存儲器地址的冗餘讀和寫以及對存儲器地址的冗餘日誌被移除。
6. 如權利要求5所述的方法，其特徵在於，所述公共子表達式消除過程還被修改成使得如果第一事務中的讀和寫被第二事務中的讀和寫變得冗餘，則消除所述第一事務中的讀和寫，其中所述第一事務嵌套在所述第二事務內。
7. 如權利要求2所述的方法，其特徵在於，執行優化包括執行代碼運動優化。
8. 如權利要求2所述的方法，其特徵在於，執行優化包括用確保對一存儲器事務外部的對象的事務性存儲器訪問與訪問該對象的至少一個非事務性存儲器操作之間的原子性的一個或多個事務性存儲器操作來擴充所述至少一個非事務性存儲器操作。
9. 如權利要求8所述的方法，其特徵在於，擴充非事務性存儲器操作包括在所述非事務性存儲器操作之前插入一打開操作，所述打開操作打開所述對象以供所述非事務性存儲器操作訪問；以及在所述非事務性存儲器操作之後插入一提交操作，所述提交操作確定在所述非事務性存儲器操作的執行期間是否有對所述對象的衝突訪問。
10. 如權利要求9所述的方法，其特徵在於-所述非事務性存儲器操作是讀取操作；所述打開操作被配置成在所述非事務性存儲器操作的執行之前檢索所述對象的狀態的指示；以及所述提交操作被配置成在所述非事務性存儲器操作的執行之後檢索所述對象的狀態的指示；以及如果所述對象的狀態指示衝突的訪問，則使得所述打開、讀取和提交操作循環，直到讀取變為可能。
11. 如權利要求9所述的方法，其特徵在於所述非事務性存儲器操作是寫入操作；所述打開操作被配置成獲得對所述對象的寫訪問；以及所述提交操作被配置成提交對所述對象所作的寫入。
12. 如權利要求9所述的方法，其特徵在於，所述打開和提交命令利用了所述對象的同步來確保所述非事務性存儲器操作原子地執行。
13. 如權利要求9所述的方法，其特徵在於，所述打開命令阻斷，直到它能夠打開所述對象來訪問。
14. 如權利要求8所述的方法，其特徵在於，還包括標識訪問存儲器事務外部的對象的一個或多個存儲器操作。
15. 如權利要求14所述的方法，其特徵在於，標識一個或多個存儲器操作包括分析事務性存儲器訪問以確定可在所述軟體的執行期間被事務性存儲器操作訪問的欄位；標識訪問可被事務性存儲器操作訪問的欄位的一個或多個非事務性存儲器操作。
16. 如權利要求15所述的方法，其特徵在於，對確保不被事務性存儲器操作訪問的任何欄位，避免對訪問該欄位的非事務性存儲器操作的擴充。
17. 如權利要求16所述的方法，其特徵在於，用一個或多個事務性存儲器操作來擴充訪問存儲器事務外部的對象的非事務性存儲器操作包括在所述非事務性存儲器操作周圍插入原子存儲器事務塊。
18. 如權利要求2所述的方法，其特徵在於，執行優化包括在一組程序點處標識對總是綁定到事務中新分配的對象的對象的引用；以及防止對象上的軟體事務性存儲器操作通過所標識的弓I用到達，其中所述操作在所述事務外部沒有效果。
19. 如權利要求18所述的方法，其特徵在於，在一組程序點處標識對總是綁定到新分配的對象的對象的引用跨過程調用而發生。
20. 如權利要求19所述的方法，其特徵在於，在一組程序點處標識對總是綁定到新分配的對象的對象的引用包括對所述程序執行前向數據流分析。
21. 如權利要求20所述的方法，其特徵在於，所述前向數據流分析包括對每一基本塊維護一數據結構，所述數據結構表示，在所述基本塊中的一位置處，對所述基本塊中的每一變量，如果所述變量或者已知為總是被賦值給新分配的對象，則所述變量可能被賦值給在所述事務外部分配的對象，或者對所述變量信息是未知的。
22. 如權利要求21所述的方法，其特徵在於，所述數據結構包括從每一引用到對每一引用保持的數據的映射，其中對每一引用保持的數據包括包含一點陣值和引用之間的依賴性的可更新單元。
23. 如權利要求22所述的方法，其特徵在於，維護所述數據結構包括使用所述引用之間的依賴性，當所述數據流分析進行時通過所述點陣值的可更新單元來傳播信息。
24. 如權利要求23所述的方法，其特徵在於，傳播信息包括在分析從變量到點陣值的可更新單元的映射中的未映射變量的程序語句之前將信息擴展到所述未映射變量。
25. 如權利要求18所述的方法，其特徵在於，防止對象上的軟體事務性存儲器操作通過所標識的引用到達，其中所述操作在所述事務外部沒有效果，包括，對每一引用，用當被分解成分解的軟體事務性存儲器操作時不包括更新曰志操作的更新操作來替換通過所述引用的更新操作。
26. 如權利要求18所述的方法，其特徵在於，防止對象上的軟體事務性存儲器操作通過所標識的引用到達，其中所述操作在所述事務外部沒有效果，包括，在軟體事務性存儲器操作被分解成分解的軟體事務性存儲器操作之後，移除通過所標識的引用來操作的分解的日誌操作。
27. 如權利要求18所述的方法，其特徵在於，還包括確定哪些所標識的引用是針對在所述事務之後不可訪問的對象的；以及其中，防止對象上的軟體事務性存儲器操作通過所標識的引用到達，其中所述操作在所述事務外部沒有效果，包括，移除軟體事務性存儲器操作以通過所確定的引用來打開對象來讀取或更新。
28. 如權利要求2所述的方法，其特徵在於，執行優化包括定位一打開引用來讀取的軟體事務性存儲器指令，該指令已知在執行期間後面跟有打開引用來更新的第一軟體事務性存儲器指令；以及對於打開引用來讀取的所述指令，替換為打開引用來更新的第二指令。
29. 如權利要求28所述的方法，其特徵在於，所述方法還包括移除打開引用來更新的所述第一指令。
30. 如權利要求29所述的方法，其特徵在於，移除所述第一指令包括使用公共子表達式消除來移除包括所述第一指令的冗餘指令。
31. 如權利要求28所述的方法，其特徵在於，所述軟體是由一控制流圖來表示的，並且所述方法是在所述控制流圖上執行的。
32. 如權利要求31所述的方法，其特徵在於，定位一打開引用來讀取的指令包括，對所述控制流圖中的基本塊標識一打開弓I用來讀取的指令；記錄所述引用；從所標識的指令開始前向掃描通過所述基本塊；當找到對所述引用的賦值時，停止對所標識的指令的掃描；以及當找到打開引用來更新的指令時，進而替換所標識的指令。
33. 如權利要求31所述的方法，其特徵在於，定位一打開引用來讀取的指令包括，對所述控制流圖中的基本塊-標識一打開弓I用來更新的指令；記錄所述引用；從所標識的指令開始前向掃描通過所述基本塊；當找到對所述引用的賦值時，停止對所標識的指令的掃描；以及當找到打開引用來讀取的指令時，進而替換所找到的打開引用來讀取的指令。
34. 如權利要求31所述的方法，其特徵在於，定位一打開引用來讀取的指令包括執行一數據流分析，所述數據流分析跨基本塊邊界搜索以找出因打開引用來更新的指令而變得冗餘的打開引用來讀取的指令。
35. 如權利要求34所述的方法，其特徵在於，執行數據流分析包括在所述控制流圖的每一基本塊的邊界處維護一變量集，所述變量集已知引用了被打開來更新的引用；對每一基本塊後向掃描通過所述控制流圖；當對一特定變量找到打開引用來更新的指令時，將該變量添加到對於所述基本塊的變量集中；當對一特定變量找到定義時，將該變量從對於所述基本塊的變量集中移除；當找到所述基本塊的開頭時，將對於所述基本塊的變量集與儲存在基本塊的末端的直接導向所述基本塊的變量集相交；重複所述進程，直到對每一基本塊創建了一穩定的變量集；以及對每一基本塊，將打開被對於所述基本塊的變量集引用的引用來讀取的指令認為是冗餘指令。
36. 如權利要求2所述的方法，其特徵在於，執行優化包括標識所述程序中的一個或多個過程，所述過程包括能夠在所述過程外部優化的一個或多個軟體事務性存儲器操作；對所述一個或多個過程中的每一個，創建所述過程的克隆的版本，所述克隆的版本允許對能夠在所述克隆的版本外部優化的軟體事務性存儲器指令的調用；移動能夠在所述過程外部優化的一個或多個軟體事務性存儲器操作；以及用對其克隆的版本的調用來替換對所述一個或多個過程的每一個的調用。
37. 如權利要求36所述的方法，其特徵在於，還包括通過移除能夠被優化的所述一個或多個軟體事務性存儲器操作中的冗餘來優化所述程序。
38. 如權利要求37所述的方法，其特徵在於，優化所述程序包括對所述程序執行公共子表達式消除。
39. 如權利要求37所述的方法，其特徵在於，能夠被優化的所述一個或多個軟體事務性存儲器操作包括獲取事務管理器的操作。
40. 如權利要求39所述的方法，其特徵在於，包括獲取事務管理器的操作的所述過程的克隆的版本包括取事務管理器的實例作為輸入的過程。
41. 如權利要求37所述的方法，其特徵在於，能夠被優化的所述一個或多個軟體事務性存儲器操作包括打開引用來讀取或更新的操作，所述引用作為輸入被傳遞給所述過程。
42. 如權利要求41所述的方法，其特徵在於，包括打開引用來讀取或更新的操作的所述過程的克隆的版本包括依賴於在過程被調用之前被打開的引用的過程。
43. 如權利要求42所述的方法，其特徵在於，創建包括打開引用來讀取或更新的操作的所述過程的克隆的版本包括執行一後向數據流分析來確定哪些過程包括對於已知在所述過程的開頭的引用打開引用來讀取或更新的操作。
全文摘要
描述了對軟體事務性存儲器指令執行優化以實現高效性能的軟體事務性存儲器系統。軟體事務性存儲器塊由軟體事務性存儲器指令來替換，這些指令隨後被分解成分解的軟體事務性存儲器指令。分解的指令允許了解指令語義的編譯器執行在傳統的事務性存儲器系統上不可用的優化。執行高級軟體事務性存儲器優化，諸如過程調用周圍的代碼移動、添加提供強原子性的操作、移除不必要的讀取—更新升級、以及移除對新分配的對象的操作。
文檔編號G06F9/45GK101542437SQ200680045337
公開日2009年9月23日 申請日期2006年11月27日 優先權日2005年12月7日
發明者A·E·肖納, D·R·小泰迪蒂, M·R·佩裡斯科, T·L·哈裡斯 申請人:微軟公司