Trình biên dịch có thể làm gì với thông tin phân nhánh?

Question

Trên một Pentium hiện đại, nó không còn có thể đưa ra gợi ý phân nhánh cho bộ xử lý. Giả sử rằng một trình biên dịch profiling như gcc với tối ưu hóa hướng dẫn profile có thông tin về hành vi phân nhánh có khả năng, nó có thể làm gì để tạo ra mã sẽ thực thi nhanh hơn?

Tùy chọn duy nhất tôi biết là di chuyển các nhánh không chắc đến hết chức năng. Có gì khác?

Cập nhật.

http://download.intel.com/products/processor/manual/325462.pdf khối lượng 2a, mục 2.1.1 nói

"tiền tố Chi nhánh gợi ý (2EH, 3EH) cho phép một chương trình để đưa ra một gợi ý để xử lý về đường dẫn mã có khả năng nhất cho một chi nhánh. Sử dụng các Chỉ sử dụng các tiền tố chi nhánh có điều kiện khác (Jcc). Việc sử dụng các tiền tố gợi ý chi nhánh khác và/hoặc các mã opcodes không xác định khác với hướng dẫn Intel 64 hoặc IA-32 được đặt trước;

Tôi không biết liệu những điều này có thực sự có hiệu lực hay không.

Mặt khác, 3.4.1. . Của http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf nói

" Trình biên dịch tạo ra mã để cải thiện hiệu quả của dự đoán rẽ nhánh trong bộ vi xử lý Intel Intel C++ Compiler hoàn thành điều này bằng cách:

• đang lưu giữ và dữ liệu trên các trang riêng biệt
• sử dụng có điều kiện hướng dẫn di chuyển để loại bỏ các chi nhánh
• mã tạo phù hợp với thuật toán dự đoán nhánh tĩnh
• nội tuyến nếu thích hợp
• unrolling nếu số lần lặp lại là có thể dự đoán

Với tối ưu hóa từng cấu hình hướng dẫn, trình biên dịch có thể đặt ra các khối cơ bản để loại bỏ các chi nhánh cho hầu hết đường thường xuyên thực hiện một chức năng hoặc ít nhất là cải thiện khả năng dự báo của họ. Chi nhánh dự đoán cần không phải là mối quan tâm ở cấp nguồn. Để biết thêm thông tin, hãy xem tài liệu về Trình biên dịch Intel C++. "

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf nói trong 'Cải tiến hiệu suất với PGO'

" PGO việc tốt nhất cho mã với nhiều chi nhánh thường xuyên thực hiện mà khó có thể dự đoán tại thời gian biên dịch. Ví dụ là mã có kiểm tra lỗi chuyên sâu trong đó các điều kiện lỗi là sai phần lớn thời gian. Mã lỗi xử lý lỗi (không thường xuyên) được thực hiện có thể được di dời để nhánh này hiếm khi được dự đoán không chính xác. Giảm thiểu đang lạnh xen kẽ vào thường xuyên thực hiện (nóng) mã cải thiện hướng dẫn bộ nhớ cache hành vi."

Answer 1

Nếu nó rõ ràng là một vòng lặp hiếm khi được nhập vào, hoặc là nó thường lặp rất ít lần, sau đó trình biên dịch có thể tránh unrolling các vòng lặp, như làm như vậy có thể thêm rất nhiều phức tạp có hại để xử lý các điều kiện cạnh (một số lẻ lặp đi lặp lại, vv).Vectorisation, đặc biệt, nên tránh trong trường hợp này.

Trình biên dịch có thể sắp xếp lại các kiểm tra lồng nhau, do đó trình biên dịch kết quả thường xuyên nhất có thể được sử dụng để tránh thực hiện kiểm tra về điều gì đó với tốc độ truyền 50%.

Phân bổ đăng ký có thể được tối ưu hóa để tránh việc đăng ký tràn khối lượng hiếm khi được sử dụng trong trường hợp thông thường.

Đây chỉ là một số ví dụ. Tôi chắc rằng có những người khác mà tôi chưa từng nghĩ tới.

Answer 2

Tắt đầu của tôi, bạn có hai tùy chọn.

Tùy chọn # 1: Thông báo cho trình biên dịch các gợi ý và để trình biên dịch sắp xếp mã phù hợp. Ví dụ, GCC hỗ trợ như sau ...

__builtin_expect((long)!!(x), 1L) /* GNU C to indicate that <x> will likely be TRUE */ 
__builtin_expect((long)!!(x), 0L) /* GNU C to indicate that <x> will likely be FALSE */ 

Nếu bạn đặt chúng trong hình thức vĩ mô như ...

#if <some condition to indicate support> 
    #define LIKELY(x) __builtin_expect((long)!!(x), 1L) 
    #define UNLIKELY(x) __builtin_expect((long)!!(x), 0L) 
#else 
    #define LIKELY(x) (x) 
    #define UNLIKELY(x) (x) 
#endif 

... bây giờ bạn có thể sử dụng chúng như ...

Điều này khiến trình biên dịch tự do tổ chức các nhánh theo thuật toán dự đoán nhánh tĩnh và/hoặc nếu trình xử lý và trình biên dịch hỗ trợ nó, sử dụng hướng dẫn cho biết nhánh nào có nhiều khả năng được thực hiện hơn.

Tùy chọn # 2: Sử dụng toán học để tránh phân nhánh.

if (a < b) 
    y = C; 
else 
    y = D; 

Điều này có thể được viết lại như ...

x = -(a < b); /* x = -1 if a < b, x = 0 if a >= b */ 
x &= (C - D); /* x = C - D if a < b, x = 0 if a >= b */ 
x += D;   /* x = C if a < b, x = D if a >= b */ 

Hope this helps.

Answer 3

Nó có thể làm cho sự sụp đổ (ví dụ như trường hợp một nhánh không được lấy) đường dẫn được sử dụng nhiều nhất. Điều đó có hai hiệu ứng lớn:

1. chỉ có 1 nhánh có thể được lấy trên mỗi đồng hồ, hoặc trên một số bộ xử lý ngay cả trên 2 đồng hồ, vì vậy nếu có bất kỳ chi nhánh nào khác (thường có, hầu hết các mã quan trọng trong vòng lặp)), một chi nhánh được lấy là tin xấu, một nhánh không được lấy ít hơn.
2. khi dự đoán nhánh sai, mã mà nó phải thực thi có nhiều khả năng nằm trong bộ nhớ cache mã (hoặc bộ nhớ cache opop, nếu có). Nếu không, điều đó có thể là do quá trình khởi động lại đường ống dẫn và đang chờ thiếu bộ nhớ cache. Đây là vấn đề ít xảy ra ở hầu hết các vòng lặp, vì cả hai phía của nhánh đều có khả năng nằm trong bộ nhớ đệm, nhưng nó lại được chơi trong các vòng lớn và các mã khác.

Nó cũng có thể quyết định xem có nên thực hiện nếu chuyển đổi dựa trên dữ liệu tốt hơn so với dự đoán phỏng đoán hay không. Nếu chuyển đổi có thể có vẻ như "luôn là một ý tưởng hay", nhưng không phải vậy, chúng chỉ "thường là một ý tưởng hay". Nếu nhánh trong triển khai phân nhánh được dự đoán rất tốt, mã nếu được chuyển đổi cũng có thể chậm hơn.

Answer 4

Có hai nguồn có thể cho thông tin mà bạn muốn:

1. Có Intel 64 và Hướng dẫn sử dụng IA-32 Kiến trúc phát triển phần mềm (3 tập).Đây là một công trình lớn đã phát triển trong nhiều thập kỷ. Đó là tài liệu tham khảo tốt nhất mà tôi biết về rất nhiều chủ đề, kể cả dấu phẩy động. Trong trường hợp này, bạn muốn kiểm tra volume 2, tham chiếu set instruction.
2. Có Hướng dẫn tham khảo về kiến ​​trúc quang học của Intel 64 và IA-32. Điều này sẽ cho bạn biết về một số thuật ngữ ngắn gọn những gì mong đợi từ mỗi kiến ​​trúc vi mô.

Bây giờ, tôi không biết ý bạn là gì bởi một bộ vi xử lý "Pentium hiện đại", đây là năm 2013, phải không? Không còn bất kỳ Pentium nào nữa ...

Bộ hướng dẫn không hỗ trợ cho bộ xử lý biết nếu chi nhánh được dự kiến ​​thực hiện hoặc không được thực hiện bởi tiền tố đến hướng dẫn chi nhánh có điều kiện (như JC, JZ, v.v.) . Xem khối lượng 2A của (1), phần 2.1.1 (của phiên bản tôi có) Tiền tố hướng dẫn. Có các tiền tố 2E và 3E không được lấy và lấy tương ứng. Để xem liệu các tiền tố này có thực sự có hiệu lực hay không, nếu chúng ta có thể nhận được thông tin đó, nó sẽ nằm trong Hướng dẫn tham khảo tối ưu hóa, phần cho vi kiến ​​trúc bạn muốn (và tôi chắc chắn nó sẽ không phải là Pentium) .

Ngoài việc sử dụng chúng, có toàn bộ phần trong Hướng dẫn tham khảo tối ưu hóa về chủ đề đó, đó là phần 3.4.1 (của phiên bản tôi có).

Không có ý nghĩa gì khi tái tạo ở đây vì bạn có thể tải xuống hướng dẫn miễn phí. ngắn gọn:

• Loại bỏ các chi nhánh bằng cách sử dụng các hướng dẫn điều kiện (CMOV, SETcc),
• Hãy xem xét các thuật toán dự đoán tĩnh (3.4.1.3),
• nội tuyến
• Vòng unrolling

Ngoài ra, một số trình biên dịch, GCC, ví dụ, ngay cả khi CMOV là không thể, thường thực hiện số học bitwise để chọn một trong hai điều riêng biệt tính toán, do đó tránh các chi nhánh. Nó thực hiện điều này đặc biệt với các lệnh SSE khi các vòng vectơ hóa.

Về cơ bản, các điều kiện tĩnh là:

• chi nhánh không điều kiện được dự đoán sẽ được thực hiện (... loại expectable ...)
• chi nhánh gián tiếp được dự đoán không được thực hiện (vì một phụ thuộc dữ liệu)
• điều kiện ngược được dự đoán sẽ được thực hiện (tốt cho vòng)
• Forward điều kiện được dự báo không được đưa

Bạn có thể muốn đọc toàn bộ phần 3.4.1.