---
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 是甚麼？


:::

## 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