Homework 4 (B)
 
 
從GCC如何Optimizing code來著手這次作業!
 
Code Motion
Code Motion是指在Common subexpression elimination 時去掉多餘的代碼,Code motion並不是去掉所有的subexpression,而是在中間語言形式下改變它們的位置,以便能減少它們出現的次數。比如,在嵌套的循環或其他控制結構裡 ,中間變量的計算次數可能不是最優的,要優化這些程序,編譯器把這些計算語句移到循 環更少的地方,並且保證計算結果是一樣的。把計算移出循環的方法我們稱為 loop-invariant code motion。Code motion還用在另一種Common subexpression elimination裡,叫做partial redundancy elimination。
 
Common Subexpression Elimination
Listing 5-1. An Example of a Common Subexpression 
#define STEP 3
#define SIZE 100  
int i, j, k;  
int p[SIZE];  
for (i = 0; i < SIZE; ++i) {
    j = 2 * STEP;
    k = p[i] * j;  
}
 
j = 2 * STEP; 就是一個common subexpression,他的值在迴圈沒外計算都沒有影響,STEP也是固定不會改變的,而Common Subexpression Elimination就會把他從迴圈內移出,減少迴圈內的重複計算
 
j = 2 * STEP;  
for (i = 0; i < 100; ++i) {
    k = p[i] * j;  
}
 
 
Constant Folding
i = 10;
j = 20;
ij = i * j;
 
如果後面的程式都沒有用到i和j,可以去除他們的定義(應該會變成ij = 10 * 20)
 
Copy propagation transformation
In wiki 的範例反而感覺比較好懂..
y = x
z = 3 + y
 
z = 3 + x
 
Dead Code Elimination
把實際上無用的或多餘的代碼去掉!!!
if (a == 10) {
.......
}
else {
    ...
    if (a == 10) {    // WT..?