基於中間代碼的優化中 循環的查找演算法有哪些呢 循環的優化方法又有哪些？
題主的問題：
基於中間代碼的優化中 循環的查找演算法有哪些呢 循環的優化方法又有哪些？
首先要在中間代碼上劃分出基本塊並且構造出控制流圖（CFG）。
控制流圖是個可能有環的有向圖。要找出其中的循環，最經典的做法就是使用Tarjans strongly connected components algorithm找出所有SCC，如果一個SCC是多於一個控制流圖節點（基本塊）的那麼肯定有循環，然後根據dominator關係確定loop header是誰；如果一個SCC是單一節點（基本塊）的，則要檢查該節點是否有從自己的末尾到自己的開頭的控制流邊，如有則是循環。
這樣就可以找出所有循環了。接下來通常會做的事情是把識別出來的循環歸納為一棵「循環樹」（loop tree）或者說循環森林（多棵循環樹），以描述循環之間的嵌套關係。
然後…循環上的優化是編譯優化的重中之重，話題太大回頭再碼字補充…R大已經回答了部分了，我就接著R大的來寫了。
1.循環的識別演算法
當前主流的編譯器中用到了兩種方法，一種就是 @RednaxelaFX所說的，利用求解流圖的強連通分量的演算法。原始的論文在http://192.35.222.224/newweb/~gilbert/cs240a/old/cs240aSpr2011/slides/TarjanDFS.pdf。這個方法也可以識別可規約循環(reducible loop)和不可規約循環(irreducible loop)，通常來說，我們在進行循環變換的時候只處理可規約循環，因為不可規約循環相當複雜。另外一種就是稍微簡單些的方法就是深度優先遍歷(Depth first traverse)。這種演算法思維直觀，實現簡單——遞歸遍歷即可，當然也有相對好點的方法——利用輔助棧的形式的工作流演算法。缺點就是無法有效的識別流圖中的不可規約循環。但是我們在處理的時候，一般是避免處理不可規約循環。所以這個缺點並不影響。
這種方法在OpenJDK的C1編譯器中使用了，另外一個研究用的虛擬機項目Maxine Virtual Machine也用了，代碼在ComputeLinearScanOrder.java中。2.循環優化演算法
在當前的主流的靜態編譯器，如：gcc，clang or llvm中，當開啟了高度優化選項-o3的時候，相當多的循環優化演算法就會對程序循環進行變換和優化。當然在循環優化領域內，既存在公共的循環優化演算法——不針對某一特定的硬體平台；也有針對某些特定的體系結構進行著重優化的，如針對多核處理器的循環並行，以及多級cache的指令預取等。
聲明：以下圖片來自於論文Loop Optimizations in Modern C Compilers
http://www.cs.columbia.edu/~ecj2122/research/x86_loop_optimizations/x86_loop_optimizations.pdf
2.1 機器無關演算法
2.1.1循環不變數移動(Loop invariant code motion)該項技術能夠方便、簡單的應用到大多數編譯器中用以提高性能。
最後的變換結果如下圖所示：
2.1.2 歸納變數的識別與消除(Identifying and removal of induction variable)
在現代類C語言中，幾乎所有的while和for循環都會使用一個計數器變數用於循環次數控制。這些變數則為歸納變數Induction variable。對於歸納變數，我們能夠應用兩種優化策略：強度削減和歸納變數消除。
如下圖所示：
2.1.3.循環展開(Loop unrolling)
該項優化及其簡單，但是只能應用到知道循環次數的循環上，對於哪些不知何時終止的循環則無能為力。充分利用了循環展開的優點的時候（提高程序的局部性，有利於數據、指令的預取），另外一個缺點也會隨之而來——代碼膨脹。所以，有些編譯器是在代碼大小小於某個閾值的時候，啟用這項優化。2.1.4.循環中switch語句變化(Loop unswitching)
該項變化通常是將包含在循環中的分支語句（該條件是不變的）提出到循環的外面。
當然，這種方法在降低指令的控制衝突的同時，也增大了代碼大小。所以和循環展開一樣，需要一個閾值進行控制何時該項優化被採用。
2.2.機器相關優化-------------------------未完待續------------------------------------------找循環好像說完了.
循環優化
按龍書分 Chap 10.5 Software Pipeling 是關於loop scheduling的.然後整個Chap 11 Optimizing for Parallelism and Locality.
大概是根據各種dependency 算 loop transformation.覺得書長的話，課件
http://suif.stanford.edu/~courses/cs243/看Software Pipeline 和 Loop transformation.然而這只是理論們循環優化最重要的方法當然是polyhedral model了，把affine變換都統一起來了。GCC里那個graphite，還有LLVM的Poly，都是基於polyhedral model的
這裡面同樣重要的是，有某個語句用到數組的哪個元素的精確信息。比如就可以用來消除中間數組，減少內存佔用，參考 下一代深度學習框架技術內幕 (打個廣告就跑如果循環是指natural loop的話，還是比較好找的。一般編譯器到這個階段已經生成了CFG圖以及它們之間dominator的關係，這樣找natural loop就是用深度優先搜索back edge：找到一條t-&>h的邊，其中h是t的dominator，這樣h就是loop的header，然後再遍歷一次找到屬於這個循環的所有block，然後根據各個循環的block set的從屬關係確定循環的層次。需要注意的是有時多個循環可能有同一個header，這時要特殊處理。
循環優化方法就太多了。通常會先做loop formation，例如在loop header前插入一個空的preheader（將來做外提用）。然後通過多個pass來優化循環。比較常見的方式有：
1、針對induction variables的優化：可以先找出循環的induction variables（就是循環內自增或自減的變數，可以通過header的phi結點，以及對其做自增／自減賦值的那一條MIR找到），然後就可以找到dependent induction variables（循環內對數組的訪問會經常在MIR這一層產生這類變數）。對於dependent induction variables，可以做strength reduction優化，例如把乘法變成加法，或者當數組的下標是dependent induction variables，以及循環邊界條件已知時，數組的越界檢查也可以優化掉（JVM的JIT會有這種情況）。
2、針對循環不變數的優化：通過SSA賦值關係很容易可以標記出所有循環不變數，然後把它們提到preheader里就可以了。
3、做constant propagation：就是把普通的constant propagation延伸到循環里，對於循環次數已知的循環可以採用這種優化。
4、循環展開，減少條件跳轉的overhead：通常做法是直接把循環體的block複製N份（包括條件跳轉的那個block），構建新的循環體，但展開後新的循環體內依然有N個條件跳轉指令，這時如果循環條件符合一定的已知條件的話，可以想辦法把中間的跳轉指令優化掉。展開的循環在寄存器分配方面也是有優勢的。
5、循環的vectorization：少數簡單的循環可以打包成SIMD指令大幅提高性能，這個比較複雜，不展開講了。
以上是本人做Android Dalvik及ART編譯器優化的一些心得，本人還沒看過鯨書，如有錯漏請指正。龍三9.6章節
不過課後練習沒有提供答案 https://github.com/fool2fish/dragon-book-exercise-answers 估計是大廠必考章節，所以就不給標答了，不過可以在LLVM Transform Scalar、Vectorize、Utils代碼中找實戰「答案」:)
識別自然循環可以用回邊法，先找dom節點，再找回邊，再遍歷，鯨書上講控制流那章有詳細演算法偽碼
推薦閱讀：
※KLEE到底是靜態分析工具還是動態分析工具？
※如何理解基於CFL-reachability的過程間分析？
※C++越跑越慢的問題？
※求講解下列鏈接以及pascal嵌套子程序是如何實現的？
※關於c前置，後置++，及函數傳參的問題？