Tạo mã trình biên dịch - đăng ký cấp phát bên trong các khối điều kiện

Question

Tôi đang viết trình biên dịch cho một khóa học. Tôi đã chạy vào một số vấn đề tối ưu hóa mà tôi không chắc chắn cách xử lý tối ưu. Giả sử có một vòng lặp while từ ngôn ngữ đầu vào sử dụng N biến cục bộ phải được giữ trong sổ đăng ký (hoặc nên, để tính toán nhanh). Giả sử N> K, số lượng thanh ghi. Có một cơ hội của thanh ghi có điều kiện được thay đổi gần cuối vòng lặp while.

Ví dụ, giả sử thanh ghi cho x (giả sử% eax trên i386) được xác định trước tuyên bố sau:

while (x) { x = x - 1 ; /* more statements */ } 

Trong báo cáo mã nhiều hơn, nó có thể cho x được đổ trở lại ngăn xếp. Khi mã nhảy trở lại phần đầu của vòng lặp while để đánh giá lại x, nó sẽ cố gắng sử dụng% eax - nhưng điều này có thể thậm chí không giữ giá trị của x bây giờ. Vì vậy, chúng ta có thể có cái gì đó như

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
_LOOP1: cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  #eax now holds something else 
     .... 
     jmp _LOOP1 

Một giải pháp tôi đang sử dụng là để buộc các mã để đổ tất cả các thanh ghi sửa đổi trước khi câu lệnh while (vì vậy thanh ghi này được xem như trống từ góc độ tạo mã của). Sau nhãn cho vòng lặp while, mã phải tải mọi thứ vào thanh ghi khi cần thiết.

Giải pháp của tôi là một cái gì đó như thế này:

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
     movl %eax, -8(%ebp)  # spilling and clearing all registers 
_LOOP1: movl -8(%ebp), %eax  # get a register for x again 
     cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  # eax now holds something else 
     .... 
     movl %eax, -8(%ebp)  # spill to prevent overwrite 
     jmp _LOOP1 

Nó có vẻ như giải pháp của tôi là một chút không liên quan hoặc không cần thiết. Có một số mẹo tối ưu hóa chung tôi đang quên ở đây?

EDIT: Tôi cũng muốn lưu ý điều gì đó tương tự xảy ra cho các điều kiện như nếu và nếu có. Điều này xảy ra cho họ bởi vì một thanh ghi có thể được cấp phát cho một biến bên trong khối cho điều kiện, nhưng trình tạo mã giả định nó đã được chuyển vào đó cho mọi thứ khác sau đó. Tôi có cách tiếp cận tương tự để đối phó với trường hợp đó.

Answer 1

Kỹ thuật chung mà bạn đang tìm kiếm ở đây thường được gọi là "tách dải ô trực tiếp". A Google Search cho thuật ngữ đó sẽ cung cấp cho bạn các con trỏ tới một loạt các bài báo khác nhau. Về cơ bản, ý tưởng là bạn muốn chia một biến duy nhất (x trong ví dụ của bạn) thành nhiều biến với các dải trực tiếp tách rời mà mỗi biến được sao chép sang biến tiếp theo tại điểm tách. Vì vậy, bạn sẽ có x.0 trước vòng lặp, được sao chép vào x.1 ngay trước while và được sử dụng như vậy trong vòng lặp. Sau đó, ngay sau vòng lặp, bạn sao chép x.1 vào x.2 và sử dụng nó sau vòng lặp. Mỗi một vars tách sẽ có khả năng được cấp phát cho một thanh ghi khác (hoặc ngăn xếp ngăn xếp).

Có rất nhiều sự cân bằng ở đây - việc chia nhỏ quá nhiều dẫn đến (nhiều) biến trong mã, khiến việc đăng ký phân bổ chậm hơn nhiều và có khả năng dẫn đến các bản sao không cần thiết.