編譯器的自動(dòng)內(nèi)存管理，靜態(tài)的GC算法
?C語(yǔ)言幾乎唯一的缺點(diǎn)就是，需要手動(dòng)管理內(nèi)存。
拋開(kāi)這點(diǎn)之外，我覺(jué)得其他語(yǔ)言都不如C語(yǔ)言?。
所以，雖然自動(dòng)內(nèi)存管理比較復(fù)雜，但我還是給scf編譯器框架加了靜態(tài)的GC算法。
在編程方面，自動(dòng)內(nèi)存管理一般叫GC算法，是英文Garbage Collection的縮寫(xiě)。
棧內(nèi)存的管理比較簡(jiǎn)單，是由編譯器根據(jù)函數(shù)調(diào)用鏈而自動(dòng)管理的。
堆內(nèi)存的管理，在C語(yǔ)言里是由程序員手動(dòng)管理的。
因?yàn)槌绦騿T管理錯(cuò)了堆內(nèi)存而導(dǎo)致的BUG，是C語(yǔ)言最常見(jiàn)、也最難搞的BUG。
所以，后來(lái)的編程語(yǔ)言都對(duì)內(nèi)存管理做了簡(jiǎn)化，例如C++的智能指針。
C++的智能指針，是一種半自動(dòng)的內(nèi)存管理機(jī)制：
它把一個(gè)堆內(nèi)存的指針?lè)旁谝粋€(gè)類(lèi)的成員變量里，利用局部對(duì)象離開(kāi)作用域時(shí)的析構(gòu)函數(shù)，來(lái)完成堆內(nèi)存的釋放。
所以C++的效率比其他語(yǔ)言快得多，因?yàn)榫植繉?duì)象什么時(shí)候離開(kāi)作用域，是可以在編譯時(shí)就確定的，不需要在運(yùn)行時(shí)做額外的處理。
也就是說(shuō)，C++的智能指針是靜態(tài)的GC算法。
在編譯時(shí)就處理好的算法，是靜態(tài)的算法。
在運(yùn)行時(shí)才會(huì)處理的算法，是動(dòng)態(tài)的算法。
動(dòng)態(tài)的算法依賴(lài)于運(yùn)行時(shí)狀態(tài)，對(duì)程序的速度有較大的影響：
- 因?yàn)榭蚣茉谔幚韺?duì)象內(nèi)存的回收時(shí)，用戶(hù)程序不得不暫停，
- 否則兩邊發(fā)生競(jìng)爭(zhēng)條件，那就是跟C語(yǔ)言的野指針一樣的BUG。
寫(xiě)過(guò)C語(yǔ)言的都知道，多線程的野指針是非常難查的BUG，因?yàn)槌绦蚺茱w了不知道會(huì)core在哪里，而且BUG也不是必現(xiàn)的。
為什么程序員怕有主控軟件的交通工具？
因?yàn)槌绦騿T知道多線程+競(jìng)爭(zhēng)條件+野指針 == 隨機(jī)crash + 事后找不到第一現(xiàn)場(chǎng)?
動(dòng)態(tài)的GC算法，為了避免出現(xiàn)第2種情況，那就只能使用第1種情況。
1、GC算法有必要是動(dòng)態(tài)的嗎？
實(shí)際上沒(méi)必要，否則C語(yǔ)言怎么手動(dòng)管理內(nèi)存的。
C語(yǔ)言的free()代碼肯定是在編譯之前就寫(xiě)好了的！
只要寫(xiě)對(duì)了free()位置，C語(yǔ)言既不會(huì)出BUG，也不會(huì)內(nèi)存泄漏。
所以，編譯器只要代替程序員添加free()，就可以自動(dòng)管理內(nèi)存了。
free()的添加位置，當(dāng)然是在變量離開(kāi)作用域時(shí)。
如上圖：
有4個(gè)對(duì)象變量m0, m1, m2, m3，
main()函數(shù)返回時(shí)也是它們離開(kāi)作用域的時(shí)候，所以在main函數(shù)的結(jié)尾自動(dòng)添加釋放代碼，程序員就不用手動(dòng)釋放內(nèi)存了。
2、怎么檢測(cè)變量什么時(shí)候離開(kāi)作用域？
在編譯器的后端：
1）代碼的每個(gè)基本塊都是流程圖上的一個(gè)節(jié)點(diǎn)，
2）基本塊之間通過(guò)跳轉(zhuǎn)聯(lián)系起來(lái)，
3）基本塊內(nèi)部的代碼是順序運(yùn)行的。
所以，釋放內(nèi)存的代碼需要加在兩個(gè)基本塊之間。
上述main()函數(shù)的流程圖
上圖是前面的main()函數(shù)的流程圖。
創(chuàng)建一個(gè)對(duì)象分兩步：第一步調(diào)用malloc()申請(qǐng)內(nèi)存，第二步調(diào)用構(gòu)造函數(shù)__init()初始化內(nèi)存。
（為了簡(jiǎn)化代碼，我沒(méi)有做返回值為NULL的檢查）
在第8個(gè)基本塊 m3 = m0 + m1 + m2 之后，m0, m1, m2 就不再使用了，也就是它們3個(gè)離開(kāi)作用域了。
即使在源代碼層面這時(shí)m0, m1, m2依然處于main()函數(shù)的作用域內(nèi)，但對(duì)后端來(lái)說(shuō)它們已經(jīng)離開(kāi)作用域了，因?yàn)橹蟮幕緣K都不再使用它們了。
所以，對(duì)m0, m1, m2的釋放代碼，應(yīng)該加在第8和第9號(hào)基本塊之間。
第9號(hào)基本塊會(huì)把指針 m3->data 賦值給dd，這會(huì)讓?zhuān)╩3->data）內(nèi)存的引用計(jì)數(shù)+1。
對(duì)m3的釋放代碼可以放在第9和第10之間，之后不會(huì)再使用m3了：這會(huì)讓m3->data的引用計(jì)數(shù)-1。
這時(shí)，內(nèi)存數(shù)據(jù)有且只有1個(gè)引用計(jì)數(shù)（一開(kāi)始自帶1個(gè)），同時(shí)有且只有指針dd指向它。
指針dd的釋放在for循環(huán)之后，即第10和11之間：這里的釋放會(huì)讓引用計(jì)數(shù)減少到0。
在引用計(jì)數(shù)為0時(shí)，要調(diào)用free()函數(shù)，把內(nèi)存還給系統(tǒng)。
GC算法的要點(diǎn)有3個(gè)：
1）什么時(shí)間調(diào)用的malloc()，
2）什么時(shí)間有指針的賦值，要把引用計(jì)數(shù)+1，
3）什么時(shí)間離開(kāi)作用域，也就是后續(xù)不再使用對(duì)象變量，要把引用計(jì)數(shù)-1，如果減少之后為0，就調(diào)用free().
3、跨函數(shù)的指針?lè)治觯?/h4>
有時(shí)候，申請(qǐng)的內(nèi)存并不會(huì)在當(dāng)前函數(shù)內(nèi)釋放，而是返回給更上層的主調(diào)函數(shù)。
這時(shí)的GC算法，就需要跨越函數(shù)的調(diào)用鏈，進(jìn)行指針?lè)治觥?/p>
mat類(lèi)的構(gòu)造函數(shù)__init()
前面的mat對(duì)象的成員指針 m3->data，就是需要跨函數(shù)分析的指針。
它是在構(gòu)造函數(shù)里申請(qǐng)的內(nèi)存，因?yàn)槭浅蓡T變量，所以要在析構(gòu)函數(shù)里釋放。
如果是局部變量，就在當(dāng)前函數(shù)內(nèi)釋放：因?yàn)榫植孔兞康淖饔糜蚓褪钱?dāng)前函數(shù)。
mat類(lèi)的聲明，成員變量部分
成員變量的有效時(shí)間，是伴隨著當(dāng)前對(duì)象的。
局部變量的有效時(shí)間，是伴隨著當(dāng)前函數(shù)的。
成員變量在構(gòu)造函數(shù)返回時(shí)依然有效，所以要把它是malloc()申請(qǐng)的這個(gè)信息，傳遞到更上層的函數(shù)。
這樣：
1）在main()里才知道它是malloc()申請(qǐng)的，
2）在 dd = m3->data 時(shí)才知道給它指向的內(nèi)存引用計(jì)數(shù)+1，
3）在釋放m3時(shí)，析構(gòu)函數(shù)把引用計(jì)數(shù)-1之后，引用計(jì)數(shù)才不為0：內(nèi)存依然是有效的，這時(shí)指針dd依然指向它。
否則，dd就是野指針了！
mat類(lèi)的析構(gòu)函數(shù)__release()
函數(shù)調(diào)用鏈，在語(yǔ)義分析時(shí)是很容易確定的。
抽象語(yǔ)法樹(shù)AST上的每一個(gè)函數(shù)調(diào)用，必然有一個(gè)主調(diào)函數(shù)、有一個(gè)被調(diào)函數(shù)。
主調(diào)和被調(diào)，構(gòu)成了整個(gè)程序的函數(shù)調(diào)用圖：
最頂層的是main()函數(shù)，最底層的是malloc()函數(shù)。
以malloc為起點(diǎn)、main為終點(diǎn)，做圖的寬度優(yōu)先搜索，就可以獲取整個(gè)調(diào)用鏈。
然后從離malloc最近的函數(shù)開(kāi)始，一層層的分析就行了。
函數(shù)調(diào)用圖
一定是用圖的寬度優(yōu)先搜索（BFS）！
不能用深度優(yōu)先搜索（DFS），因?yàn)橐粋€(gè)上層函數(shù)可能調(diào)用多個(gè)下層函數(shù)，而這多個(gè)下層函數(shù)里都malloc了內(nèi)存。
如上圖：
如果是DFS，分析順序是A->D，這樣D調(diào)用B而申請(qǐng)的內(nèi)存就會(huì)被漏過(guò)去了。
如果是BFS，分析順序是A->B->C->D->E，這樣任何函數(shù)申請(qǐng)的內(nèi)存如果傳遞給上層，（在分析上層函數(shù)時(shí)）都不會(huì)被漏過(guò)去。
4、遞歸調(diào)用的指針?lè)治?/h4>
上圖的C()和E()之間的互相調(diào)用構(gòu)成遞歸，表現(xiàn)為函數(shù)調(diào)用圖上的回路。
這種情況下，兩個(gè)函數(shù)里申請(qǐng)的內(nèi)存會(huì)互相傳遞，屬于最復(fù)雜的一種情況！
在編譯器里的處理方法是：
用do while循環(huán)檢查內(nèi)存的傳遞情況，記錄傳遞的變量和計(jì)數(shù)，直到不再發(fā)生變化為止。
最后，就是在合適的位置添加free()代碼了：
最后的總是最簡(jiǎn)單的，the last is the simplest.
