對於一個很複雜的常量表達式，編譯器會算出結果再編譯嗎？

01-04

抑或是很忠實地把這個表達式完全翻譯成機器碼，留給最終的程序去解決？
ps：本人使用vs2010和keil uv4 都是c語言
但是也希望了解別的高級語言在這方面的問題

把常量表達式的值求出來作為常量嵌在最終生成的代碼中，這種優化叫做常量摺疊（constant folding）。題主的問題：

對於一個很複雜的常量表達式，編譯器會算出結果再編譯嗎？
抑或是很忠實地把這個表達式完全翻譯成機器碼，留給最終的程序去解決？

這種問題會有幾個維度。挑兩個來說說：

涉及的常量摺疊是否為語言規範所強制要求的。如果是的話，那麼符合規範的編譯器就一定要做這樣的常量摺疊。
如果不屬於上一條的情況，那麼這就是編譯器的實現質量的問題。一個編譯器可以自由選擇是否做常量摺疊（或其它常量相關）優化。同一個編譯器有可能可以配置在不同的優化層級上工作，或許有些在低優化層級沒有被常量摺疊的代碼，在高優化層級會被優化。

常量摺疊的概念自身很簡單。對此沒啥了解的同學可以先跳個老傳送門：Optimizing C++ Code : Constant-Folding

=========================================

語言規範要求做常量摺疊的情況

Java

例如說在Java語言中，下面這些情況都會被認為是語言規範所規定的編譯時常量表達式：

Java原始類型（byte、boolean、short、char、int、float、long、double）以及java.lang.String的字面量
聲明為static final的Java原始類型或java.lang.String類型的靜態欄位，並且帶有以常量表達式來初始化的情況（如果沒有初始化表達式或者初始化表達式不是常量表達式的話則不算）
聲明為final修飾的原始類型或java.lang.String類型的局部變數，並且帶有以常量表達式來初始化的情況（類似於上一條）
以常量表達式為操作數的算術和關係運算表達式，以及String拼接運算符（"+"）

所以，在Java中，下面的表達式都是語言規範強制要求的常量表達式：

1 // int literal, type: int, value: 1 1.0 // double literal, type: double, value: 1.0d "foobar" // string literal, type: java.lang.String, value: "foobar" "foo" + 1 // constant string concatenation expression, type: java.lang.String, value: "foo1" 1 &< 2 // constant relational expression, type: boolean, value: true

然後下面的Foo類中的幾個聲明：

class Foo { static final int BAR = 37 + 2 + 3; // yes public static final int BAZ = BAR + 1; // yes public static final int GOO; // no: no initializer public static final int QUUX = Integer.valueOf(42).intValue(); // no: initializer not a constant expression

public static int example() { final int x = 42; // yes int y = 42; // no final int z = "foobar".length(); // no: initializer not a constant expression } }

像這樣的情況，Java語言編譯器（例如javac、ECJ）在遇到相關的運算符時，必須要檢查其操作數是否都為常量表達式，如果是的話就必須在編譯時對該運算符做常量摺疊。

C#在語言規範里也有類似的規定。

當然，即便一個表達式從Java語言規範的角度看不是強制的常量表達式，編譯器還是有自由在語義允許的前提下把代碼優化為在編譯時求值。例如說，像下面的例子，目前主流的桌面/伺服器端JVM里的JIT編譯器都可以徹底優化掉：

public static int foo() { int x = 40; int y = new int[2].length; return x + 0 + y; }

可以被一些JIT編譯器優化到等價於：

public static int foo() { return 42; }

C語言當然也有類似的規定。請參考 Constant expressions。

最典型的，整型字面量、sizeof()運算符（當參數不是VLA時），以及各種算術、關係/比較運算符在所有操作數都是整型常量時，整個表達式都會算是整型常量表達式。所以像是說 40 + 1 + (4 &> 3) 這個表達式就是一個整型常量表達式，必須在編譯時求值。

C語言里有些語言結構是要求操作數一定要是常量表達式的，例如說非VLA的數組聲明裡面指定數組長度的表達式。如果有局部變數聲明 int a[10 + 2]; ，而10 + 2被允許在運行時才求值的話，那麼這個數組的大小就要在運行時才知道，就變成一個VLA了。

C++

早期版本的C++的常量表達式的規定跟C語言是頗為相似的。加入模版支持後，通過模版元編程實現複雜的編譯時求值的技巧被人發掘出來，變得很有趣。

C++11開始支持的constexpr修飾符則進一步擴大了非模版語法下能表達的編譯時求值的語法結構的範圍，C++14、C++17都對此做了進一步擴展。

D語言

D語言也有跟C語言相似的常量表達式，此外它還特彆強調它的編譯器支持「CTFE」（Compile Time Function Evaluation），也就是說如果一個函數調用傳入的所有參數都是編譯時常量，而且這個函數滿足一些（不那麼多的）限制，那麼這個函數調用就會被編譯時求值。

放倆傳送門：

Compile Time Function Evaluation (CTFE) - D Language Tour
Project Highlight: The New CTFE Engine

=========================================

編譯器提供的特殊查詢支持

GCC有一個編譯器內建函數（builtin function），

__builtin_constant_p(x)

可以檢測傳入的參數表達式是否為編譯器可以在編譯時做常量摺疊的表達式。請參考官方文檔的描述：

Other Builtins - Using the GNU Compiler Collection (GCC)

Clang也支持這個編譯器內建函數。

=========================================

一個C語言的綜合例子

舉個綜合例子，來看看從語言規範上看並沒有要求在編譯時徹底求值，但編譯器自身通過優化實現了徹底求值的情況。

int fib(int);


int foo() {

  return fib(21); // 17711

}

int fib(int n) { int a = 1, b = 0; for (int i = 0; i &< n; i++) { int t = a; a = a + b; b = t; } return a; }

用Clang 3.0到3.9.1測個遍，這些版本的Clang在-O2下都可以把foo()完全靜態求值，變成等價於：

int foo() { return 17711; }

這裡沒有任何const修飾，也不依賴於諸如C++14開始支持的擴展版constexpr，全靠Clang編譯器自己決定做的優化而達到這樣的效果。其它主流的C/C++優化編譯器在-O3、/Ox之類的優化層級上對這個例子似乎都還不會把foo()徹底的靜態求值掉，例如說試了下GCC 4.4.7到6.0，然後ICC 13、17，然後MSVC CL 19，都做了一些優化但是沒有完全靜態求值。

=========================================

編譯器中常量相關優化的極入門介紹

簡單說說這三種優化：

常量摺疊（constant folding）
常量傳播（constant propagation）
條件常量傳播（conditional constant propagation）及其改良版，稀疏條件常量傳播（sparse conditional constant propagation，SCCP）

1、常量摺疊

常量摺疊是編譯器里最基本最常見的優化，沒有之一。連很多基本上不做優化或者只做很簡單優化的編譯器都會實現常量摺疊，例如TCC（Tiny C Compiler）。

本文前面講的很多東西都是跟常量摺疊相關的。看似很直觀明了對不對？

簡單的常量摺疊確實是很簡單的。例如說，如果用C++寫一個類C語言的編譯器，在它做語法分析/構建AST的時候，可以做類似這樣的事情：

Node* Parser::ParseAdditiveExpression() { Node* expr = ParseMultiplicativeExpression();


  while (Token() == "+" || Token() == "-") {

    Operator op;

    if (Token() == "+") {

      Match("+");

      op = OP_BINARYADD;

    } else {

      assert0(Token() == "-");

      Match("-");

      op = OP_BINARYSUB;

    }

    Node* left = expr;

    Node* right = ParseMultiplicativeExpression();

    expr = CreateBinaryExpression(op, left, right);

  }
  return expr;

}
Node* CreateBinaryExpression(Operator op, Node* left, Node* right) {

  // constant fold simple cases

  if (left-&>IsConstant()  right-&>IsConstant()) {

    switch (op) {

    case OP_BINARYADD: {

        Type type = PromototedTypeFor(left, right);

        switch (type) {

        case T_INT:

          return new Constant(T_INT, left-&>IntConstantValue(), right-&>IntConstantValue());

        case T_LONG:

          return new Constant(T_LONG, left-&>LongConstantValue(), right-&>LongConstantValue());

        // other types ...

        }

      }

      // other operators ...

    }

  }

// otherwise create the node return new BinaryExpression(op, left, right); }

這樣，對於下面的表達式，

1 + 2 + 5

在做語法分析+構建AST的時候就可以將其常量摺疊為8了，簡略步驟是：

Step 1: 1 + 2 + 5 ^


  expr = Constant(T_INT, 1)
Step 2:

  1 + 2 + 5

      ^
  expr = CreateBinaryExpression(OP_BINARYADD, Constant(T_INT, 1), Constant(T_INT, 2))

       = Constant(T_INT, 3)
Step 3:

  1 + 2 + 5

          ^

expr = CreateBinaryExpression(OP_BINARYADD, Constant(T_INT, 3), Constant(T_INT, 5)) = Constant(T_INT, 8)

如果把完整的AST構造出來再做摺疊的話可能看起來更明顯一些：

Step 0: + / + 5 / 1 2


Step 1:

    +

   /

  3   5

Step 2: 8

可以很明顯地看到，這個AST上的兩個加法的操作數都是常量表達式。

但是上面的做法碰到稍微複雜那麼一丁點的情況就紗布了：

x + 1 + 2

假如x是一個局部變數，不是常量表達式，那麼按照上面的做法，如果構造出完整AST的話會是：

+ / + 2 / x 1

雖然字面上看1 + 2是一個常量加法，但實際編譯器看到的結構卻是 (x + 1) + 2 而不是 x + (1 + 2) ，所以1和2並不是相鄰的。

可以看到，對下面的加法，x + 1由於x不是常量所以這個加法也不是常量表達式，然後對上面的加法由於左手邊操作數不是常量表達式，所以這個加法也不是常量表達式。於是上面的簡易常量摺疊就無法把這段代碼優化為 x + 3。

那要怎麼辦呢？很簡單，讓常量摺疊的邏輯多看一層就好了。就這個例子而言，對上面的加法，它應該看看其操作數是否是常量，如果不是的話該操作數是否有部分操作數是常量，是的話就根據加法的結合律來旋轉AST的結構並摺疊常量。

Step 0: + / + 2 / x 1


Step 1: rotate

  +

 /

x   +

   /

  1   2

Step 2: constant fold + / x 3

這就是一種模式匹配。但如果編譯器需要為優化去匹配太多的模式，實現起來就會很繁瑣。所以貫穿於優化編譯器里的一個思想就是代碼的規範化（canonicalize）——儘可能把多種等價形式的代碼規範化為一種統一的形式，這樣後續的模式匹配就只要匹配較少形狀的代碼了。

例如說，再稍微複雜一點的表達式：

1 + x + 2

對應的完整AST：

+ / + 2 / 1 x

這個無論從源碼字面上還是從AST上看，常量都沒有緊挨在一起。所以要怎麼辦？

（順帶：TCC在遇到這樣的代碼時就無法把它常量摺疊為 x + 3，咳咳）

一種思路就是：在創建AST節點的時候，對於二元運算，在滿足交換律的情況下，總是把常量放在右手邊。所以就會有：

Step 0: + / + 2 / 1 x


Step 1: commute

    +

   /

  +   2

 /

x   1

Step 2: rotate ...

後面就跟上一個例子一模一樣了，不再贅述。

綜上，對這組簡單的常量摺疊例子，我們可以對AST定義下述改寫規則：

c1 + c2 =&> c3

其中c3的數值等於c1 + c2的數值

c + x =&> x + c

根據交換律把常量移到右手邊

(x + c1) + c2 =&> x + (c1 + c2)

向下看一層，將常量向右推

(x + c) + y =&> (x + y) + c
x + (y + c) =&> (x + y) + c
(x + c1) + (y + c2) =&> (x + y) + (c1 + c2)

向下看一層，將常量向右推

重複應用這組改寫規則直到不能進一步改寫，我們就能把一串加法表達式中所有常量加法都儘可能向右邊推並且摺疊起來了。

常量摺疊還可以利用上某些算術恆等性，例如說 x + 0 == x ，x * 0 == 0 ， x * 1 == x ，等等。這樣，即便參與運算的操作數只有一邊是常量（另一邊是不是常量都無所謂），利用這些特殊性質我們還是可以做常量摺疊。

當然，要應對一串表達式中的常量摺疊，除了上面的樹改寫（或者DAG改寫）的方法外，還有不少其它方式，其中不乏更「簡單粗暴」的。

例如說，可以把整棵表達式樹「拍扁」（flatten）成一個扁平的多項式，通過排序/分組把相同變數的項合併起來（不包含變數的項也合併起來），就完成了從這棵表達式樹中提取出所有常量項並摺疊之的操作，順帶還可以有效簡化多項式里涉及變數的項的運算。

2、常量傳播

上面提到的常量摺疊是一種只關注非常局部的信息、效果也僅限於非常局部的範圍的一種優化。單獨應用它的話，最大的局限性在於它一般處理不了涉及變數的操作，因為它不會主動去了解變數的定值（definition，或者叫賦值 assignment 也可以）的情況。

那麼考慮下面的例子：

int x = 40; int y = x + 2;

像C語言、Java語言之類的，語言規範層面上都不會把y的初始化表達式 x + 2 規定為一個常量表達式。但我們直覺上覺得編譯器應該能把它也給常量摺疊起來。差在哪裡了呢？

差就差在這裡要提到的「常量傳播」（constant propagation）優化上。變數x的定值是一個常量，int型的40，如果把這個信息傳播到後面所有使用變數x的地方去，那麼那些地方就可以把x當作一個常量來看待，於是就可以做相應的常量優化了，例如說上面所說的常量摺疊。

可是一個變數之所以叫做「變數」就是因為它允許被多次賦值（擁有多個定值），假如例子改為：

int x = 40; x = rand(); int y = x + 2;

則變數x有兩個定值，一個是常量40，而另一個是個未知數值的函數調用返回值，這樣在變數y的初始化表達式處， x + 2 就不能把x看作常量來做優化了，因為x在此處並不應該去常量的那個定值，而要取另一個定值而它不是常量。

所以，要實現常量傳播，它必須要依賴一種叫做「到達定值」（reaching definition）的前向數據流分析（forward data-flow analysis）。它要確定某個定值能被傳播到哪些使用點，或者反過來說，某個使用點上應該採用哪個版本的定值。如果在某個使用點上發現應該使用的定值是一個常量的話，就可以在此處做諸如常量摺疊之類的常量優化了。

對編譯原理有一定了解的同學，如果聽說過SSA形式的話，此時應該會會心一笑。沒錯，這個意義上的常量傳播在SSA形式里是免費的 &>_&<

3、條件常量傳播

所謂「條件常量傳播」（conditional constant propagation），是一種結合了常量摺疊、常量傳播與無用代碼消除（dead code elimination）的優化。它最有趣的效果就是：通過常量傳播與常量摺疊，可能可以消除掉代碼里的某些分支（由於條件是常量），此時可能會發現出更多的常量，於是又能消除更多分支…

試想這樣的例子：

int x = 40; int y = 42; int z = 1;


if (x &> y) {

  z = 2;

}

if (z &> 1) { x = y; }

當我們單純應用常量摺疊時，這個例子沒有任何可優化的地方。

當我們先應用常量傳播然後再常量摺疊，則這個例子可以被優化為：

int x = 40; int y = 42; int z = 1;


if (FALSE) { // x &> y == FALSE

  z = 2;

}

if (z &> 1) { x = y; }

這裡會使得例子中的一個條件分支變成無用代碼，但在消除它之前，我們並不能做更多的優化了。

如果對這個例子應用上條件常量傳播，它就會發現並消除掉這塊無用代碼，並且進一步發現在 if (z &> 1) 處變數z的定值肯定是常量1：

int x = 40; int y = 42; int z = 1;

if (FALSE) { // z &> 1 == FALSE x = y; }

於是最終這個條件分支也被看作無用代碼被消除掉。

大家還可以試試看涉及循環的例子。這邊我就不另外舉例了，有興趣的同學可以參考Wikipedia上的例子：Constant folding

CCP是一種簡單而強大的優化，可以簡化相當做的代碼，為其它優化更有效地進行奠定了良好的基礎。

應用在SSA形式上的CCP叫做SCCP。這也算是現代優化編譯器中的看家本領了，沒實現CCP / SCCP都不好意思出來見人…

會的。常量計算一般在前段就做完了，很簡單的一個演算法（遍歷整個表達式挨個求值）。有時候能求出來一個準確值，但是無法替換。比如：

int a = foo() 0;

不能被換成int a = 0，因為有side effects。

管他多複雜只要都是字面量那就是個編譯期常量，既然叫編譯期常量了...算出來再編譯是什麼鬼？你想說算出來再運行吧...

用vs很方便你隨便寫一條常量表達式然後滑鼠移上去你就能看到結果了。

別說這個編譯期常量了，再比如，除法，我們知道一個除法的指令跟加減乘是差了一個數量級的，如果你的除數是一個編譯期常量，一個聰明的編譯期都能幫你優化掉。比如我用vs寫一個：

#include &

int main() { unsigned int n = 234525235; n = n / 10000; printf("%d ", n); }

先在debug版本看反彙編：

unsigned int n = 234525235; 00D917AE mov dword ptr [n],0DFA9233h n = n / 10000; 00D917B5 mov eax,dword ptr [n] 00D917B8 xor edx,edx 00D917BA mov ecx,2710h 00D917BF div eax,ecx 00D917C1 mov dword ptr [n],eax printf("%d ", n); 00D917C4 mov eax,dword ptr [n] 00D917C7 push eax 00D917C8 push offset string "%d " (0D96B30h) 00D917CD call _printf (0D91316h) 00D917D2 add esp,8

n = n / 10000 後面那一段，就是除法指令，一大堆。

然後在看看release版本的：

unsigned int n = 234525235; n = n / 10000; printf("%d ", n); 00EE1040 push 5B9Ch // 23452 00EE1045 push offset string "%d " (0EE20F8h) unsigned int n = 234525235; n = n / 10000; printf("%d ", n); 00EE104A call printf (0EE1010h) 00EE104F add esp,8

。。中間哪個 5B9Ch 就是 23452，這直接把結果算出來了。

感興趣看看這篇blog ：編譯器是如何實現32位整型的常量整數除法優化的？[C/C++] - shines77 - 博客園

還有很多很多的各種優化例子。

————————

最後就一句話，給在座的各位（包括我）：

在如今，除非你是 R大這樣的人，否則不要去試圖幫編譯器優化，因為人類優化代碼時通常都是錯誤的。通常，編譯器都會比你做得更好。

不止是編譯器了，sql都有這個常量摺疊(constant folding)優化規則，最近學習到hive opertimizer里也有類似的處理。

看你編譯優化參數

會

我覺得會的。實在不行用c舉個例子，你寫const，就一定會了，我猜的。。話說編譯器選項里應該有

我只能舉java的例子

這是源代碼：

這是編譯後的class文件再反編譯後的：

說明會算出結果再寫成機器碼

我不知道實際答案，我猜一下，覺得不會。

我是這樣考慮的，假設會的話，那我的源代碼裡面寫很多這種計算，不是會造成編譯器極大的額外開銷？

另外，在c語言中，我如果計算過程中用到了的是外部常量，假設我又忘記定義這個常量，那麼是在鏈接過程中報錯的吧。