Can you summarize the following document?
        
  許多程式語言,程式設計師會有任意地配置過多變數的錯誤觀念,然而在編譯時,編譯器必須決定在一個較小及有限暫存器的系統中如何分配這些變數,並非所有變數都是在同一時間執行,所以有些暫存器可能被分配超過一個變數。然而,兩個被分配在同一暫存器的變數,若在同一時間使用,若是不破壞他的數值就無法被分配在相同的暫存器。無法被分配在相同的暫存器的變數必須被保留在隨機存取儲存器,在需要讀取或寫入時才會被載入,這個過程稱之為溢位(spilling)。記憶體存取速度比存取暫存器還慢,這會降低程式的執行速度,所以一個最佳化的編譯器會儘可能的將更多的變數放置在暫存器。"暫存器壓力"(Register pressure)這個詞被使用在當硬體暫存器數量比起理想數量還少的狀況,高壓的情況通常代表會產生更多溢位以及更多過載的情況發生。  除此之外,程式可以被進一步的最佳化,只要可行,任何地方都能透過codice_1指令來使一個暫存器的數值可以被移進移出,這在編譯器中相當重要,這被使用在一些最佳化技術,例如靜態單賦值形式,他會在中間碼額外產生codice_1指令。

  透過活躍變數分析(Live variable analysis),編譯器可以決定哪個變數的集合在同一時間是活躍的,也就是涉入codice_1指令的變數。使用這些資訊,編譯器可以建構一張圖,使每個點(Vertex)在程式中代表一個獨立的變數。當變數被同時使用時,則利用"干擾邊"(Interference edges)連結兩個節點,當變數同時涉入move指令時,則建立"優先邊"(preference edges)。可以透過K-coloring用來解決暫存器配置的問題(K為暫存器可用的數量)。兩個共享一個干擾邊的節點不會被分配相同的顏色,而共享一個優先邊的節點可能會被分配相同的顏色,有些節點可能一開始就會被上色,代表這些變數因為慣例或是模組間溝通的因素而必須留在某些特定的暫存器,圖著色問題廣義來說是NP完全問題,然而一個好的演算法必須平衡效能以及程式碼的品質。  圖著色技術是相當有效率,因為它不只考慮到變數的暫存器配置,還考慮在同時間執行的變數,邏輯上,如果變數V所有活躍的鄰近變數可以被配置暫存器,那麼通過V則可以訪問到所有鄰近的變數,所以這是一個遞迴的案例,目的是移除活躍變數集合中的變數。這個迴圈將持續進行,直到所有活躍變數都可以被配置,而其他的變數則溢位到記憶體。

  在多數的暫存器分配,每個變數會存在暫存器或是記憶體,換句話說,如果一個變數無法被分配到一個暫存器,那麼當這個變數要被使用時就會從記憶體載入。一個"溢位的變數"(Spilled Variable)代表一個變數在記憶體中而不在CPU的暫存器。舉例來說,一個32位元的變數溢位到記憶體,他會取得32位元的堆疊空間,而所有使用到這個變數的位置將會指到記憶體,這樣的變數的處理速度相較於暫存器的變數就會比較慢,所以要決定哪些變數必須溢位,就必須考慮到執行時間、程式碼佔用空間以及資料空間等因素。

  暫存器分配有很多型別,迭代暫存器接合(Iterated Register Coalescing,IRC)則是常用的一種,IRC是由LAL George及Andrew Appel在1996年提出,IRC基於一些原理所運作,第一,如果在圖中存在無法被移動的節點,而這些與這些節點的連線的數量小於K,則這些圖可以直接移除掉這些節點,因為一旦這些節點被加回去,則可以保證找到他們的顏色(簡化)。第二,兩個節點共享一個優先邊,而他們鄰近集合的連線總數小於K,那麼這兩個點可以被結合為一個節點(接合),如果上述兩個步驟可以簡化圖,簡化的程式在移動相關節點時(凍結時),可以再執行一次。最後,如果沒有任何其他工作了,節點可以被標示為可能溢位並且從圖中移除(溢位)。以上步驟用以減少圖中節點的連線數,節點的連線數可能從大於K的情況降為低連線數,使節點可以被簡化或是接合。這個階段的演算法被迭代,以確保簡化及接合的品質。虛擬程式碼如下:  codice_4  在IRC中進行接合是相當穩定的,因為一個積極的接合可能會導致圖的溢位,然而這同時啟發了像是George coalescing接合了更多的節點,更可確保沒有額外的溢位發生,Work-lists被使用在這個演算法來確保每個IRC的迭代皆需要sub-quadratic time。

  利用圖著色來改進的程式碼的效率雖然有效,但是配置的時間仍然很長,在靜態編譯的案例中,配置時間並不是那麼被在意,但是在動態編譯的案例中,例如即時編譯(Just-in-time,JIT)編譯器,快速的暫存器配置是很重要的,Poletto及Sarkar提出一個的有效技術線性掃描配置,這個技術僅需要一個階段取得活躍變數的區間列表,較短生命週期區間的變數將會被分配到暫存器,而較長生命週期的變數將會被溢位,這個結果的效能平均只比圖著色降低12%。  線性掃描演算法的步驟如下:  Cooper及Dasgupta近期開發了一個"有損的"Chaitin-Briggs圖著色演算法,適用於JIT。"有損"代表這個演算法所提出的干擾圖並不是那麼精確,這個最佳化減少了圖建立的步驟,Chaitin-Briggs使它適合執行時期的編譯。實驗中顯示,這個有損的暫存器配置比起線性掃描效率來得好。  "理想的"暫存器配置演算法是基於Goodwin及Wilken所開發的線性規劃演算法,這些演算法已經被Kong及Wilken延伸到更多架構。  最糟的情況是執行時間為指數,這個實驗結果顯示,實際的時間是典型的formula_1。  在靜態單賦值形式進行暫存器配置的可能,是近期研究所專注的專案,SSA形式程式的干擾圖為弦圖,可在多項式時間內進行著色。
在編譯器最佳化的領域裡,暫存器配置(Register Allocation)的用途,在於使一個在較少暫存器數量的CPU可使用較大數量的變數,暫存器配置可使用在一個基本區段(Basic block)(區域暫存器配置)、函式或程式(全域暫存器配置)、或是透過Call Graph進行跨函式邊域分析(跨程式暫存器配置),當完成每個函式或是程式,慣例上會要求每個呼叫函式的位置(Call site)必須插入儲存或是還原。