Tối ưu hóa vòng lặp "tĩnh"

Question

Tôi đang viết một ngôn ngữ biên soạn cho vui, và gần đây tôi đã nhận được một cú đá để làm trình biên dịch tối ưu hóa của tôi rất mạnh mẽ. Tôi đã tìm ra một số cách để tối ưu hóa một số thứ, ví dụ, 2 + 2 luôn là 4, vì vậy chúng ta có thể thực hiện phép tính đó trong thời gian biên dịch, nếu (false) {...} có thể bị xóa hoàn toàn, v.v ... Tôi đã nhận được vòng lặp. Sau khi một số nghiên cứu, tôi nghĩ rằng những gì tôi đang cố gắng làm là không chính xác vòng lặp unrolling, nhưng nó vẫn là một kỹ thuật tối ưu hóa. Hãy để tôi giải thích.

Lấy mã sau đây.

String s = ""; 
for(int i = 0; i < 5; i++){ 
    s += "x"; 
} 
output(s); 

Là một con người, tôi có thể ngồi đây và nói với bạn rằng đây là 100% thời gian sẽ tương đương với

output("xxxxx"); 

Vì vậy, nói cách khác, vòng lặp này có thể được "biên soạn ra "hoàn toàn. Nó không phải là vòng lặp unrolling, nhưng những gì tôi gọi là "hoàn toàn tĩnh", đó là, không có đầu vào nào có thể thay đổi hành vi của phân khúc. Ý tưởng của tôi là bất cứ thứ gì hoàn toàn tĩnh có thể được giải quyết thành một giá trị duy nhất, bất cứ thứ gì dựa vào đầu vào hoặc làm cho đầu ra có điều kiện của khóa học không thể được tối ưu hóa thêm. Vì vậy, từ quan điểm của máy, tôi cần phải cân nhắc điều gì? Điều gì làm cho một vòng lặp "hoàn toàn tĩnh?"

Tôi đã đưa ra ba loại vòng mà tôi cần tìm ra cách phân loại. Các vòng lặp sẽ luôn luôn kết thúc với cùng trạng thái máy sau mỗi lần chạy, bất kể đầu vào, vòng lặp S W KHÔNG BAO GIỜ hoàn tất và các vòng lặp mà tôi không thể tìm ra theo cách này hay cách khác. Trong trường hợp đó tôi không thể tìm ra nó (nó có điều kiện thay đổi bao nhiêu lần nó sẽ chạy dựa trên đầu vào năng động), tôi không lo lắng về việc tối ưu hóa. Các vòng lặp vô hạn sẽ là một lỗi biên dịch/cảnh báo trừ khi bị chặn bởi trình lập trình và các vòng lặp giống nhau mỗi lần chỉ cần bỏ qua trực tiếp để đặt máy ở trạng thái thích hợp, không lặp lại.

Trường hợp chính tất nhiên để tối ưu hóa là lặp vòng lặp tĩnh, khi tất cả các cuộc gọi hàm bên trong cũng tĩnh. Xác định xem một vòng lặp có các thành phần động là đủ dễ dàng không và nếu nó không động, tôi đoán nó phải là tĩnh. Điều tôi không thể tìm ra là làm thế nào để phát hiện nếu nó sẽ là vô hạn hay không. Có ai có bất cứ suy nghĩ về điều này? Tôi biết đây là một tập hợp con của vấn đề tạm dừng, nhưng tôi cảm thấy nó có thể giải quyết được; vấn đề tạm dừng là một vấn đề do thực tế là đối với một số tập hợp chương trình, bạn không thể nói nó có thể chạy mãi mãi, nó có thể không, nhưng tôi không muốn xem xét những trường hợp đó, tôi chỉ muốn xem xét các trường hợp nơi nó S h dừng lại, hoặc nó S W KHÔNG dừng lại, nhưng trước tiên tôi phải phân biệt giữa ba trạng thái.

Answer 1

Điều này trông giống như một loại bộ giải mã tượng trưng có thể được xác định cho một số lớp, nhưng không phải là chung.

Hãy hạn chế yêu cầu một chút: không bị tràn số, chỉ cho vòng lặp (đôi khi có thể được chuyển thành vòng lặp đầy đủ, trừ khi sử dụng tiếp tục, v.v.), không ngắt, không sửa đổi biến điều khiển bên trong vòng lặp for .

for (var i = S; E(i); i = U(i)) ...

trong đó E (i) và U (i) là những biểu hiện có thể được thao tác một cách tượng trưng.Có một số lớp học là tương đối dễ dàng:

U(i) = i + CONSTANT: n chu kỳ -thứ giá trị của i là S + n * CONSTANT

U(i) = i * CONSTANT: n chu kỳ -thứ giá trị của i là S * CONSTANT^n

U(i) = i/CONSTANT: n -thứ chu kỳ giá trị của i là S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n chu kỳ -thứ giá trị của i là (S + n * CONSTANT) % M

và một số kết hợp khác khá dễ dàng (và một số những người rất khó khăn)

Xác định vòng lặp kết thúc đang tìm kiếm n nơi E(i(n)) là sai. Điều này có thể được thực hiện bởi một số thao tác tượng trưng cho nhiều trường hợp, nhưng có rất nhiều công việc liên quan đến việc làm cho người giải quyết.

Ví dụ:

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n, E(i(n)) =>not(n < 5) =>
• n >= 5 => dừng cho n = 5

---

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - kể từ n là một số nguyên không âm này là không bao giờ thành sự thật - không bao giờ dừng lại

---

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => điều này không bao giờ đúng => không bao giờ dừng

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) =>
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n)) =>not(10 * 3^n < 480) =>10 * 3^n >= 480 =>3^n >= 48 =>n >= log3(48) =>n >= 3.5... =>
• kể từ n là toàn bộ => nó sẽ dừng lại cho n = 4

đối với trường hợp khác, nó sẽ là tốt nếu họ có thể được chuyển thành những người bạn đã có thể giải quyết ...

Nhiều thủ thuật cho thao tác biểu tượng đến từ kỷ nguyên Lisp, và không phải là quá khó khăn. Mặc dù những người được mô tả (hoặc biến thể) là loại thực hành phổ biến nhất, có nhiều khó khăn hơn và/hoặc không thể giải quyết các kịch bản.