Nếu bạn viết (a*b + 1) * (a*b + 2), con người đọc thấy ngay a*b xuất hiện hai lần và chỉ cần tính một lần. Trình biên dịch cũng thấy — nó gọi việc này là gộp biểu thức chung (common subexpression elimination, CSE): nhận ra một phép tính lặp lại, tính một lần rồi dùng lại kết quả. Bài này biên dịch thật trong container và đếm số phép nhân trong assembly để thấy CSE hoạt động — rồi vấp đúng cái ranh giới khiến trình biên dịch không dám gộp, và một lần chính công cụ đếm của tôi nói dối.
CSE gộp cái gì
CSE tìm những biểu thức con cho cùng một giá trị ở nhiều nơi và tính chúng một lần. (a*b + 1) * (a*b + 2) có hai lần a*b; thay vì nhân hai lần, trình biên dịch tính t = a*b một lần rồi dùng t cho cả hai. Đây là một trong những tối ưu cơ bản nhất, bật từ -O1. Nghe hiển nhiên, nhưng có một điều kiện ẩn quyết định tất cả: trình biên dịch chỉ được gộp khi nó chứng minh được hai lần xuất hiện chắc chắn cho cùng giá trị. Với số học thuần trên biến cục bộ thì hiển nhiên. Với dữ liệu đọc qua con trỏ thì không — và đó là chỗ CSE lặng lẽ tắt.
Đo: đếm phép nhân trong assembly
Tôi biên dịch int f(int a, int b){ return (a*b + 1) * (a*b + 2); } rồi đếm lệnh mul ở từng mức tối ưu (aarch64, gcc 13):
-O0: mul = 3 (a*b tính hai lần + phép nhân ngoài)
-O1/-O2: mul = 1
Ở -O0 trình biên dịch dịch nguyên văn: hai lần a*b là hai lệnh mul, cộng phép nhân ngoài cùng, tổng ba. Ở -O1 trở lên chỉ còn một mul. Đọc assembly -O2 để biết nó làm gì:
mul w1, w0, w1 ; t = a*b (tính MỘT lần — CSE)
add w0, w1, 2 ; t + 2
madd w0, w1, w0, w0 ; (t+1)*(t+2) gộp vào một lệnh nhân-cộng
a*b chỉ còn một lệnh, dùng lại cho cả hai vế — đúng là CSE. (Phép nhân ngoài cùng thì trình biên dịch dồn vào một lệnh madd, nhân-rồi-cộng trong một nhịp, nên chỉ đếm được một mul "thuần".) Với số học cục bộ, CSE làm việc gọn gàng, không có gì bất ngờ.
Bất ngờ đến khi tôi đưa cùng ý tưởng đó qua bộ nhớ. Tôi viết một hàm đọc *p hai lần, với một phép ghi vào *q chen giữa:
void alias(long *p, long *q){
long x = *p * *p;
*q = 7;
long y = *p * *p; // giống hệt dòng đầu?
g(x, y);
}
Đọc assembly -O2 bằng objdump từng hàm:
alias: nạp *p = 2 lần, mul = 2
CSE không gộp. *p * *p được tính lại từ đầu ở dòng thứ hai — hai lần nạp *p, hai lần nhân. Lý do: giữa hai lần đọc có *q = 7, và trình biên dịch không biết q có trỏ vào đúng ô mà p trỏ tới hay không. Nếu q trùng p (aliasing), thì *q = 7 đã đổi *p, và x với y phải khác nhau. Không chứng minh được q ≠ p, trình biên dịch buộc phải giả định điều tệ nhất và nạp lại.
Bằng chứng: tôi thêm restrict — lời hứa với trình biên dịch rằng p và q không trỏ chung (như bài về restrict đã đo) — rồi biên dịch lại:
norestrict (có restrict): nạp *p = 1 lần, mul = 1
Chỉ một lần nạp, một phép nhân. Nhờ restrict bảo đảm *q = 7 không thể chạm tới *p, trình biên dịch tự tin gộp hai *p * *p thành một. Cùng một đoạn mã, chỉ khác một từ khóa hứa hẹn, mà CSE bật hay tắt.
Một lần tôi đo hớ: công cụ đếm của tôi nói dối
Trước khi dùng objdump, tôi đếm lệnh bằng một đoạn awk cắt lấy thân hàm từ assembly -S: bắt đầu ở nhãn alias: và dừng khi gặp ret. Nó báo hàm alias có 3 lần nạp *p và 3 mul — một con số kỳ quặc, vì mã nguồn chỉ đọc *p bốn lần và tôi chờ 2 hoặc 4, không phải 3.
Con số lẻ đó là dấu hiệu tôi đang đo nhầm. Tôi mở thẳng assembly ra đọc và thấy vấn đề: hai hàm này kết thúc bằng một lời gọi đuôi (tail call) b g — một lệnh nhảy thẳng sang g thay cho cặp "gọi rồi trả về" — chứ không có lệnh ret. Đoạn awk của tôi dừng ở ret, mà alias chẳng có ret nào, nên nó chạy tuột qua ranh giới hàm và nuốt luôn một phần hàm norestrict phía sau. Con số "3" là tổng lai của hai hàm dính vào nhau.
Đọc lại bằng objdump -d --disassemble=alias — tách đúng từng hàm theo bảng ký hiệu — cho con số thật: alias 2 nạp, 2 mul; norestrict 1 nạp, 1 mul. Bài học đo lường đúng với cả sê-ri: công cụ đo của tôi là một biến. Đoạn awk ngầm giả định "mọi hàm kết thúc bằng ret", và một tối ưu — biến lời gọi cuối thành lời gọi đuôi — phá vỡ giả định đó, khiến bộ đếm sai mà không báo lỗi. Nếu tôi tin con số "3" và viết bài quanh nó, tôi đã kể một câu chuyện hoàn toàn bịa. Số đo kỳ quặc nghĩa là công cụ đang nói dối; phải đọc thẳng cái mình đo, đừng tin bộ đếm.
Và cái tôi suýt bỏ lỡ khi mải sửa công cụ chính là bài học thật: CSE không phải phép thần. Nó không nhìn thấy "hai dòng giống nhau" rồi gộp bừa; nó chỉ gộp khi chứng minh được hai lần cho cùng một giá trị. Một phép ghi qua con trỏ có thể trùng là đủ để phá chứng minh đó, và trình biên dịch chọn đúng đắn nhưng tốn kém: tính lại.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng thủ công "tối ưu" bằng cách gộp biểu thức mà trình biên dịch đã tự làm — với số học cục bộ. Viết int t = a*b; return (t+1)*(t+2); không nhanh hơn (a*b+1)*(a*b+2) một mảy may ở -O1 trở lên, vì CSE đã gộp rồi; nó chỉ làm mã dài hơn. Sức của bạn nên để dành cho chỗ CSE không tự làm được.
Hệ quả thứ hai, và là chỗ đáng để tâm nhất: CSE trên dữ liệu bộ nhớ bị chặn bởi khả năng trùng con trỏ. Nếu một vòng lặp đọc arr[i] nhiều lần và giữa chừng có ghi qua một con trỏ khác, trình biên dịch có thể phải nạp lại arr[i] mỗi lần — biến cái tưởng là một lần đọc thành nhiều lần đọc bộ nhớ. Đây là lý do những đoạn mã "nhìn thì đọc một biến" lại chậm bất ngờ: trình biên dịch bị buộc phải bảo thủ. Cách gỡ giống hệt các phần trước của sê-ri: giúp trình biên dịch biết các con trỏ không giẫm chân nhau — bằng restrict, bằng cách nạp giá trị vào một biến cục bộ một lần rồi dùng lại (long v = *p; rồi tính trên v), hoặc bằng cách sắp xếp mã để phép ghi không xen giữa các phép đọc.
Hệ quả thứ ba là một nguyên tắc đo lường chung, học được từ chính lần đo hớ: khi một con số trông vô lý, nghi công cụ trước, đừng nghi thực tại. Con số "3 mul" của tôi không phải vì trình biên dịch làm điều lạ, mà vì bộ đếm của tôi hỏng ở một giả định ẩn (hàm phải kết bằng ret). Con số mang theo: CSE tính một biểu thức lặp đúng một lần — (a*b) từ 3 phép nhân ở -O0 xuống 1 ở -O1 — nhưng chỉ khi trình biên dịch chứng minh được hai lần cho cùng giá trị; một phép ghi qua con trỏ có thể trùng làm nó buộc phải tính lại (2 nạp/2 mul), và restrict gỡ đúng chỗ đó (1 nạp/1 mul). Muốn trình biên dịch gộp phép tính lặp trên bộ nhớ, hãy cho nó bằng chứng rằng dữ liệu không đổi giữa các lần dùng.
Thử ba mươi giây
Viết một hàm nhỏ đọc cùng một ô nhớ hai lần với một phép ghi chen giữa: long f(long *p, long *q){ long a = *p; *q = 5; long b = *p; return a + b; }. Biên dịch với gcc -O2 -S và đếm số lệnh ldr nạp từ [p] — bạn sẽ thấy hai lần nạp, vì q có thể trùng p. Giờ đổi chữ ký thành long *restrict p, long *restrict q và biên dịch lại: chỉ còn một lần nạp. Cùng đoạn mã, khác một lời hứa, và bạn vừa tận mắt thấy CSE bật lên. Nếu muốn chắc mình đọc đúng hàm, dùng objdump -d --disassemble=f thay vì tự cắt bằng grep — vì hàm của bạn có thể kết bằng lời gọi đuôi, không phải ret.
