---
# System prepended metadata

title: Adv Compiler(11/24)W11#8
tags: [' AdvCompiler', 111-1]

---

---
title: Adv Compiler(11/24)W11#8
tags: 111-1, AdvCompiler
---
[TOC]


<style>
.blue {
  color: blue;
}
.red {
  color: red;
}
.green {
  color: green;
}
.purple {
  color: purple;
}
</style>




###### 11/24
###### 只有課本 9.1 的內容
:::success
- 自己補充: 
- Types of Code Optimization: 
    - The optimization process can be broadly classified into two types :
    1. Machine **Independent** Optimization:
        - This code optimization phase attempts to **improve the intermediate code** to get a better target code as the output.
        - The part of the IR(intermediate code) which is transformed here does **not involve any CPU registers** or **absolute memory locations**.
    2. Machine **Dependent** Optimization: 
        - Machine-dependent optimization is done **after the target code has been generated** and when the code is transformed according to the target machine architecture.
        - It **involves CPU registers** and may **have absolute memory references rather than relative references**.
        - Machine-dependent optimizers put efforts to take maximum advantage of the **memory hierarchy**.
:::

# Machine-Independent Optimization
## Principle Sources of Optimization
### Global Optimization
- Optimization 也可以說是 improvement 之意
- optimize 不只是 prove 如何改善，還要證明自己的作法是最好 der，即證沒有其他的方法比這個更好
1. Optimization 是在做 Program Transformation
2. Optimization 衡量的三個標準
    1. 以前：**execution speed**
        - 比較翻譯出來的執行檔(.exe)的執行速度。
    2. 現在：**code size**
        - 比較翻出來的 code size 大小，對於嵌入式系統的領域(SOC-system on chip)很重要
            （也就是說不介意 program 再多跑 1, 2 秒，跑的不是最快也無妨，但 **code size 越小越好**）
    3. 耗電量 - power optimization | energy optimization
        - 在差不多功能的 code (機器命令)，若兩個的耗電量不同，盡可能在執行 code 時降低耗電量
        - 記憶體的 power reduction
            - static RAM: 把資料寫進去固定在 voltage high??
            - dynamic RAM: 假設 device 能儲存資料的 voltage bound 為 3V，所以只要讓 RAM 維持在 > 3V 的情況，當 vlotage 快要到(低於) 3V 時再將 RAM 充滿電(ex. 6V)，就有機會降低耗電量
            - 以上方 RAM 舉例是想表示 **記憶體是耗電 der，耗電很多是在 high voltage 的狀況**
            - 改善 RAM 的方法：
                1. 數量: 
                    限制儲存資料的個數(0&1可以存的 bit 多寡)
                2. 安排 bit 在 memory 中的位置: 
                    voltage 在 0->1 時為充電的情形，而 1->0 則是在放電，以上兩種情形為 voltage 的改變且會造成耗電量增加，所以盡可能讓bit 在每個 cycle 時保持 0->0 或 1->1 的情形，以減少耗電量。

:::info
以前(傳統)的 optimization 是在分辨(比較)，透過 compiler 轉出來的 code 的執行效能是不是 optimizing。(因不同的 compiler 轉出來的 code 是有差異性ㄉ)
:::
- 轉換(optimization)前後須嚴格滿足的條件。 
1. 轉換(optimization)前後需證明出，此轉換能夠**保留程式語言的語意(preserve the semantic)**，或保留 source program 的語意，即翻譯前後 **code 執行效果要一樣**。 
2. 若 compiler 在轉換後，轉出來的結果有些許不同(substantially different)，但卻能更有效率(more efficient)的執行此 program。
    即便如此仍不可使用該方法，因為如果 100 個 examples 中，雖然 99 個 examples 能得到正確的解答，可是有 1 個結果和 source program 想達到的效果相異，就不能使用該方法。
3. 當提出一個 optimization 的方法後，仍要提供 low-level semantic 的表達方法，讓其他人驗證程式轉換後的執行效果是否最佳化。
4. ex. i+0 用 i 取代，有兩個說法
    - 不同意: compiler 怎麼可以自己判斷不用做加法?
    - 同意: 歡迎進入 compiler optimization 的世界(?)
## Redundancy
- 不必要的重複: 同樣的事做兩次，和做一次得到的效果相同。
- **redundant operation**: ex. 宣告時 assign 一個初始值，後方又 assign 同個 value。
    OR 初始值設為 0 ，中間沒有用到此 variable，又將其 value assign 為 1。
- 通常發生在 programmer 初手的低級錯誤，是一種 side effect，通常發生在 source level。
:::success
- side effect 是甚麼？

![](https://i.imgur.com/Hy7X5D2.png)

:::

## Common-Subexpression Elimination
- 屬於 Semantics-Preserving Transformation 的一種
> - Semantics-Preserving Transformation
>   (ａ) Common-Subexoression Elimination
>   (ｂ) Copy propagation
>     1. It's extension of constant propagation.
>     2. 
>     3. 利用 reduces co
>     
>   (Ｃ) Dead-code elimination
>   (ｄ) Constant folding
:::danger
propagation: 
傳播、廣傳；
（植物）繁殖，（動植物）繁殖，繁衍；
宣傳，（光、聲波等的）傳播
:::

## Data-Flow Analysis

## Constant Propagation

:::warning
Note: Difference between **Constant Propagation** and **Constant Folding**: 

In <span class="red">Constant Propagation</span>, the <span class="red">**variable**is substituted with its **assigned constant**</span> where as in <span class="blue">Constant Folding</span>, <span class="blue">the **variables** whose **values can be computed at compile time** are considered and computed.</span>

:::
## Partial-Redundancy Elimination

# Quiz #7 
![](https://i.imgur.com/4V8Kglb.png)
